読者です 読者をやめる 読者になる 読者になる

ACM-ICPC 2016アジア地区つくば大会 参加記

結果

5完26位でした。

Results and Standings | ACM-ICPC 2016 Asia Tsukuba Regional

メンバー

会場に行くまで

奈良に新幹線なんてあるわけないじゃん!

移動時間の見積もりで,1時間に2本のバスに乗り遅れたときのバッファとみどりの窓口が混雑していたときのバッファを乗せていたら,13:00時到着の予定で6時30分に家を出ることになりました。結局バッファを使うことがなかったので,12時すぎに到着したのですが,つくば ↔︎ けいはんな に5時間半かかるのはちょっと憂鬱ですね…

駅前では筑波大の研究室のロボットが動いていました。

練習セッション

事前に System Trial DVD が提供されていたので,滞りなく終わりました。

練習問題を解いたあとは印刷を試してみたりClarを試してみたり "I want to go to restroom." の練習をしてみたりしました。

そのあとは実行環境のスタックサイズを確認したり,ループがどれくらいの回数回せるかを確認したかったのですが,キーボードに慣れるためにタイピング練習をしていたら練習セッションの時間が終わってしまいました。去年までのJava Challengeの時間はキーボード練習の時間を兼ねていた考えると,練習セッションの時間はあと15分くらいは欲しかったかもしれません。

去年のキーボードは配列がイマイチで選手からも不評だったのですが,今年のキーボードはアンケートの内容を反映してもらえたのか,去年よりも拡大に快適でした。

Welcome Party

会場はアヒルボートの博士号がある池に近い場所だったらしかったので見に行けたら良かったのですが,良いタイミングが見つからず見に行けませんでした。

宿泊

東横イン最高!!去年はあまり眠れず競技時間中に頭が回らなくて困ったことになったのですが,今年は快適でした。

コンテスト

A

解いた

B

時間がかかったけど解いた

C

その位置に到達できる製造ラインの番号のminとmaxを更新していくDPみたいなものをめんふぃむが提案してくれて10分くらいで解けた。

D

基数をBとして

(aの出現回数*B0 + bの出現回数*B1 + cの出現回数*B2 + … + zの出現回数*B25) % M

をハッシュにした。ハッシュ値をstd::set<int64_t> に格納して O(N2 log N) にするとTLEするし,ハッシュをstd::unordered_setに格納して O(N2) にするとハッシュがコンフリクトしてWAになるしペナルティがたくさん加算されて辛い思いをした。O(N2 log N) の定数倍を改善すると通った。想定解は O(N2) らしい。ふーん…

↓ AOJでは通るけど本番環境では通るか自信なし

https://gist.github.com/arosh/61b3753f1d747b6f251e90f34bac2299#file-d-cpp

G

ビットの配列の上で多倍長の足し算を実装できればいいね,ということで,以下のクエリを実現するデータ構造を平方分割で実装するという愚かな方針を選んでしまった。

  • set1(p) … pビット目を1にする
  • set0range(l,r) … [l,r) の範囲のビットを全て0にする
  • search(p) … pよりも左側にあって,最も右にある0の位置を返す
  • check0(p) … pよりも右側のビットが全て0であるか確認する

常識的に考えて,他のチームはかなり早く通しているのだから,もっと簡単な方針がないか検討するべきだった。

↓実際に通したコード

https://gist.github.com/arosh/61b3753f1d747b6f251e90f34bac2299#file-g-cpp

E

40分しか残っていない状況で実装を始めた。

終了数分前に -1+1 を -(1+1) と解釈してしまうバグが見つかり,どこを直せば良いのかすぐに見つけられず無念のまま競技時間が終わってしまい,E(p)F(p) に直せば良いだけじゃん,ということがわかって絶望していたのだが,そのほかにも 01 みたいな数値リテラルは無効にするという処理を入れていなかったので,1バイト直せばACするというのは嘘だった。

↓ あと数分あれば通せたコード

https://gist.github.com/arosh/61b3753f1d747b6f251e90f34bac2299#file-e-cpp

@@ -113,7 +113,7 @@ Result F(iter &p) {
   }
   else if(*p == '-') {
     ++p;
-    Result e = E(p);
+    Result e = F(p);
     if(!e.valid) return fail;
     e.value *= -1;
     return e;
@@ -125,10 +125,13 @@ Result N(iter &p) {
     return fail;
   }
   int n = 0;
+  int i = 0;
   while(isdigit(*p)) {
     n *= 2;
+    if(i > 0 && n == 0) return fail;
     n += *p - '0';
     ++p;
+    ++i;
   }
   // DEBUG(n);
   return Result(true, n);

表彰式

13*2位という理由で(?)IBMから副賞を貰いました。順位はイマイチだったけど,今までICPCで一度も賞を貰ったことがなかったので,最後にもらえて嬉しいです。

最後に

5年前にICPCの出場歴が無い大学から参加を始めて,最初は国内予選60位という順位でしたが,最終的にアジア地区大会に4回も出ることができて良かったです。

続き