CodeForces Round #226(Div2)
みなさんお久しぶりです。chigichanです。
今回は10日くらい前のCFについてです。
とても、印象深い回だったので。。。
まずCFをご存じでしょうか？？
うちの部活ないではあまりメジャーではない気がするので...
そこでwikipedia大先生に聞いてみました。
うん、英語わからない ＞＜
まぁ、僕の適当な理解でいくと、だいたい週1くらいのペースで0:30~2:30の2時間
開かれているコンテストです。SRMと違って問題数は5問あります。しかし、SRMと同様、
Ratingというシステムがあり、それぞれ色が分かれています。
2200- Grand Master
2050-2199 International Master
1900-2049 Master
1700-1899 Candidate Master
1500-1699 Expert
1350-1499 Specialist
1200-1349 Pupil
-1199 Newbie
みたいな感じです。
で、Candidate Master以上がDiv1でそれ未満はDiv2となって
います。
あと、Hackという、SRMのチャレンジみたいなのがあります。なにかしらの問題を提出し、Rockという操作を行うことで、同じRoom内のその問題のコードを読むことが出来ます。そこで、このインプット投げたら落ちそう、的なのをなげて成功すれば得点がもらえます。
もし、自分のコードがHackにより落とされたとき、Rockをしていなければ、再提出が出来ます。
ここは戦略の一つになりますね。
個人的にはSRMよりもCFのほうがおすすめです。
理由としては
こんなところですね。
で、なんで、みんなこれに参加しないのかわからないですね。
とっても楽しいと思うのですが。。。
ま、原因はSRMに比べて英語がムズイ(Reading Hard)だからなのかなぁと思います。
とっても、前置きが長くなりましたが、この前のRound #226で思ったことです。
とりあえず、時系列順に自分のsubmit履歴を並べると、
問題はこちらで
A問題、英語はわからなかったが適当にサンプルから察した。
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<cctype> #include<complex> #include<iostream> #include<sstream> #include<algorithm> #include<functional> #include<vector> #include<string> #include<stack> #include<queue> #include<map> #include<set> #include<bitset> using namespace std; const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1}; #define INF 1e+8 #define EPS 1e-8 #define rep(i,j) for(int i = 0; i < (j); i++) #define reps(i,j,k) for(int i = j; i < k; i++) typedef long long ll; typedef pair<int,int> Pii; int main(){ int n,c; int ans = -10000; int value[128]; cin >> n >> c; rep(i,n)scanf("%d",&value[i]); rep(i,n-1){ ans = max(ans,value[i]-value[i+1]-c); } if(ans < 0)puts("0"); else printf("%d\n",ans); return 0; }
B問題、(文字列全体の長さ - 最初に見つかった"bear"の位置)を足していったらあってた。
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<cctype> #include<complex> #include<iostream> #include<sstream> #include<algorithm> #include<functional> #include<vector> #include<string> #include<stack> #include<queue> #include<map> #include<set> #include<bitset> using namespace std; const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1}; #define INF 1e+8 #define EPS 1e-8 #define rep(i,j) for(int i = 0; i < (j); i++) #define reps(i,j,k) for(int i = j; i < k; i++) typedef long long ll; typedef pair<int,int> Pii; int main(){ int ans = 0; string str; cin >> str; int len = str.size(); rep(i,len-3){ reps(j,i,len-3){ if(str[j] == 'b' && str[j+1] == 'e' && str[j+2] == 'a' && str[j+3] == 'r'){ ans += (len-j-3); break; } } } printf("%d\n",ans); return 0; }
C問題、提出を7度するも5RE & 2TLEでほげほげ
TLEするコード
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<cctype> #include<complex> #include<iostream> #include<sstream> #include<algorithm> #include<functional> #include<vector> #include<string> #include<stack> #include<queue> #include<map> #include<set> #include<bitset> #include<numeric> using namespace std; const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1}; #define INF 1e+8 #define EPS 1e-8 #define rep(i,j) for(int i = 0; i < (j); i++) #define reps(i,j,k) for(int i = j; i < k; i++) typedef long long ll; typedef pair<int,int> Pii; vector < ll > PRIME(10000005); map<int,int> Prime(int n){ map < int,int > res; reps(i,2,n+1){ while(n % i == 0){ ++res[i]; n /= i; } } if(n != 1)res[n] = 1; return res; } int main(){ int n; scanf("%d",&n); rep(i,n){ int tmp; scanf("%d",&tmp); map<int,int> sub; sub = Prime(tmp); map<int,int>::iterator it = sub.begin(); for(;it != sub.end();it++){ PRIME[it->first]++; } } partial_sum(PRIME.begin(), PRIME.end(), PRIME.begin()); int m; scanf("%d",&m); rep(i,m){ int l,r; scanf("%d%d",&l,&r); if(r >= 10000000)r = 10000000; if(l >= 10000000)l = 10000000; printf("%lld\n", PRIME[r] - PRIME[l-1]); } return 0; }
なにがまずかったのか？？？？？？
結論から言うと、素因数分解の方法が甘かった。
先に、エラトステネスの篩をしてから、その素数たちで、素因数分解したらACしますた。
ACするコード
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<cctype> #include<complex> #include<iostream> #include<sstream> #include<algorithm> #include<functional> #include<vector> #include<string> #include<stack> #include<queue> #include<map> #include<set> #include<bitset> #include<numeric> #define INF 1e+8 #define EPS 1e-8 #define PB push_back #define fi first #define se second #define rep(i,j) for(int i = 0; i < (j); i++) #define reps(i,j,k) for(int i = j; i < k; i++) using namespace std; typedef long long ll; typedef pair<int,int> Pii; int cnt[10000001]; int a[10000001]; int vp[10001]; int make_prime(){ int index = 0; a[0] = a[1] = 1; for(int i = 2; i*i <= 10000000; i++){ if(a[i]==0){ vp[index++] = i; for(int j = i*i; j <= 10000000;j+=i){ a[j] = 1; } } } return index; } int main(){ int len = make_prime(); int n; scanf("%d",&n); rep(i,n){ int tmp; int index=0; scanf("%d",&tmp); while(tmp != 1 && index < len){ bool f=false; while(tmp%vp[index]==0){ tmp/=vp[index]; f=true; } if(f)cnt[vp[index]]++; index++; } if(tmp!=1)cnt[tmp]++; } rep(i,10000000)cnt[i+1] += cnt[i]; int m; scanf("%d",&m); rep(i,m){ int l,r; scanf("%d%d",&l,&r); if(r >= 10000000)r = 10000000; if(l >= 10000000)l = 10000000; printf("%d\n",cnt[r]-cnt[l-1]); } return 0; }
このC問題みたいなのとてもすきです。ただアルゴリズム知ってるだけでも結局のところ
使いこなせないとただのザコなんだなぁと強く実感しました。
やっぱり競技趣味勢としてこれからも精進していきたいと思います。
それでは。
