うにゅーん、って感じだ

だいたいのコンテストサイトで橙か赤です、よく C#を書きます。

ACM-ICPC 2017国内予選 参加記

ICPC

半年ぶりのブログ更新ですね。
本当はこの記事の前に、この前 SnackDown2017 というやつでインドに行った、という記事を書かなければならないのですがちょっと色々忙しかったのでそのうち書きます。

icpc とは？

こちらをごらんくださいな
ACM-ICPC とは？ | ACM-ICPC 国際大学対抗プログラミングコンテスト



あらすじ

icpc たいてっく予選は毎年熾烈（しれつ）を極めていた。謎の組織 FCCPC 、†赤きもの†へと進化した後輩、大魔王 yosupot ...。
ただ、そんなたいてっくにも希望はあった。謎の組織 FCCPC は謎すぎたため消滅、大魔王 yosupot は力を溜めるための眠りについた。
今こそたいてっく予選に打ち克つべき！ †赤きもの†へと進化した後輩の次の1枠を狙い立ち上がったチーム「kurukuru-sushi」の前に立ちはだかったのは、チーム「IQ1」だった…。

登場人物

チーム「kurukuru-sushi」

rian_tkb（りあん）, Ashurnasirpal（葦）, monman53（もんまん）からなるチーム
http://icpc2017.yamagula.ic.i.u-tokyo.ac.jp/team/1308

チーム「IQ1」

吹雪, 睦月, 夕立 からなるとてもバランスの良いチーム
http://icpc2017.yamagula.ic.i.u-tokyo.ac.jp/team/1142

チーム「ninjaribaton」

nari, baton, ninja からなるガチプロ後輩チーム
http://icpc2017.yamagula.ic.i.u-tokyo.ac.jp/team/1327

ティッピーぬいぐるみ

チーム「kurukuru-sushi」の机の上に鎮座するぬいぐるみ


国内予選前日 (7/13)

たいてっく予選突破が絶望的だった一昨年、去年とは異なり、たいてっく予選突破が現実味を帯びている今年のicpc国内予選。……というより、今年の出場選手のうち†赤きもの†へと進化した後輩の次にレートが高いのが自分で[要出典]、さすがにたいてっく予選突破できないと人権がない、という状況になり今までにないプレッシャーに追われる rian_tkb。

血迷った rian_tkb は、秋葉原に赴き25000円のキーボードとリストレストを購入する。

（今思うと、ここまでして突破できてなかったら本当にやばかった）

国内予選当日 (7/14)

コンテスト前

今期の授業は全て切ったのでリハーサルが終わるまでに大学に着けばいいのだが、家にいても落ち着かないので早めに家を出る。


ラボに置いてあった蟻本を持ち、蟻本に書いていない平衡二分探索木と、あとは AtCoder の提出のうち特に苦手なものの提出コードを印刷して会場に向かう。


チームメイトが皆蟻本を持ってきていたので積み上がる。

リハーサルも3問通して暇なので遊ぶ（上の kurukuru-tippy もこのとき撮影）。

この後、もんまんくんが M問題を頑張って通していた。

コンテスト中

最速で印刷ジョブを飛ばしたつもりがプリンターがトナー切れで、少しタイムロス。
その間に A問題を読む。
……ん？ これは恐ろしいほどに簡単だぞ？？？
横からめっちゃ口を挟みながらもんまんくんにコーディングしてもらい、そのまま AC。ここまで 5min。

葦くんが B を読んでいたので見ると、構文解析。
問題文がよくわからなかったのでよくよく読むと、ダブルクォーテーションで split して偶奇を気にしつつぐっ、とやるだけ。
しかし、A が通ってしまい PC を空いた状態にしたくないという焦りから見切り発車してしまい、少しめんどい実装になってしまった。
ただそこまでバグらせずに通してくれたのでよかった（とは言ってもやはり時間はかかってしまった）。ここまで 30min。

葦くんが B 問題と格闘している間に C 問題を手に取ると、h, w <= 10 なのが不思議なレベルで簡単な問題。
本当にやるだけにしか見えない。
もんまんくんに解法を伝えつつ紙コーディングをしてもらう（もちろんこれにもめっちゃ口を挟む）。
葦くんが B を通したらそのまま C を実装してもらい、AC。ここまで 40min。

