ICPC2016 アジア予選つくば大会

2016/10/17 (Mon) ICPC

ACM-ICPC アジア地区つくば大会 2016 に参加した記録です http://icpc.iisf.or.jp/2016-tsukuba/regional/?lang=ja

コンテストの結果は大変微妙でしたが， 問題は面白く運営もよくされて大変良かったです． コンテスタントとしては今年で終わりですが，来年からも JAG として手伝いで参加する可能性が高いです． 準備関係者，スポンサーの皆様ありがとうございました．

前日

  • かなり早く到着したので関西勢とだべる
  • 練習セッションで，ジャッジサーバーはスタックメモリはかなり大きく実行速度もそれなりに速いことを確認する
  • C++ も新しいし __int128_t なども使えて最高
    • 老害臭いことを言うと，練習セッションでは必ずこういうことも確認しましょう
  • 懇親会でコミュ症を発揮する
  • ARC は寝落ちする

当日

本番

チーム nishiyon で 32 位だった． http://icpc.logic.cs.tsukuba.ac.jp/standings/

  • A
    • 気づいたらチームメイトが通していた
  • B
    • 見るからに面倒くさそうだけど読むとそこまででもない
    • しかし誤読して 1 WA
    • すぐ直して AC
  • C
    • チームメイトが考えていたが，僕が嘘考察を吹き込んで大変邪魔をしてしまった…
  • D
    • 「連続した」部分列という条件を見落として，ソートして LCS 求めるだけやんけ！となる
    • サンプルが合わない
    • 改めて考える
    • 割とすぐ思いつく
    • 実装の計算量の計算をミスって TLE (マジでごめんなさい)
    • 想定解の $O(|s_1|^2 \log (|s_1|^2) + |s_2|^2 \log (|s_1| ^2))$ に修正する
    • set<array<int,26>> S[4001] で部分列の文字の頻度を持ったら TLE
    • irb でランダムな長さ 4000 の文字列を作ってテストすると確かに 15 秒かかっている
    • irb は便利
    • __uint128_t の力によって定数倍高速化をし AC
    • 最初からローカルでテストすべきだったし TL が 10 秒な時点で察するべきだった
  • E
    • 面倒
    • パーサーをごりごり書く
    • パースエラーは例外で __LINE__ を投げる実装にするとデバッグしやすかった
    • 時間がギリギリで間に合う絶対の自信も無いので他の問題も見るために中断する
  • F
    • チームメイトが無理そうと言っていたので諦める
  • G
    • 通しているチームも多いが残り 30 ~ 40 分 (確か) しかない
    • おそらく答えに近いところまで考察が詰まっていたが詰め切れず終了

大戦犯で申し訳ない．無駄な WA を出し過ぎ，G を先に見るべきだった，E をさっさと書くべきだった など反省点ばかりで悲しい．真に立ち回りを最適化すればあと最低 2 問は溶けた気がするので悲しいがまあ練習不足だったので．

問題以外のこと

  • 位置的に周りが北京大学，BrakeAce，Cxiv-Dxiv で威圧感がすごかった
  • キーボードは僕は普段から英字なので英字配列でも気にならなっかたがチームメイトはつらそうだった
  • キータイプの感触は悪かった
  • 普段のエディタが
    • 私: Emacs or Visual Studio
    • チームメイト 1: Visual Studio
    • チームメイト 2: Vim
  • という感じでバラバラで，合わせるのが大変だったので結局本番もバラバラの環境で実装した
    • チームメイト1 が Eclipse を使うようなので私も Eclipse に合わせようとしたけど， 私がやるには Emacs とターミナルで作業するより何倍も非効率だったので諦めた
  • 終了間際でかなり順位を上げているチームが多くてすごかった
  • 表彰式会場の壁の模様の意味に感動した
  • 懇親会でクイズを出している企業が多くて真面目にやると食べている時間がなさそうだった
    • 僕はお腹の調子が悪くあまり食欲がなかったのでまあ
  • PFN ブースでついに iwi さんのサインをもらう
  • Google の謎解きはクオリティが高かった