Codeforces Beta Round #63 (Div2 Only)
春休みという流れでCodeforcesにノリで初参加。
TopCoderもあわせて久しぶりのDiv2なので嬉しい気分。
(ちなみに操作のしかたはよくわかりませんでした)
A: Young Physicist
沢山あるベクトル(3次元)の和が0ベクトルになるかどうか判定する。
書くだけ。
#include<stdio.h> int d[3]; int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++){ int e,f,g; scanf("%d%d%d",&e,&f,&g); d[0]+=e; d[1]+=f; d[2]+=g; } if(d[0]==0&&d[1]==0&&d[2]==0)printf("YES\n"); else printf("NO\n"); }
B: Bets
競技参加している時間帯、ラップタイム、賞金が沢山の競技者についていて、最大でどのくらいのお金がもらえるか(謎)
範囲狭いし時間でループが回せる。書くだけ。
#include<stdio.h> int l[100]; int r[100]; int t[100]; int c[100]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<b;i++){ scanf("%d%d%d%d",l+i,r+i,t+i,c+i); } int ret=0; for(int i=1;i<=a;i++){ int at=0; bool ok=false; int min=9999999; for(int j=0;j<b;j++){ if(l[j]<=i&&i<=r[j]&&min>t[j]){ at=j; ok=true; min=t[j]; } } if(ok)ret+=c[at]; } printf("%d\n",ret); }
C: Game
文字列系実装問題? 問題文が理解できないけど、もし考えられるパターンが複数個あったらどうするんだろう…
適当にJavaで提出してみたがpretestで-2されるだけされておわった。
D: Dot
普通に難しいと思う。ビットDPとかかなぁ。
E: Subsegments
どう見ても座標圧縮+SegmentTree安定でした。mapとsetやらpriority_queueやらを使っている人が多かったように見える。
#include<stdio.h> #include<algorithm> using namespace std; int t[100000]; int k[100000]; int zahyou[100000]; int co[100000]; int SEGTREE[262144]; void query(int at,int val){ if(val==1)SEGTREE[at+131072]=at; else SEGTREE[at+131072]=-1; at+=131072; at/=2; while(at>0){ SEGTREE[at]=max(SEGTREE[2*at],SEGTREE[2*at+1]); at/=2; } return; } int find(int begin,int end,int a,int b,int t){ if(begin<=a&&b<=end)return SEGTREE[t]; else if(begin>b||end<a)return -1; else return max(find(begin,end,a,(a+b)/2,t*2),find(begin,end,(a+b)/2+1,b,t*2+1)); } int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ scanf("%d",t+i); k[i]=t[i]; } std::sort(k,k+a); for(int i=0;i<262144;i++)SEGTREE[i]=-1; for(int i=0;i<a;i++){ zahyou[i]=lower_bound(k,k+a,t[i])-k; } for(int i=0;i<b;i++){ co[zahyou[i]]++; } for(int i=0;i<b;i++){ if(co[zahyou[i]]==1){ query(zahyou[i],1); } } if(SEGTREE[1]!=-1) printf("%d\n",k[SEGTREE[1]]); else printf("Nothing\n"); for(int i=1;i<a-b+1;i++){ co[zahyou[i-1]]--; co[zahyou[i+b-1]]++; if(co[zahyou[i-1]]==1)query(zahyou[i-1],1); else query(zahyou[i-1],-1); if(co[zahyou[i+b-1]]==1)query(zahyou[i+b-1],1); else query(zahyou[i+b-1],-1); //for(int j=131072;j<131072+a;j++)printf("%d ",SEGTREE[j]); if(SEGTREE[1]!=-1) printf("%d\n",k[SEGTREE[1]]); else printf("Nothing\n"); } }
Hack:
面白そうだしCとD書けないしHackでもして遊んでみよう。
とりあえずA,B,Eの全員のソースを眺めてみる。
Aで最後の判定を三つの要素の合計が0とか三つの要素がすべて等しいと判定してる人が沢山! -> +3
他は落とせなさそう。 ->誰かが落としていました
SystemTest:
通った
496 + 956 + 0 + 0 + 2040 + 300 = 3792 (37th)
No rated -> 1760 (+260)
初参加の割りには良かったように思えます。最近のTopCoderと比較すれば。
Div2Onlyじゃない回はどのくらい解けばレート上がるんでしょう。