ICPC 2017 国内予選に参加した話 - 日々ｄｒｄｒする人のメモ

今年もICPCに参加することにした。
今年はちゃっくとkuwa氏と組んでチームIQ1として参加した。

2017年国内予選 | ACM-ICPC 2017 Asia Tsukuba Regional

国内予選前の準備とか

予選前までは週一で過去問使って本番想定のチーム練習をしてた。

また、模擬国内予選の方に参加した時に幾何実装で無限にバグらせてつらい思いをしたので、昔ちょこっと解いてたAOJのIntroductionのCGLの続きを解いてライブラリを生成するなどしていた。
http://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?course=CGL

CGL解いたもの + ライブラリ (今回の実装は基本Pythonで書くつもりだったのでPython)
AOJ: Library of Computational Geometry (CGL) · GitHub

国内予選

開始後はちゃっくA問題、kuwa氏B問題、自分C問題で進める。
C問題は制約を見て、とりあえず全てのパターンを試すことにすぐ気付く。それをそのまま実装し通した。

A,B,Cと順調に通すことができ、次はちゃっくが考えていたD問題を考える。E問題はkuwa氏、F問題はちゃっくに任せる。

D問題は ${1 \le m \times n \le 500}$ が気になりながらｳｰﾝｳｰﾝと悩んでたら、レシピをxorして得られるmビットが高々 ${\min(2^n, 2^m)} \le 2^{22}$ 通りしかないことに気付き、bitDPっぽく書いたら通った。D問題までは55分で通すことができてて調子がよかった。

その後は、E問題をkuwa氏と一緒に考えてみる。自分はa,b,c,dの全ての入力(16通り)の真偽を状態に持つ ${2^{16}}$ のbitDPを思いつくが、値の更新が重すぎて詰み♨。kuwa氏はparseの実装をしてその上でいろんな方法を試す。
E問題を考えている時にちゃっくが相談しにきて、その際にF問題の解の計算方法の方針が見えたため、F問題をちゃっくと一緒に考えてみることにする。

F問題でいろいろ悩んでたら、印の部分が上になるように折ったのか下になるように折ったのかを折った後から順に計算しておき、その次に、印の位置が折った時のリボンの半分から左にあるか右にあるかによって"L","R"を折る前から順に判別していけばよいことに最終的に気付く。
この考察がややこし過ぎて1時間以上使い、終了10分前ぐらいに実装を始める。急ぎ目で実装したので入力の変数名i,jとループの変数名が衝突したり、-1が抜けたりと、バグに遭遇しまくって無限のつらみにハマりかけたが、実装を終える。ぎりぎり過ぎて間に合わないのではとドキドキしながら提出してたが、終了1秒前に通すことに成功。実装終わってから2回目の提出までを落ち着いてできた自分を正直に褒めたい。

ABCDFを解いて5完、最終的には20位になった。学内では3位になった。
f:id:smijake3:20170715085427p:plain