ACM-ICPC 2018 Asia Yokohama Regional 参加記
ACM-ICPC 2018 Asia Yokohama Regional に参加してきました。 神戸大学で、getting_over_32というチームでした。 チームメイトは私kurenaifとcormoranさん、takeoさんです。
チーム名の由来としては、Asiaに生きたいねということで予選で確実に突破できる32位を通過したいという気持ちと、私が当時getting_over_it with bennett foddyにハマっていたのでそれらを連結させました。 今年でAsiaは初参加です。
1日目
同期は早生まれの人でない限りいないはずなので、ぼっちだろうなぁと思っていたらコーチでdrafearさんとか大阪大学の友人とか、あとはスタッフ側できゅうりさんなどに会った。久々に会ったのでテンションが上った。
1日目はリハーサルということでA-Dまでの、本戦とは関係ない問題を解く。 最近記憶がすぐ無くなる傾向があり、問題は忘れてしまったがDが制限付きで最小全域木を構成する問題だった気がする。 右前にいたチームがすぐ通していてやばかった。
ctrlとcapsを入れ替えたかったが、コマンドをメモしておらずかつ忘れるという悲しい事件があったので、そこでかなりの時間を食った。 特にtakeoさんにlinuxコマンドの使い方をなれてもらいたく、この日は長く使ってもらえるように指示した。
その夜、中華街でTikeさんが予約をとってくれた店で10名今日でご飯を食べた。 ご飯でNimが始まりかけたのが面白かった(やりがちらしい)
2日目
いよいよ本戦。 開幕は準備: cormoranさん、A:coromoranさん(with takeoさん)、B:私、C:takeoさん(with coromoranさん(?))みたいな感じで動いた。 Bを読んでいたら知らん間にAが通っていたので、Bを実装した。
B問題
Bはざっくり、数列が与えられるので、そのうちから任意の N 個を取り出し、等差数列を作る問題で、 Nを最大化させる問題だった。
結論から言うと、N^2 logN は実装によりけりで、N^2は確実に通るみたいな問題で、油断してN^2 log Nを実装していたらTLEを吐いてしまった。
log Nの部分はmapでかかるのだが、ココをlower_boundにすることでAC
そのあと、残りの問題を読んでいたらC問題がACしていたので、Standingsを見つつ、D,G,Kに注目する流れに
D問題はパット見た感じ、なんか見たことあるなぁという気持ちになった(実際見たことあった)のだが、すぐ解法を思いつかないのでとりあえずパス。
G問題がよく解かれていたので、G問題を考察
G問題
バブルソートの交換回数を求めるのだが、あるindexまでは昇順ソート、あるindexまでは降順ソートみたいな感じで山形のソートを行う問題。山の頂上の位置はどこでも良くて、最小となるような位置で答えを求める。
問題を見たときに、とりあえず転倒数は必要そうだったので、転倒数は merge_sort を使う方法と BIT を使う方法があることをチームメイトに伝え、今回の問題はさらに中に入っている数字が大きくないのでBITが適切な可能性が高いことも共有しておいた。
最初は、山の頂上に位置するindexを決めたら答えが求まるかなと思ったが、その情報自体は余り大事ではないらしく考察が進まなかった。
こういう問題の基本は、「わかりそうなものから順番に決めていく」という感じなので、バブルソートらしく小さい順に値を見ていくことにした。
すると、実験をしていくと小さい数字は右と左のうち、近い方によっていくことが判明した。
この時点で、priority_queueを使った実装を思いつくが、もう少し軽そうなので議論を進めた。
takeoさんが、「今注目している数字より大きな数字がある分だけ移動する」という確信めいたことをつぶやいてくれたので、考察を整理した。
これらを組み合わせると、それぞれのindexについて、「その数字より左にあるその数字大きなものの数」と「その数字より右にあるその数字より大きなものの数」のうち、小さな方を、すべてのindexについて足していくと良いことがわかる。
これはBITを使うと楽なので、BITで実装。英字キーボードでのタイピングが遅いので、coromoranに実装をお願いしようと思ったが、厳しそうだったので私が担当した。→AC
G問題を書いてACしている間に、K問題をtakeoさんが読んでいた。自分も読もうとしたが、疲れておりもう何も英語が読めなかったのでtakeoさんに全て教えてもらった。 何もわからんとのことなので、少し自分も考えてみることにした。
K問題
さっくり問題を要約することが難しいので、問題文を読んでほしい。
辞書順最大のものを求める問題で、この手の問題は貪欲に求めるとよい典型があるのでそのように求める。
貪欲+判定で何も考えずに実装すると、N^3logN になるので、なにかしらの方法でN^2 logN くらいに抑える必要がある。(ちなみに、N^2 log^2Nは通らない)
ウーンと悩んでいたところ、一つのindexに注目して一つ一つ値を調べていくのにNかかるが、そこは二分探索で良いことに気づいたので、そこでNをlogNにすることができた。
しかし、実装がうまくいかず、サンプルが通らず終わってしまった。
ちなみに、同じ方針を神戸大学のもう一チームもやっていて、TLEしたのでサンプルが通っていても無理だった。
判定部分でしゃくとりなどを使用し、logNを落とす必要があった。
合計でABCGの4完 まあまあチームに貢献できたのではと思っている。
懇親会
まさかの高専時代の後輩に遭遇。前から大学を変えると言っており、大学院で大学を変更していた。 indeedがビンゴ企画をやっており、色んな人と適当には話ながらbingoを埋めていった。 好きなプログラミング言語にRustと書いていたが、思いの外おらずさまよっていたらRust勢を発見した。 Rustの同志を見つけたことに対して強い喜びを感じていたら、あとでよく見ると実はwataさんだった(ICFPCのUnagiの人)。ガチプロだった。 きゅうりともダベり、前々から見せたかった等身大きゅうりの画像を見せるミッションに成功したのでOKだった(ゾッとしたと言われた)
3日目
MUSIN, PFN, BitFlyer
どこまで話していいのかわからないため詳細は省略するが、とてもおもしろかった。 どこの会社もやばかったが、PFNがやはり意味不明レベルだった。やばい。 質問が思ったより来ず人事さんとかも困っている感じだったのでひたすら質問攻めにした。
反省点
チームの連携がまだ微妙に不足していた感じはあった。 これは全員大学院生で時間が取れなかったため仕方がないとは思う。 D問題は完全に僕が速攻で思いつかなければならないジャンルだったので、猛反省。精進します。
