ICPC2017 国内予選 参加記
気がついたら年齢的にもICPCの参加リミットを超えてしまった。年を重ねるにつれ、目標を達成してしまうし、目標になるものも減ってきてしまうのが、競技プログラミング(に限らないけど)の難しいところ。
その昔、こんな目標を持っていた。
- IOIに参加してメダルを取る
- ICPCに参加してメダルを取る
- 海外オンサイトに参加する
もちろんIOIは2012年の時にまあなんとかして代表になって銀メダルを取ったし、ICPCですら2014年の時に運もあって銀メダルを取ったし、この二つは年齢的にも引退なのでもう仕方がない。海外オンサイトはいつまでも出られるので、これは目標にできるか?と思いきや、FHC2015、DCJ2016ときてまたDCJ2017でも進出し、やはり数回出場すると目標としていまいちインパクトに欠けて、やる気が出ない。これだけのために必死に問題解き続けられるかと言われるとそんなことはないと思う。
じゃあここまでくると目標というのはどういうものが考えられるかと言うと、
- TopCoder target
- Codeforces LGM
- AtCoder 3200
- 海外オンサイトで入賞
とかなんだけども、TopCoderは廃れて目も当てられないし、Codeforcesはゴミみたいなセットが増えすぎでいちいちやる気を削いでくるし、AtCoderは過去問練習で上位に来た無能を真っ向から潰しにかかってくるセットばっかりだし、海外オンサイトで入賞は有名人たちの争いだし、なんか以前の目標に比べて遠すぎる。
もっと現実的かつ練習が要求されて見返りも結構ある目標が立てられるといいんだけどもなあ。赤中上位だけどtargetには届かない、そんな人たちを集めてリーグ戦とかやって欲しい。chokudaiさんお願いします。
関係ないけどOpenCupのおかげで今もチーム戦に参加できるのは嬉しい。制限なしのチーム戦の真面目なコンテストとか出てきてくれないかなとも思ってる(ロシアにはあるよね)。
純粋培養競技プログラマが基本情報技術者試験を解いてみた話
参考:
d.hatena.ne.jp
こんにちは。たまには有機的な投稿をします、tozangezanです。
twitterで基本情報技術者試験、というものが話題に上がっていたので、過去問を解いてみることにしました。
筆者紹介
大学4年。中学2年のときに競技プログラミングを始める。インターンに行ったことがある。競技プログラミング以外の用途でもプログラムを書く(研究でシミュレーションをするため)。
パソコンの中のことやネットワークのことについて勉強したことはなし。離散最適化に興味なし。
DEGwerと違い、理学も工学も専攻していません(ポイント)
使用した問題
http://www.fe-siken.com/kakomon/29_haru/
ここに上がっている、平成29年度春の午前試験を解きました。
結果
46問正解/80問 です。ボーダーが6割らしいので、ぎりぎり不合格です。
感想
アルゴリズムの問題が1桁問しかない!
全般的に知らない語彙が多すぎます。具体的にはパソコン系単語とビジネス系単語だと思います。DEGwerも言っていましたが、まだ英語をカタカナにしたものは意味が想像つくので(たとえばニッチャとか生まれて初めて見た4文字ですが、nicheに-erをつけただけだと思うし、nicheという単語は生態学を専攻している人が知らないわけがありません)、まだなんとかなります。問題は、技術に関する知識が文字どおり0(特にネットワーク関係は、「パソコンの右上か左上に扇のようなマークがあり、これを押すとネットにつながる」くらいの知識しかないので、どうすることもできません)なので、問題文から推測しようがありません。
特にDMZにネットワークを置く問題とか、なんで韓国と北朝鮮の国境地帯にサーバー(あのディスクが3枚つながったやつです)を置くのかしか頭に残りません。
ビジネス関連単語も、発音はできるが全く意味がわからない日本語で構成されており、正気を疑います。
採点してみる。なんか最初の方間違えまくってるやんけ! → どれもこれも単語の説明問題でした(完)
面白かった問題
問30. 唯一解きがい(手の動かしがい?)がありました。
問69. ここまでくると、経済学の問題じゃないですかね。
結論
一般常識 + 最低限の英語力 + 競プロ風味の算数 では通らないこともあります。多分わからない問題の乱択の結果のブレが、合否を分けるラインです。
じゃあ競技プログラミングは基本情報技術者試験の役に立たない? そんなことはないと思います(わずかだとは思いますが)。そんなことで一番伝えたいのは、
情報系専攻は基本情報の役に立つ。
回答
間違えた問題の回答には、・がついています。
え
- う
い
あ
あ
い
う
え
- い
え
- い
- う
- あ
う
- う
- い
え
あ
- う
あ
う
あ
あ
い
- あ
- い
- う
- う
う
う
- え
い
- い
- あ
- い
- う
い
あ
- あ
- え
う
- い
う
え
あ
- い
- え
え
- え
- え
- い
- い
え
- い
- え
う
- あ
う
い
あ
- う
う
- う
え
- う
い
- い
う
い
- あ
い
う
い
え
う
い
い
う
え
う
四国フォトギャラリー
2017年2月に四国に行きました。そのとき撮った写真のうち、見せたいものをただひたすら張り続けます。
番号が汚い
ラスボスがいそう
高松からは離島行きフェリーがたくさんある
セルフの醍醐味
さぬきうどん駅
徳島。駅の隣に山がある
サラダ
阿波池田。寂しすぎる
大歩危峡
ゆるして
日本一駅間が短い
大都会予土線
半家 はげ
四国一箇所巡り
願い事
ごはん
おまけ
B: flagpoles
差を取ると本当に簡単。
long long p[11000000]; long long lf[210]; long long lv[210]; long long rf[210]; long long rv[210]; long long sv[210]; int main(){ int T=NumberOfNodes(); int I=MyNodeId(); int N=GetNumFlagpoles(); if(N<=2){ if(I==0){ printf("%d\n",N); } return 0; } N--; if(N<T){ T=N; if(I>=T)return 0; } int L=(long long)N*I/T; int R=(long long)N*(I+1)/T; int n=R-L; long long now=GetHeight(L); for(int i=0;i<n;i++){ long long tmp=GetHeight(i+1+L); p[i]=tmp-now; now=tmp; } long long left=0; long long right=0; for(int i=0;i<n;i++){ if(p[i]==p[0])left++; else break; } for(int i=0;i<n;i++){ if(p[n-1-i]==p[n-1])right++; else break; } long long ma=0; long long val=0; for(int i=0;i<n;i++){ if(i==0||p[i]==p[i-1]){ val++; }else{ val=1; } ma=max(ma,val); } if(I==0){ lf[0]=p[0]; lv[0]=left; rf[0]=p[n-1]; rv[0]=right; sv[0]=ma; for(int i=1;i<T;i++){ Receive(i); lv[i]=GetLL(i); lf[i]=GetLL(i); rv[i]=GetLL(i); rf[i]=GetLL(i); sv[i]=GetLL(i); } long long ret=0; long long nc=0; long long nl=0; for(int i=0;i<T;i++){ ret=max(ret,sv[i]); if(nc==lf[i]){ ret=max(ret,nl+lv[i]); }else{ nl=0; nc=rf[i]; } long long TL=(long long)N*i/T; long long TR=(long long)N*(i+1)/T; if(TR-TL==lv[i]){ nl+=lv[i]; }else{ nl=rv[i]; nc=rf[i]; } ret=max(ret,nl); } printf("%lld\n",ret+1); }else{ PutLL(0,left); PutLL(0,p[0]); PutLL(0,right); PutLL(0,p[n-1]); PutLL(0,ma); Send(0); } }
C: number_bases
事前にくり上がりがある場合ない場合どっちも用意しておく。
int X[1100000]; int Y[1100000]; int Z[1100000]; int LL[210][2]; int RR[210][2]; int DD[210][2]; int KK[210][2]; int main(){ int T=NumberOfNodes(); int I=MyNodeId(); int N=GetLength(); if(N<T){ T=N; if(I>=T)return 0; } int L=(long long)N*I/T; int R=(long long)N*(I+1)/T; int n=R-L; for(int i=0;i<n;i++){ X[i]=GetDigitX(i+L); Y[i]=GetDigitY(i+L); Z[i]=GetDigitZ(i+L); } int DL=0; int DR=-1; int dame=0; int KR=0; for(int i=0;i<n;i++){ DL=max(max(DL,Z[i]+1),max(X[i]+1,Y[i]+1)); if(KR+X[i]+Y[i]>Z[i]){ int nr=KR+X[i]+Y[i]-Z[i]; if(DR==-1||DR==nr){ DR=nr; }else{ dame=1; } KR=1; }else if(KR+X[i]+Y[i]==Z[i]){ KR=0; }else{ dame=1; } } if(DR!=-1&&DR<DL)dame=1; LL[I][0]=DL; RR[I][0]=DR; DD[I][0]=dame; KK[I][0]=KR; DL=0; DR=-1; dame=0; KR=1; for(int i=0;i<n;i++){ DL=max(max(DL,Z[i]+1),max(X[i]+1,Y[i]+1)); if(KR+X[i]+Y[i]>Z[i]){ int nr=KR+X[i]+Y[i]-Z[i]; if(DR==-1||DR==nr){ DR=nr; }else{ dame=1; } KR=1; }else if(KR+X[i]+Y[i]==Z[i]){ KR=0; }else{ dame=1; } } if(DR!=-1&&DR<DL)dame=1; LL[I][1]=DL; RR[I][1]=DR; DD[I][1]=dame; KK[I][1]=KR; if(I==0){ // printf("%d: %d %d %d %d\n",0,LL[I][0],RR[I][0],DD[I][0],KK[I][0]); //printf("%d: %d %d %d %d\n",1,LL[I][1],RR[I][1],DD[I][1],KK[I][1]); // fflush(stdout); for(int i=1;i<T;i++){ Receive(i); for(int j=0;j<2;j++){ LL[i][j]=GetInt(i); RR[i][j]=GetInt(i); DD[i][j]=GetInt(i); KK[i][j]=GetInt(i); } } bool ok=true; int dl=0; int dr=-1; int kr=0; for(int i=0;i<T;i++){ if(DD[i][kr]){ ok=false;break; } dl=max(dl,LL[i][kr]); if(dr!=-1&&dr!=RR[i][kr]&&RR[i][kr]!=-1){ ok=false; }else if(RR[i][kr]!=-1)dr=RR[i][kr]; kr=KK[i][kr]; } if(kr)ok=false; if(dr!=-1&&dl>dr)ok=false; if(!ok){ printf("IMPOSSIBLE\n"); }else{ if(dr==-1)printf("NON-UNIQUE\n"); else printf("%d\n",dr); } }else{ for(int i=0;i<2;i++){ // printf("%d: %d %d %d %d\n",i,LL[I][i],RR[I][i],DD[I][i],KK[I][i]); //fflush(stdout); PutInt(0,LL[I][i]); PutInt(0,RR[I][i]); PutInt(0,DD[I][i]); PutInt(0,KK[I][i]); } Send(0); } }
D: broken_memory
落ちた。不必要にデータを送りすぎた。(700回ですむところを調子に乗って送りまくってしまった)
E: nanobots
smallは分割統治であることは有名。largeはたくさんスライスしてランダムに割り振ってsmallと同じことをする。
const long long mod=1000000007; long long ret=0; void count(long long L,long long R,long long lm,long long rm){ if(L>=R)return; if(lm>rm)return; // printf("%lld %lld %lld %lld\n",L,R,lm,rm); if(Experiment(R-1,rm)=='T'){ ret=(ret+((R-L)%mod)*((rm)%mod))%mod; // printf("%lld %lld\n",R-1,rm); return; } if(Experiment(L,lm)=='E')return; long long M=(L+R)/2; long long left=lm-1; long long right=rm+1; while(left+1<right){ long long mid=(left+right)/2; if(Experiment(M,mid)=='T'){ left=mid; }else right=mid; } ret=(ret+left)%mod; //ret=(ret+(M-L)%mod*((left-lm+1)%mod))%mod; count(L,M,max(1LL,left),rm); count(M+1,R,lm,left); } int main(){ int T=NumberOfNodes(); int I=MyNodeId(); int N=GetNumNanobots(); long long R=GetRange(); int BK=min((long long)R,2000000LL); //count(1,R+1,1,R); srand(1145141919); for(int i=0;i<BK;i++){ int tmp=rand(); long long left=R*i/BK+1; long long right=R*(i+1)/BK+1; if(tmp%T==I){ count(left,right,1,R); } } if(I==0){ for(int i=1;i<T;i++){ Receive(i); long long tmp=GetLL(i); ret=(ret+tmp)%mod; } printf("%lld\n",ret); }else{ PutLL(0,ret); Send(0); } }
21位。なんで通ったんだろう。アイルランドでも頑張ります。
英単語の覚え方
7000語くらい知ってる人(大学受験でそんなに苦労しないレベル)が15000~20000語くらい知ってる人になるための方法です。
自分の体験にしか基づいていないので、これが多くの人に適用可能かとかそういうことは一切考えてないのであしからず。
文脈で覚えるべきなのか単語リストとして覚えるべきなのか?英英で覚えるべきなのか英和で覚えるべきなのか?etc
以下、僕がやったことは単語リストで覚えて、多読で実際に触れることで実際の使用例を後から文脈で知るという方法をとりました。最初から文脈で覚えようとすると異常なほどに労力が必要でペースが落ちるので、非効率だと思います。特に高校生レベルの単語ならまだしも、それ以上になってくるとものすごい多義語とかは減ってくるわけで、和訳を見ただけでもう文脈も限られてくるようなものばかりです。(たとえば、sonnet (イタリアの14行詩) のような単語が、文脈で覚えないと情報量が落ちるかといわれると、そんなことはないと思います)。ただし、具体的なものの名称で、単語の説明だけ見ても想像が困難なものがあり、これは Google 画像検索によってイメージで覚えることが得策なこともあります。(僕が想像に苦労したのは、西洋の城に関する単語です。例えば portcullis という単語は「落とし格子」という意味ですが、城といえばまず鶴ヶ城を思い浮かべるような人には想像が難しいでしょう?)
英英で覚えるべきか英和で覚えるべきかに関しては、どちらも一長一短あるので好きなほうを選べばいいと思います。個人的には英和が(多くの場合)ストレスがないのでおすすめです。英和の良い点は、「パッと見で分かるので、単語を回すスピードが上がる」「訳語の意味を勘違いしていたせいで間違って覚える心配が少なめ(無いという事ではありません)」、英英の良い点は「説明が豊富でより的確」「GREレベルですら英和辞典に載ってない単語が意外とあるが、英英には必ず載ってる」ということでしょうか。
もう一つは媒体ですが、僕は紙で覚えようと思ったことはありません。格安で数千枚の単語カードが買えるなら考えなくもないのですが、本だと順番が固定されていたりする点、自分でカードを準備するには大変過ぎる点がネックでした。また、音声も付加して覚えるというのはすごく良いアイデアだと思います。しかし、これは自力で辞書と単語リストだけから環境を構築する場合はほぼ無理です。
覚えて思ったこと等
語幹を使って覚えるというのは、ある程度助けになります。例えば、mal-は悪いことですし、dys-は何かが壊れていたり失っていたりするものですし、arbo-は樹木に関しています。しかし、in-が特に厄介です。
単語と訳語の対応だけを覚えていると、実際に使えないというのは広く言われています。これは正しいです。例えば、infiltrate にはどのようなときにin/throughが付くのかとかは、infiltrateの意味が分かっていても全く知りません。
ただし、そのような難しい単語で、専門的な名詞や形容詞というわけでもないものを、作家でもないノンネイティブが使うときが来るのでしょうか?特にノンネイティブが使う複雑な動詞というのは、科学的な論文に登場しがちな単語だけな気がします。
厄介な外来語
mikanのGRE/TOEFLを終えて新しい単語リストを始めたとき、フランス語の単語を勉強しているような錯覚に囚われるほど、外来語が大量に登場しました。外来語は発音が意味不明で、複数形が意味不明で、語幹が全く通用しないものが多く、さらに意味がやけにマイナーなことが多いので、単語リストのため、試験のためだけに勉強しているような気分になります。特に感情が消えるフランス語由来の単語を並べてみます。発音してみましょう。
- malapropos
- maladroit
- verdigris
- cliche
- raconteur
- patois
実際、何をやったか
で、実際僕がやったことをまとめていきます。
- mikan に出会う。mikan は本当に良いアプリです。ただし、ある程度覚えてからが本当に不便です。あと、四択クイズはいらないですね。やったことは、「とりあえず出来る限り早く全レベルを解禁し、学習済みにする」→「『全ての単語』モードからランダムを選び、150個カードをめくる」→「分からなかった単語が未学習に戻るが、それを全部学習済みに埋めなおす」を毎日やることです。3ヶ月くらいでGREを全部やり、次の3ヵ月くらいでTOEFLを全部やりました。これだけでもかなり十分だと思います。具体的には、Eragonシリーズはそこまで辞書に頼る必要がなくなります。
- mikan の GRE/TOEFL 単語を9割以上覚えてしまったことと、覚えた単語が多いときの効率の悪さに不満を感じたので、自分でプログラムを作って今までmikanで毎日やってきたことがより効率的に出来るものを作りました。これが #1日150Shokubutsuランダム でおなじみのShokubutsuです。単語リストはネット上にあった難しめ(なかなか難しい!)のものを使いました。これが割りとできるようになるとEragonシリーズは10ページに1回くらいしか辞書を引かなくてよくなります。
- やめたことは、Ankiに12000語レベルのものを大量にぶち込んでやったことです。これは単語リストの質が悪かった。(本当にどうでも良い単語ばかりな上和訳が変なのばっかりでした)
- これ以降やるべきことは、小説や新聞で実際に出会った単語を覚えることと、気が向いた単語をthesaurusで引いて眺めることだと思いました。しかし、小説を読んで知らない単語に線を引くと、高確率でスラングなのが気がかりです。
おまけ
almost_sorted
区間をK伸ばしてソートするだけです。
#include<stdio.h> #include<algorithm> #include<message.h> #include"almost_sorted.h" using namespace std; long long p[3100000]; const int mod=1<<20; int main(){ int T=NumberOfNodes(); int I=MyNodeId(); int N=NumberOfFiles(); int K=MaxDistance(); int L=(long long)N*I/T; int R=(long long)N*(I+1)/T; int ans=0; if(L==R){ ans=0; }else{ int left=max(0,L-K); int right=min(N,R+K); for(int i=left;i<right;i++){ p[i-left]=Identifier(i); } std::sort(p,p+right-left); for(int i=L;i<R;i++){ long long t=p[i-left]%mod*i%mod; ans=(ans+t)%mod; } } if(I==0){ for(int i=1;i<T;i++){ Receive(i); ans=(ans+GetInt(i))%mod; } printf("%d\n",ans); }else{ PutInt(0,ans); Send(0); } }
shhhh
中継点をランダムに決めることが本質です。ハッシュの計算を間違えました。
#include<stdio.h> #include<algorithm> #include<message.h> #include<set> #include<cassert> #include"shhhh.h" using namespace std; int key[120]; int ha[110000]; int p[120]; int q[120]; int main(){ int T=NumberOfNodes(); int I=MyNodeId(); int N=GetN(); if(N<1000){ if(I!=0)return 0; int ret=0; int at=0; while(1){ int to=GetRightNeighbour(at); ret++; if(to==1)break; at=to; } int R=ret; int L=N-ret; if(L<R)printf("LEFT %d\n",L); else if(L>R)printf("RIGHT %d\n",R); else printf("WHATEVER %d\n",L); return 0; } srand(114514810); set<int>S; S.insert(0); S.insert(1); for(int i=0;i<100000;i++)ha[i]=-1; ha[0]=0; ha[1]=T; for(int i=1;i<T;i++){ while(1){ key[i]=rand()%N; if(!S.count(key[i]%100000)){ ha[key[i]%100000]=i; S.insert(key[i]%100000);break; } } } //printf("%d: %d\n",I,key[I]); //fflush(stdout); int at=key[I]; int dist=0; int nx=0; while(1){ int to=GetRightNeighbour(at); //printf("%d: %d %d\n",I,at,to); //fflush(stdout); dist++; if(~ha[to%100000]&&(to==1||to==key[ha[to%100000]])){ nx=ha[to%100000]; break; } at=to; } // printf("%d: %d %d %d\n",I,key[I],nx,dist); //fflush(stdout); if(I==0){ p[0]=nx; q[0]=dist; for(int i=1;i<T;i++){ Receive(i); p[i]=GetInt(i); q[i]=GetInt(i); } int R=0; int L=0; int now=0; int cnt=0; while(1){ int to=p[now]; R+=q[now]; cnt++; if(to==T){ break; } now=to; if(cnt>T){ assert(false); } } L=N-R; if(L<R)printf("LEFT %d\n",L); else if(L>R)printf("RIGHT %d\n",R); else printf("WHATEVER %d\n",L); }else{ PutInt(0,nx); PutInt(0,dist); Send(0); } }
load_balance
半分全列挙をどのスレッドでもやるのですが、条件を満たした結果(modとかで振り分ける)のみを各スレッドで考慮することにすると、log分もなんとかなります。
ただしこの解法はあんまり良くないようで、TLEぎりぎりです。(26個1があると26C13個の13を持つことになってそこがネック)
#include<stdio.h> #include<algorithm> #include<message.h> #include"load_balance.h" using namespace std; long long p[60]; int m[110]; const int mod=53461; int bt[60000]; int L,R; int I; int ls; int rs; long long left[11000000]; long long right[11000000]; void dfs(int a,int b,int c,long long d){ if(a==b){ if(bt[c%mod]==I){ if(b==L)left[ls++]=d; else right[rs++]=d; } return; } dfs(a+1,b,(c+p[a])%mod,d+p[a]); dfs(a+1,b,(c+mod-p[a]%mod)%mod,d-p[a]); } int main(){ int T=NumberOfNodes(); I=MyNodeId(); int N=GetN(); for(int i=0;i<N;i++)p[i]=GetWeight(i); srand(114514810); for(int i=0;i<mod;i++){ bt[i]=rand()%T; } L=N/2; R=N-L; dfs(0,L,0,0LL); dfs(L,N,0,0LL); // std::sort(left,left+ls); std::sort(right,right+rs); int ok=0; for(int i=0;i<ls;i++){ if(binary_search(right,right+rs,left[i]))ok=1; } if(I==0){ bool ret=false; if(ok==1)ret=true; for(int i=1;i<T;i++){ Receive(i); int tmp=GetInt(i); if(tmp==1)ret=true; } if(ret)printf("POSSIBLE\n"); else printf("IMPOSSIBLE\n"); }else{ PutInt(0,ok); Send(0); } }
kolakoski
最初に配列の種みたいなのを割り振っておき、順々に種から次の世代を発生させていきます。
発生のさせ方ですが、最初に長さと1/2が切り替わる回数がわかるので、それらを求め親ノードにこれを転送します。親ノードは子ノードの左から順にこれらを使うことで、その子ノードで1/2どちらから始まるか、オフセットがどこかというのを渡すことができるようになります。
デバッグがしにくいです。スレッド数を下げる(3とか)のがおすすめです。
#include<stdio.h> #include<algorithm> #include<message.h> #include"kolakoski.h" using namespace std; char a[2000]; long long N; int Get(long long i){ if(i>=N)return 0; return GetMultiplier(i); } char p[2][41000000]; long long X[110]; long long Y[110]; int main(){ int T=NumberOfNodes(); int I=MyNodeId(); N=GetIndex(); a[0]=1; a[1]=a[2]=2; int left=2; int right=3; while(right-left<T){ if(a[left]==1){ a[right++]=left%2+1; }else{ a[right++]=left%2+1;a[right++]=left%2+1; } left++; } //if(I==0){for(int i=0;i<right;i++)printf("%d",a[i]);printf("\n");} if(I==T-1){ long long ret=0; for(int i=0;i<right;i++){ ret+=Get(i)*a[i]; // printf("%d",a[i]); } // printf("\n");fflush(stdout); long long now=left; long long at=right; while(1){ for(int i=0;i<T-1;i++){ Receive(i); X[i]=GetLL(i); Y[i]=GetLL(i); } for(int i=0;i<T-1;i++){ PutLL(i,now%2); PutLL(i,at); Send(i); now+=X[i]; at+=Y[i]; } bool end=false; for(int i=0;i<T-1;i++){ Receive(i); long long tmp=GetLL(i); long long cnt=GetLL(i); ret+=tmp; if(cnt){ end=true; } } if(end)break; } for(int i=0;i<T-1;i++){ Receive(i); X[i]=GetLL(i); Y[i]=GetLL(i); } for(int i=0;i<T-1;i++){ PutLL(i,-1); PutLL(i,-1); Send(i); } printf("%lld\n",ret); }else{ int m=right-left; int L=m*I/(T-1)+left; int R=m*(I+1)/(T-1)+left; for(int i=L;i<R;i++){ p[0][i-L]=a[i]; } int ptr=0; int n=R-L; while(1){ long long r1=0; for(int i=0;i<n;i++)r1+=p[ptr][i]; PutLL(T-1,n); PutLL(T-1,r1); Send(T-1); Receive(T-1); int sc=GetLL(T-1); long long off=GetLL(T-1); if(sc<0)break; int nn=0; for(int i=0;i<n;i++){ for(int j=0;j<p[ptr][i];j++){ p[!ptr][nn++]=(sc+i)%2+1; } } long long res=0; long long end=0; // printf("%d: ",off); for(int i=0;i<nn;i++){ if(off+i>=N){end=1;break;} res+=Get(off+i)*p[!ptr][i]; // printf("%d",p[!ptr][i]); } // printf("\n");fflush(stdout); PutLL(T-1,res); PutLL(T-1,end); Send(T-1); ptr=!ptr; n=nn; } } }
DCJは、残り解法が分かってないのが4問あります。解法だけは読んでおこうかと思っています。
Wolf Sotheとは?
決して暇ではないし、なんか節目の時期であるわけでもなく、Advent Calendarシーズンですらないのに、唐突に変な記事を書きます。
Wolf Sotheとは?
昔のITMO Universityのアイスホッケーチームのユニフォーム。Edmonton Oilersと同じカラーリング。
このブログをわざわざ見ている人にはご存知かもしれませんが、Wolf Sotheというのは(特に僕がwriterをしているときによく登場する)プログラミングコンテストのキャラクターです。
例えば、以下のようなところに出没しています。
CODE FESTIVAL 2015 OKINAWA OPEN - CODE FESTIVAL 2015 OKINAWA OPEN | AtCoder
TopCoder Statistics - Match Overview SRM637 (non-tozangezanなWolf Sothe)
TopCoder Statistics - Problem Statement SRM690
本名は Tozan Southerpacks です。(pack: 狼の群れ) *1 現にプログラミングコンテスト上以外の彼(自分?)は、ほとんどTozanと呼ばれています。
いろいろあって彼はアイスホッケーが好きなんだそうです。
ちなみに、よくコンテストに持っていく狼のスモールマスコットはco-Sotheと言います。参考
おまけ
DCJが近いので本番で通せなかった問題を解いて振り返ったのでメモをば。
rps
これはまあ。使うノードの数を2のべきにする。ノードを使いすぎない。
#include<stdio.h> #include<algorithm> #include<message.h> #include"rps.h" using namespace std; /* USER'S GUIDE Num of data / node: 1000 Amount of data / node: 8MB HOW TO USE TOO COMPLICATED AND TOO DIFFICULT LIBRARIES python dcj/dcj.py test --source QUESTIONNAME.cpp --nodes NUMBER_OF_NODES FUNCTION LIBRARIES : int NumberOfNodes(); int MyNodeId(); void PutChar(int target, char value); void PutInt(int target, int value); void PutLL(int target, long long value); void Send(int target); : call this after using Put*** int Receive(int source); call this before using Get*** (return value: number of sended values) char GetChar(int source); int GetInt(int source); long long GetLL(int source); */ char ch[4200000]; long long ind[4200000]; int main(){ int T=NumberOfNodes(); int I=MyNodeId(); int N=GetN(); long long a=1LL<<N; int use=1; while(use*2<T&&use<a){ use*=2; } if(I==T-1){ for(int i=0;i<use;i++){ Receive(i); ch[i]=GetChar(i); ind[i]=GetLL(i); } int n=use; while(n>1){ int at=0; for(int i=0;i<n;i+=2){ if((ch[i]=='R'&&ch[i+1]=='P')||(ch[i]=='S'&&ch[i+1]=='R')||(ch[i]=='P'&&ch[i+1]=='S')){ ch[at]=ch[i+1]; ind[at]=ind[i+1]; }else{ ch[at]=ch[i]; ind[at]=ind[i]; } at++; } n/=2; } printf("%lld\n",ind[0]); }else if(I<use){ long long L=a/use*I; long long R=a/use*(I+1); for(long long i=L;i<R;i++){ ch[i-L]=GetFavoriteMove(i); ind[i-L]=i; } int n=R-L; while(n>1){ int at=0; for(int i=0;i<n;i+=2){ if((ch[i]=='R'&&ch[i+1]=='P')||(ch[i]=='S'&&ch[i+1]=='R')||(ch[i]=='P'&&ch[i+1]=='S')){ ch[at]=ch[i+1]; ind[at]=ind[i+1]; }else{ ch[at]=ch[i]; ind[at]=ind[i]; } at++; } n/=2; } PutChar(T-1,ch[0]); PutLL(T-1,ind[0]); Send(T-1); } }
necklace
2015finalの簡単枠。
substringのほうの文字列は短いことが大事。あとはここ1年で嫌という程見た「区間の左をiでスタートしたらどこまでいけるのか」をちまちま求めていく。
#include<stdio.h> #include<algorithm> #include<message.h> #include"necklace.h" using namespace std; /* USER'S GUIDE Num of data / node: 1000 Amount of data / node: 8MB HOW TO USE TOO COMPLICATED AND TOO DIFFICULT LIBRARIES python dcj/dcj.py test --source QUESTIONNAME.cpp --nodes NUMBER_OF_NODES FUNCTION LIBRARIES : int NumberOfNodes(); int MyNodeId(); void PutChar(int target, char value); void PutInt(int target, int value); void PutLL(int target, long long value); void Send(int target); : call this after using Put*** int Receive(int source); call this before using Get*** (return value: number of sended values) char GetChar(int source); int GetInt(int source); long long GetLL(int source); */ int str[10100000]; int in[3100]; int g[110][3100]; int sz[10100]; int q[10100][3010]; int to[3100]; int main(){ int T=NumberOfNodes(); int I=MyNodeId(); int N=GetNecklaceLength(); int M=GetMessageLength(); int L=(long long)N*I/T; int R=(long long)N*(I+1)/T; for(int i=L;i<R;i++)str[i-L]=GetNecklaceElement(i); for(int i=0;i<M;i++)in[i]=GetMessageElement(i); for(int i=0;i<=M;i++){ to[i]=i; if(i<M)q[in[i]][sz[in[i]]++]=i; } int n=R-L; for(int i=0;i<n;i++){ int t=str[i]; int ke=sz[t]; for(int j=0;j<ke;j++){ to[q[t][j]]++; } sz[t]=0; for(int j=0;j<ke;j++){ if(to[q[t][j]]>=M)continue; q[in[to[q[t][j]]]][sz[in[to[q[t][j]]]]++]=q[t][j]; } } if(I==0){ for(int i=0;i<=M;i++)g[0][i]=to[i]; for(int i=1;i<T;i++){ Receive(i); for(int j=0;j<=M;j++)g[i][j]=GetInt(i); } int ret=0; for(int i=0;i<M;i++){ int now=i; for(int j=0;j<T;j++){ now=g[j][now]; } ret=max(ret,now-i); } printf("%d\n",ret); }else{ for(int i=0;i<=M;i++)PutInt(0,to[i]); Send(0); } }
johnny
考察のほうが大事で、distribution要素はほぼない。
出次数が小さい順にソートして、左端から到達できる範囲の右端がどこかを探す。到達できない頂点がjohnnyの手札。
実は、転送するデータ量が結構厳しめ。一つ前のノードから受け取って一つ後のノードに転送すると、ノードあたりの通信量は抑えられるが、これは時間がかかるのでTLEする。
結局押し込むのが正解。charはsignedなので気をつける。
#include<stdio.h> #include<algorithm> #include<message.h> #include"johnny.h" using namespace std; /* USER'S GUIDE Num of data / node: 1000 Amount of data / node: 8MB HOW TO USE TOO COMPLICATED AND TOO DIFFICULT LIBRARIES python dcj/dcj.py test --source QUESTIONNAME.cpp --nodes NUMBER_OF_NODES FUNCTION LIBRARIES : int NumberOfNodes(); int MyNodeId(); void PutChar(int target, char value); void PutInt(int target, int value); void PutLL(int target, long long value); void Send(int target); : call this after using Put*** int Receive(int source); call this before using Get*** (return value: number of sended values) char GetChar(int source); int GetInt(int source); long long GetLL(int source); */ int out[21000]; pair<int,int> p[21000]; int at[21000]; int rev[21000]; int lm[21000]; bool is[210][21000]; int main(){ int T=NumberOfNodes(); int I=MyNodeId(); int N=NumberOfCards(); int L=N*I/T; int R=N*(I+1)/T; for(int i=L;i<R;i++){ for(int j=0;j<N;j++){ if(IsBetter(i,j)){ out[i]++; is[i-L][j]=true; } } } if(I==0){ for(int i=1;i<T;i++){ int left=N*i/T; int right=N*(i+1)/T; Receive(i); for(int j=left;j<right;j++)out[j]=GetInt(i); } for(int i=0;i<N;i++)p[i]=make_pair(out[i],i); std::sort(p,p+N); for(int j=1;j<T;j++){ for(int i=0;i<N;i++){ PutChar(j,p[i].second/256); PutChar(j,p[i].second%256); at[i]=p[i].second; } Send(j); } }else{ for(int i=L;i<R;i++)PutInt(0,out[i]); Send(0); Receive(0); for(int i=0;i<N;i++){ at[i]=GetChar(0); if(at[i]<0)at[i]+=256; at[i]*=256; int tt=GetChar(0); if(tt<0)tt+=256; at[i]+=tt; } } for(int i=0;i<N;i++)lm[i]=rev[i]; for(int i=0;i<N;i++)rev[at[i]]=i; for(int i=L;i<R;i++){ for(int j=0;j<N;j++){ if(is[i-L][j]){ lm[i]=max(lm[i],rev[j]); } } } if(I==0){ for(int i=1;i<T;i++){ int left=N*i/T; int right=N*(i+1)/T; Receive(i); for(int j=left;j<right;j++)lm[j]=GetInt(i); } int tmp=0; for(int i=0;i<N;i++){ if(tmp<i)break; tmp=max(tmp,lm[p[i].second]); } if(tmp==N-1)printf("IMPOSSIBLE\n"); else printf("%d\n",N-tmp-1); }else{ for(int i=L;i<R;i++)PutInt(0,lm[i]); Send(0); } }
gold
2016final、2番目に簡単とはいえ、これが解ければ入賞できる。
基本アイデアは「範囲[L,R]が与えられた時、その中に金が埋まってるかを判定し、埋まってるならどこか一つの場所を返す」のをlogで求める方針。
両端の文字で場合分けすると2段階の処理で済むことになる。
特定の場所に偏りすぎだとあるノードで探す金の個数が多すぎるが、これはある程度多い時は諦め、再度親ノードに戻ってきて多かった場所をさらに分割してやり直せばよい。
打ち切りは何回くらいがいいのか多分真面目にやったら解析できるが、practiceにはlargeにフィードバックがあるのでサボった。
#include<stdio.h> #include<algorithm> #include<queue> #include<message.h> #include"gold.h" using namespace std; /* USER'S GUIDE Num of data / node: 1000 Amount of data / node: 8MB Send, Receive / 5 ~ 10ms? Linear Message passing: slow (500ms through every nodes) HOW TO USE TOO COMPLICATED AND TOO DIFFICULT LIBRARIES python dcj/dcj.py test --source QUESTIONNAME.cpp --nodes NUMBER_OF_NODES FUNCTION LIBRARIES : int NumberOfNodes(); int MyNodeId(); void PutChar(int target, char value); void PutInt(int target, int value); void PutLL(int target, long long value); void Send(int target); : call this after using Put*** int Receive(int source); call this before using Get*** (return value: number of sended values) char GetChar(int source); int GetInt(int source); long long GetLL(int source); */ long long bs(long long L,long long R){ while(1){ long long M=(L+R)/2; char tmp=Search(M); if(tmp=='X')return M; if(L+1>=R)return -1; if(tmp!='>')R=M; else L=M+1; } } long long chk(long long L,long long R){ if(L>=R)return -1; char Lc=Search(L); if(Lc=='X')return L; char Rc=Search(R-1); if(Rc=='X')return R-1; if(L+1==R)return -1; if(Lc!='<'&&Rc!='>'){ return bs(L,R); } long long bl=L; long long br=R; if(Lc=='<'){ long long ks=1; while(1){ bl+=ks; ks*=2; if(bl>=R)break; char cc=Search(bl); if(cc=='X')return bl; if(cc!='<')break; } } if(Rc=='>'){ long long ks=1; while(1){ br-=ks; ks*=2; if(bl>=br)break; char cc=Search(br-1); if(cc=='X')return br-1; if(cc!='>')break; } } if(bl>=br)return -1; return bs(bl,br); } long long solve(long long L,long long R){ long long ret=0; int cnt=0; queue<pair<long long,long long> > Q; Q.push(make_pair(L,R)); while(Q.size()){ pair<long long,long long> at=Q.front();Q.pop(); if(at.first>=at.second)continue; long long tmp=chk(at.first,at.second); if(tmp>=0){ cnt++; ret^=tmp; Q.push(make_pair(at.first,tmp)); Q.push(make_pair(tmp+1,at.second)); } if(cnt==10000)break; } if(cnt==10000){ return -1; } return ret; } int main(){ int T=NumberOfNodes(); int I=MyNodeId(); int N=NumberOfNuggets(); long long L=RoadLength(); //printf("%d\n",I); if(I==T-1){ vector<pair<long long,long long > >Q[10]; long long ret=0; Q[0].push_back(make_pair(0,L)); for(int i=0;i<9;i++){ for(int j=0;j<Q[i].size();j++){ long long n=Q[i][j].second-Q[i][j].first; for(int k=0;k<T-1;k++){ long long left=Q[i][j].first+n*k/(T-1); long long right=Q[i][j].first+n*(k+1)/(T-1); PutLL(k,left); PutLL(k,right); } } for(int j=0;j<T-1;j++){ PutLL(j,-1); PutLL(j,-1); Send(j); } for(int j=0;j<T-1;j++){ Receive(j); for(int k=0;k<Q[i].size();k++){ long long tmp=GetLL(j); if(tmp<0){ long long n=Q[i][k].second-Q[i][k].first; long long left=Q[i][k].first+n*j/(T-1); long long right=Q[i][k].first+n*(j+1)/(T-1); if(left<right){ Q[i+1].push_back(make_pair(left,right)); } }else ret^=tmp; } GetLL(j); } } printf("%lld\n",ret); }else{ for(int i=0;i<9;i++){ Receive(T-1); while(1){ long long left=GetLL(T-1); long long right=GetLL(T-1); if(left<0)break; long long ret=solve(left,right); // printf("%lld %lld: %lld\n",left,right,ret); PutLL(T-1,ret); } PutLL(T-1,-1); Send(T-1); } } }
SRM186 Div1 Hard
昔の問題は変な意味で面白い。
プログラミングコンテストの問題の題材としてアイスホッケーが出題されることは少なくありません.しかし,活動時間の全てをオンラインジャッジにつぎ込む生活では,アイスホッケーを想像することができず,問題の理解に困ってしまうこともあるでしょう.一分一秒を争うこの世界では,致命傷となりかねません.
当然この問題の本質は問題文読解なんだけど、まず普通の人が思い浮かべるのは、「好きな方向に打てて何回でも反射できるので最短距離を求める」みたいな感じ。しかしテストケースを見てみても問題の妥当性を考えてみてもこれはおかしいので、徐々に「反射は1回以下なのでは...?」と疑うことになる。
それでもなおうまくいかないので、魔力で反射が0回のケースは考慮してはいけないことと、問題文冒頭の The left-handed Finnish hockey player から左利き選手は右にシュートしやすそうだから右のみ反射なのでは?と考えるに至る。
実は、画像の下の段落にちょろっと反射のルールが書いてあるんだけど、実はここでは「right」としか書いてない上実はこれは反射の法則ではなく、この問題でvalidとみなされる移動の仕方である。知るか。
複数経路があるときの処理も謎でゴールの右端に近いものを採用するんだけど(角度のminではない)、これも実際ゴールを入れる人は端に打ってそうだなあと思うとなんか納得できなくもない感じになる。これらのエスパーによって同点のものがたくさん現れてどれを出力しないといけないか問題も解消できて一件落着。
冒頭みたいな逸話は笑い話のように扱われていますが、この「アイスホッケー」を「物理学」や「機械・パソコンの仕組み」に置き換えてみると、未だに背景知識がないと理解できない系の問題文を書く人がいます。専門的なストーリーにしたいときはちゃんと親切に全部問題文中に記述されているかどうかを念入りに確認しましょう。物体の落下の仕方の式やファイルのURLの表し方に説明がないなんて論外です。
// I like wolves!! #include <vector> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <sstream> #include <iostream> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <queue> #include <string.h> #include <complex> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; const double EPS = 1e-13; const double INF = 1e+10; const double PI = acos(-1); vector<Pt>L; vector<Pt>R; vector<Pt>hb; class PuckShot { public: double caromAngle(int X0, vector <int> X, vector <int> Y) { int n=X.size(); double val=INF; double ret=-1.0; hb.push_back(Pt(X0,1)); for(int i=0;i<=1;i++){ for(int j=0;j<n;j++){ double tx=X[j]; double ty=Y[j]; if(i%2==0)tx+=3000*i; else{ tx=3000-tx; tx+=3000*i; } L.push_back(Pt(tx-25,ty)); R.push_back(Pt(tx+25,ty)); hb.push_back(Pt(tx-25-(1e-10),ty)); hb.push_back(Pt(tx+25+(1e-10),ty)); } if(i==0)continue; Pt gl,gr; gl=Pt(3000*i+1408.5,1733); gr=Pt(3000*i+1591.5,1733); if(i%2)swap(gl,gr); hb.push_back(gl); hb.push_back(gr); for(int j=0;j<hb.size();j++){ bool ok=true; for(int k=0;k<L.size();k++){ if(iLS(Pt(X0,0),hb[j],L[k],R[k])){ ok=false;break; } } if(!iLS(Pt(X0,0),hb[j],gl,gr))ok=false; if(ok){ Pt p=pLL(Pt(X0,0),hb[j],gl,gr); double dist=(p-gr).ABS(); // printf("%f %f %f\n",hb[j].x,hb[j].y,dist); if(dist<val){ val=dist; ret=(hb[j]-Pt(X0,0)).arg()*180/PI; } } } } return ret; } };
最大独立集合 速め
696Mediumで書いたもの。38頂点を1000回実行して200ms弱と相当速い。
s[i][j]: 隣接行列
S[i]: 隣接行列を詰め込んだもの
v[i]: 頂点の利用状況
val: 答え
uk: v[i]=0のiを詰め込んだもの
n: 頂点数
int s[40][40]; long long S[40]; int v[40]; int val; int n; long long uk=0; void calc(){ int nm=0; for(int i=0;i<n;i++)if(v[i]==1)nm++; val=max(val,nm); for(int i=0;i<n;i++){ if(v[i]==0&&__builtin_popcountll(uk&S[i])<2){ v[i]=1; uk-=1LL<<i; long long ch=0; for(int j=0;j<n;j++)if(v[j]==0&&s[i][j]){v[j]=2;ch+=1LL<<j;uk-=1LL<<j;} calc(); v[i]=0; uk+=1LL<<i; for(int j=0;j<n;j++)if(ch&(1LL<<j)){v[j]=0;uk+=1LL<<j;} return; } } int dm=1; int at=-1; for(int i=0;i<n;i++){ if(v[i]==0&&__builtin_popcountll(uk&S[i])>=dm){ dm=__builtin_popcountll(uk&S[i]); at=i; } } if(at==-1)return; v[at]=2; uk-=1LL<<at; calc(); v[at]=0; uk+=1LL<<at; v[at]=1; uk-=1LL<<at; long long ch=0; for(int j=0;j<n;j++){ if(v[j]==0&&s[at][j]){ v[j]=2; uk-=1LL<<j; ch+=(1LL<<j); } } calc(); for(int j=0;j<n;j++){ if(ch&1LL<<j){v[j]=0;uk+=1LL<<j;} } v[at]=0;uk+=1LL<<at; }