ここで順位表を見る。
結構いい感じに進んでいたと思っていたので IQ1 に時間ペナルティでとても大きく離されていてとてもビックリする。
この様子だと正答数で上回らないと IQ1 に勝てないぞ……。

ここで自明問題が尽きる。
自分はすでにちょっとテンパっていたので、葦くんに D の問題文の要約を頼む（正確には問題概要はほぼ入っていたが、D に入る問題に見えなかった（＝普通に解ける気がしなかった）ので誤読が怖くて読んでもらうことにした）。
どう考えても n * m <= 500 が重要な制約だが、よくわからない。
葦くんから整理された問題概要を聞くが、まだわからない。
ただ、こういうのは大抵 n = m あたりが重要なので、紙に 20 * 25 = 500 という式を書く
→ あ、これいけるのでは？？？
PC が空いていた焦燥感もあり、とりあえず書き始める。
途中少しテンパるが、大きなバグもなく実装した……はずが、答えが合わない。
よく見てみると、求めるものが作れるレシピの集合が何通りあるか、ではなくレシピの集合の要素数の最大値だった（ここは葦くんの誤読だったと思う）。
ただ、修正自体はすぐにでき、AC。ここまで 1h10min。

ここでまた順位表を見ると、また IQ1 との差が広がっている。これは本格的にヤバい……。
E は無理そうという話があったので、先に F を見る。明らかに考察ゲーの匂い。
無理そうと言われていた E も読むが、確かに無理そうだったので、F の考察をする。
とりあえず計算用紙に印をつけて実際に折ってみる。
左からの位置と上からの位置と左右どっちに折ったかがわかれば、次の状態が定式化できそうな状態にはなる、が、まだ考察が進まない。
もう少し考察をすると、上から何番目にあるか、というのは折り方と 1対1 に対応することがわかる。
あと、逆に折った状態から展開したとき、右に開いても左に開いても上から何番目かというのが変わらないことがわかった。
が、前からやっていくべきか、後ろからやっていくべきかがよくわからない。
両方からやって 2^30 はさすがに間に合わなさそう……。

ここでうだうだ言っていると、もんまんくんが考察の手助けをしてくれて、一気に解法へ結びついた


（折った状態から展開したとき、右に開いても左に開いても上から何番目かというのが変わらない、という自分の考察を完全に忘却していた）

ばばばっと書く。
1-origin なので境界条件とか +1 するか、とかがクソめんどい。
実際にバグる。
サンプルが合うようにコードをいじいじする。

そうこうしているうちに葦くんが G 問題がいけそうな雰囲気になったと言っていて、写経が必要なのでとりあえずコードを印刷して交代する。

コードを印刷して眺めていると、バグがすぐに見つかる。
また交代してもらってそこを直すとサンプルが通ったので、そのまま投げると AC。俺ってもしかして天才か？？？ ここまで 2h。

葦くんが G の写経をしている間、E を考えるが普通に無理そう。
H に関しても、4回まで調べればいいので探索範囲はすごく絞れそうだが絞り方がよくわからない。
なので、葦くんの G の解放に反例がないかどうかを調べる。

葦くんのコーディングが終わってサンプルを食わせるが、バグっている。
いくつかのしょうもないバグは潰し、見た目上はいい感じに動いているが、どうしても関節点列挙がバグっている……。写経はもんまんくんに適宜チェックしてもらっていたので問題ないはず……。
もう時間がなかったので一回バグったままで投げてみるが、当然 WA。
結局バグがどこかわからず、最後は順位表を見ながら終了。

最後の 2h59m59s で IQ1 が F を通していて、時間ペナルティ的に 1WA でも出していたら順位が逆転していたので、本当に危なかった。


結果、ABCDF の 5完 0WA早解きで 16 位でした！ まぁ上々では
f:id:riantkb:20170715204109p:plain

Standings
http://icpc2017.yamagula.ic.i.u-tokyo.ac.jp/standings/

コンテスト後





打ち上げに行くが全然飲み足りないので、家で独り祝勝会

いま、めっちゃジンが入っています✌︎

あとがき

国内予選突破できて本当に良かった。
こんな日が来るのは本当に夢みたいで、大学入って競プロ始めて以来、一番嬉しいかもしれない。

それではみなさん、つくばで会いましょう！