ヘクトのメモ

なんとなくいろいろ書いていくと思います．

ICPCアジア地区予選2016

チームnocowとして参加しました．(初のICPCアジア地区予選)

チームメンバー
@osrehun
@icchyr
@xthexworldx

結果は5完24位でした．
初めてのアジア地区予選はいろいろ新鮮でした．

以下詳細なタイムスケジュールと感想


初日

初つくばでした．
都会より遠くを広く見れるので個人的に好き
何かお祭りをしていた．

ちなみに，icchyが集中講義で遅れる．
いろんな人に質問攻めにあうので次の返答をずっと行う．(仕方がないことではある)

練習セッション
A問題を爆速で通す．
その後に環境構築の確認を行う．
この時に，ありとあらゆるバグを踏む
nokotaroが英字キーボードに慣れるためにめっちゃ頑張っていた．
.vimrcを書く前にvimをタイピングしたり，循環シンボリックリンクを貼ったり...
B問題はチームメイトが一切頭働いていなかったんで、二分探索解を投げつける．
とりあえず，無事に環境構築できた．

ウェルカムパーティー
いろんな人と再会する．
ICT48の人といろいろな話をしていた．
ここでチームメイトと合流する．
チーム紹介スライドにアニメーションを仕込んだけど，飛ばされて悲しみ...
ということで，チームスライドを公開します．
www.dropbox.com

宿泊施設
ARCには出ることなく寝る．
謎のキャラクターと温泉がとても良かった．
久々に未来日記を読んだ．

2日目

午前6時に起きる．
ついに戦いの日ということで力がみなぎっていた．
朝ごはんを食べて会場へ移動
すぐに会場入りしそうなので，急いでつぶやく．

そして本番スタート

0:00
まず，icchyが環境構築を行いながら，自分がA問題を読む．xthexworldxにはB問題を任せる．

0:06?
A問題が読めてすぐに実装できるので，すぐに自分が実装する．
テストケースを落とせるリンクがあったので，icchyrが適当なスクリプトで全部落としてくれる．
サンプルが全部通る

0:13 A AC
nokotaroがB問題を読み終えたので実装を任せる．
icchyがC問題を読み，自分はD問題を読む．
Bのサンプルが通ったらしい．

0:34 B AC

C問題を自分とicchyと話していて思いついたので，icchyに実装を任せる．
サンプルは通ったけど，同じレーン間に複数回のクエリをあたえたら死ぬような嘘解法であることを見ぬく．
自分がレーンの上端と下端をpairに持った方針を思いついたのでチームメイトのコードを改造する．
Cのサンプルが通る．

0:56 C AC

次に，D問題を考える．anagramの長さで分類して，文字の組をハッシュをsetで持たせれば良さそうということを思いつく．
さすがに，set>は怖いので...
実装すると全てのサンプルが通る．
投げる．

?? D TLE
TLEしたのでデバッグを始める．この時にicchyが最大ケースのランダム文字列をpythonで生成してもらう．
投げる．time ./d.out < d.in　で計ると15.6秒... 定数倍高速化すればいけるじゃん!
vector+sort+uniqueに書き換える．46秒... 絶望という気分
次にまさかと思い，unordered_setに書き換える．8.7秒!
というわけで投げる　

1:47 D AC

これで通るとは...
ということで問題を読み進める．
nokotaroがE問題読めたので実装をお願いする．
構文解析だけど，なんとかなると思っていた．

次に解かれている人の多いG問題に取り組む．
いろいろ考えると，1を連続する区間を足す操作や1以上になる最も右の部分など求めるクエリ
遅延評価つきセグメントツリーだと思い，E問題の実装と交代してライブラリを写経する．

コンパイルして実行してみる．
システムが不安定になる…
スタッフ呼んだりしてパニックになり30分くらい時間を使って判明したバグが
配列のサイズを1<<(32-__builtin_clz(m))と書くべきところを1<<(__builtin_clz(m))と書いて2GBくらいのメモリを消費していた...

この間にチームメイトがE問題をデバッグして実装して，進める．
4:00くらいのタイミングでE問題のサンプルが通る．投げるE WA...
この後もいろいろなバグを探して潰そうとして実装が二転三転していく...

I問題の考察とかも進める．

ad-bc =1となるような三角形を求める方法は思いついたけど，

x_bb=10^9,y_bb=10^9の場合の解法が思いつかず

G問題を実装してサンプルが通ったけど、xの値が大きくてどうしよう...
動的や座圧にするとか思いついたけど，やばそう...
そこで,xの値を2*nで制限してコードを投げる．

4:49 G AC
めっちゃ喜んだ
この後もE問題のデバッグを続けたけど，通らず

5:00 TimeUp


講評
解けなかった問題について見るけど，実装するのが一番重要みたいな形だった．
あと，最後にG問題を通したので順位表が上がるのを見れて楽しかった．(YES/NOはめっちゃ盛り上がる)

クロージングパーティー
ICPCを終えた選手に，大量の問題を企業が出題するパーティー(楽しい)
そのせいか，問題解き:食事=3:1という時間配分になった．
その時にゲットした景品がこれ


感想
初回なので，参加できて嬉しいという思いがあるけど，5完だったのが心残り(6完はしたかった)
最初は割とスムーズにいったけど，途中で詰まってしまった．
特に，E問題は合計3時間くらい費やしていたので，どこかでコードを1から書き直すべきだったかもしれない．(この判断は難しい)
自分がコーディングすれば良かったのかなと言われたけど，実際どうなんだろう (一人でずっとコーディングしているのは少し辛いので避けたい)
ようやく，チームの中で自分が司令塔という役割なのだということを意識した．(コーディングの担当割り振りはほとんど自分でやる)
あと，解法は思いつくけど実装するときのことをあまり詰めないでコーディングしていることが多いな... (ACすることが重要なので)
相変わらずだけど，実装時間の見積もりを適切に行う訓練はするべきかな...
こういったことはいくつかのブログに書いてあるので，チーム戦略を改善していきたい．
topcoder.g.hatena.ne.jp
それと，個々の実力ももう少しあげないとやっぱり辛いな... 1人で解くことができる問題のレベルを上げたい．

大会自体の質は高く，来年もぜひ参加したいと思いました．
ただ，写真がどこに掲載されるかの情報は前もって知りたかった．(順位表のサイトに載ることを大会前日の夜に知ったので)
それと，順位表や生中継などの観戦者向けのコンテンツは充実していて，知り合いに紹介しやすかった．(簡単なルールの記述もあると良いのかも)
(研究室での話題にも多少なった)
いろいろ楽をするために持って行く荷物は軽くすべきですね... (トートバッグがすごい数に...)

というわけで，最後のICPCに向けて引き続き練習をします!