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

結果

5完26位でした。

Results and Standings | ACM-ICPC 2016 Asia Tsukuba Regional

メンバー

@shora_kujira16
@menphim
M2の先輩
@odashi_t（コーチ）

会場に行くまで

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

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

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

49分のがある pic.twitter.com/nv4aRC33Ij
— しょラー（求職中） (@shora_kujira16) October 14, 2016

ﾌｯｼﾞｻｰﾝ pic.twitter.com/NgJwVIurjd
— しょラー（求職中） (@shora_kujira16) October 15, 2016

東海道新幹線弁当 pic.twitter.com/s8e4uzEMAE
— しょラー（求職中） (@shora_kujira16) October 15, 2016

うまかった pic.twitter.com/6caHRUfoZA
— しょラー（求職中） (@shora_kujira16) October 15, 2016

つくば到着 pic.twitter.com/kOtZbicWCE
— しょラー（求職中） (@shora_kujira16) October 15, 2016

pic.twitter.com/dlUFeHKION
— しょラー（求職中） (@shora_kujira16) October 15, 2016

練習セッション

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

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

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

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

DOMjudgeのスタックサイズはulimit -s unlimitedであることが知られている https://t.co/iSyWTjtnkY
— しょラー（求職中） (@shora_kujira16) October 19, 2016

Welcome Party

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

宿泊

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

コンテスト

A

解いた

B

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

C

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

D

基数をBとして

(aの出現回数*B⁰ + bの出現回数*B¹ + cの出現回数*B² + … + zの出現回数*B²⁵) % M

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

↓ 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);