ICPC 2017 国内予選

うろ覚えだけどメモ。

参加まで

チームメンバーに誘われたので参加することにした。ところで、いまいち参加方法がわからない。自分の大学が最後に出場したのは大分昔で、あまり参考にならない。具体的には、コーチとか監督とかどうすればいいのかということである。研究室の先生にお願いして何とかなったが、監督とかコーチとか本当に必要なんだろうか…。

ICPC特有の謎仕様(電子データの持ち込みがダメなのに、なぜ紙なら良いのか?)に文句を言いつつ、蟻本に載ってないような処理を幾つかまとめて印刷して持っていった。本当に何の意味があるんだこれ(一切の持ち込み不可とかなら分かるけど)。ICPCはルールに妥当性を感じないものが多くて好きになれないなぁ。

A問題

本来チームメンバーに丸投げする予定だったんだけど、問題文の印刷が終わるのを待てずにコードを書いてしまう。AC。

B問題

チームメンバーに丸投げしていた。

C問題

RMQや累積和の雰囲気を感じたけど、よく見たらA問題レベルの処理を要求されていた。あまりに簡単すぎたのでB問題を待たずにAC。FAだったのかな?

D問題

25×25>500なので指数時間アルゴリズムっぽい。B問題を待たずにAC。これもギリギリFAだったんだろうか。

E問題

自分がD問題をやっている間にチームメンバーが E,F,G の問題概要を読み終えていたので、雰囲気を教えてもらう。Eが一番難しそうに見えたけど、一応E問題から考察を始める。

入力長が16以下なので、長さ15以下の式をすべて列挙するとかが有り得そうな解法だとは思う。そんなに多くならないという直感を信じることにする。

B問題(2)

チームメンバーが実装に苦戦していたようなので、B問題の問題概要を聞く。書いてあったコードをちら見したらヤバそうだった。一から書いても時間も掛からなさそうだったので自分が適当に書く。微妙に解釈が面倒だったので、細かいルールをチームメンバーに訪ねながらコーディングする。AC。

E問題(2)

どうやって全列挙しようかと迷っていると、DPらしき解法が思いつき始める。インデックスに出力を16ビット並べるというもの。全列挙に比べて計算量に自信を持てそうということでDPの方の考察を始める。

bellman-ford的っぽい方法を取れば2^32×hoge 程度のループを回すことで解くことができ、遷移も比較的穏やかだと分かったので実装を行う。実行時間がどの程度になるのかよくわからなかったが、実際に書いてみた感じだと1分程度で実行が終わるようだった。

あとは構文解析を書けば完成。先読みしなくても解析できるタイプだったのでサクッと実装する。サンプルとも合ったので提出。しかしWA。

何がダメなのかと眺めていたら、dpの初期化がおかしかった。再提出してAC。

(後になって思えば、全列挙したときのパターン数はカタラン数的なもので評価できる)

F,G問題

順位表を見るとE問題を解かずにF問題を解いているチームがちらほら。解くべき問題を間違えたかなぁと思いつつF問題に取り掛かる。

答えが複数ある場合は~とか言っているが、これはフェイクで(i,j)が決まれば答えが一意に定まるような気がする。また2冪に関する問題なので、おそらくパリティが絡む、という予想を立てる。

実際にL,Rによってどのように変化するかを眺めてみたが、露骨にパリティがでてくる訳ではなさそうだったので諦めて G 問題に移る。

G問題はYES/NO問題。YES/NOに対してフローは悪手に思えた(直前のAGCのEでYES/NO問題をフローで解こうとして失敗した)のでフローはとりあえず捨てる。おそらくグラフ論的性質を使う問題で、○○分解とかその手のもので判定できるのではというのが最初の推測。二重頂点連結成分が使えないかなぁと考えていたが面倒になってやめる。

大抵の場合、適当にやってもうまくいきそうに見えたので、邪悪な探索を掛けることも考えたが面白くないのでやめる。

(どうやら右手法で解けるらしい。あまり関係ないが、以前codechefで平面埋め込みに関する問題を解いたことがあり、その際用いたアルゴリズムはいま考えると右手法に基づいていた。後になって思い返してみれば、平面性のあるものに対して右手法は自然な発想だったように思える)

H問題は方針は割と自明に見えたが、細かいところを詰める余裕もないのでやめる。

おわりに

結局 ABCDE の5問しか通せず17位という結果になってしまった。F,Gを並列に考えて中途半端な考察で終ったのが良くなかったように思える。あと、最近そこまで練習していないため集中力が落ちているような気がする。AOJは全然手を付けてないのでやろうかなぁ。