ICPC2020アジア横浜地区大会参加記
ICPC2020アジア横浜地区大会に参加しました！
チーム「Simulated Annealing」はpaotan、hexa0611とcirno3153で参加しました。
前日リハーサルは省略。
3:57
起床に成功！
適当に準備して、開催に備えます。
8:30
ZOOMログイン開始―！
8:45
開始前準備、どの順に問題を解くかなどを打ち合わせ。
9:00
まずAをpaotan、Bをhexa0611が読んで、私はCから順に解けそうな問題を読む作業開始。
Dが題意を取れないけど挑めそうだからストック、Gを読めそうなので読み始める。
9:10
AもBも実装が辛いらしい？
Bが貪欲で解けそうか聞かれたので、問題文を読んだら明らかな区間スケジューリングだったのでそう伝える。
9:22
G、和訳終わったけど咄嗟に解法は浮かばないねーってことで、順位表を眺めてみる。
何故かThe atamaがJをFAしていたので、じゃあJ読むかーって読み始める。
9:33
J読んだら自明な木DPだったので、これ実装するかーと解き始める。
9:45
paotanから、AがACできないと聞いたのでデバッグに参加。
三面図が与えられるので該当する図形があるか判定せよって問題だったので、まず立方体で埋めて、0の部分だけくり抜いた図形を判定するのが速いのでは？と伝える。
10:07
Jを投げたら通った、1完。
ABより先にJ通すのギャグでは？
とりあえず、Gも解けそうだったのでそっちを挑む。
10:16
Aが通ったらしいので、Dの翻訳を依頼する。
Bがバグってて通らないらしいので、Bの実装を奪い取って1から実装開始。
10:44
と
を間違えて1RE、if文を1個忘れてて1WAしつつBを通す。
Eを読んでいたhexa0611から答えの二分探索で解けそうと聞いたので読んでみて、やり方を示せたので提案してみる。hexa0611が幾何ライブラリを持っているとのことだったので、和訳が終わっていたDを読んでみる。
ちょっと考えるも、こんなの簡単に解けたらヤバいだろってことでGに戻る。
11:11
UnionFindを使って解ける問題と判明、なんだ難しくないねって言いながら実装開始。
11:20
Cを読んでいたpaotanが和訳を終わらせ、実は命令数が少ないのでは？と予想していたので読んでみる。
10 10 .......... ...#.#.... ..#...#... .#..#..#.. .#.#G#.#.. .#.....#.. ..#####... .......... ....S..... ..........
が思いついたのでこれヤバいのでは？となり、後回しにしようかということで合意。
11:35
Eを実装していたhexa0611がテストケース4の問題を指摘したので、再度考察。
円の中心を含むような多角形だと角度和で良いけど、そうでない場合は最大の角度=残りの角度だねって図を見せて説明する。
12:25
GをAC。
この時点で20位になっていて、すげーって言いながら他の問題を読む。
DPで解けそうなIを私とhexa0611で読んで、これ箱根駅伝DPでは？とか、これARC104-C Fair Elevatorでは？とか言いながら考察するも上手くいかず。
12:40
paotanがHを読んでいて、セグ木で解けそうに見えるというので全員で読んでみる。
素因数ごとに独立に解けないかなーとか、区間の個数ってどうやって求めるんだ……？とか考えても分からず、いったん飲み物を取りに行く。
飲み物をマグカップに補充していると、ふと答えがそのままセグ木に載らないか？って思って考えると載るので、解けますねってなって実装開始。
12:58
実装が軽いので、そのままサクッと提出してAC。
この時点で15位だったので、6完やべー、すげー！！って興奮する。
いや本当にすごくない？正直、25位くらい取れれば健闘かなって思ってたのだけど。
13:05
2問解ける可能性があるのと、同じ問題を3人で考察するの効率悪いかもねってことで分担作業をすることに。
Cはhexa0611が全探索できるかもって判断し、次のように分担することが決定する。
- paotan C問題の入力とコマンドが与えられたとき、SからGに移動できるか判定するコードを書く。
- hexa0611 C問題のコマンド全探索を書く。
- cirno3153 I問題を実装する。
13:25
空間 で時間
のDPは書けたけど、もちろん通らないねーってことで遷移の高速化を考える。
ぐっと睨むと良い感じの方針は思いつくけど、かなり色々とややこしい……。
13:46
paotanが判定コードを組めたのでソースコードを共有する。
13:55
hexa0611 も全探索を実装でき、サンプル1,2を試すと正しそうなので提出する。
残りのサンプルを試しながらお祈りすると、なんとAC！
残りの時間だと何もできないので、順位表を鑑賞し始める。
14:00
終了！
昼食を食べるため、一度解散する。
14;30
それぞれの問題について感想戦を始める。
C問題、hexa0611曰く最大でも6だと思ったから長さ6以下で決め打って全探索したとのこと。
確かに計算量は で済むから良さそうだけど、本当に長さ6以下なのかー？という話になる。
10 10 .......... ...#.#.... ..#...#... .#..#..#.. .#.#G#.#.. .#.....#.. ..#####... .......... ....S..... ..........
のサンプルがあるじゃん、あれどうだったんだろう？って話になったので試すと、次のコマンドが出力される。
6 FORWARD LEFT IF-OPEN 2 RIGHT FORWARD LEFT
……マジ？
丁度6個の命令で終わるらしく、これをエスパーできるのヤバすぎないかって盛り上がる。
14:55
解説放送のお時間。
まぁでも、Iを除いて解ける問題は全部解いたので正直不要ね。
15:51
解説で、制約だとSは一番上の段、Gは一番下の段にあるので～って言ってるのを聞いてあれ？ってなる。
いやその制約があるなら左手法(5命令)で自明じゃん、そんなことある？？？
翻訳したpaotanは追加制約無いって言ってたので騙されてしまった……。
というか上の入力が解けるの、逆に凄くない？
どうなってるんだ……？
16:20
みんな大好きYes/Noのお時間。
eat_iceのエンターテインメント性が高すぎる、ICPCでtourist出しするのヤベー
Simulated Annealingは7完で18位、すごく健闘したと思う！
16:50
最上位6チームのYes/No、見てて楽しいね。
自分たちが届くことは一生無さそうな位置だけど、いつかは企業コンとかで表彰レベルの順位を取りたいね……！
17:10
懇親会のお時間。
7完という望外の結果を得られて、かなり嬉しい気持ちで参加できたね。
前回は2完で自分が戦犯をしていたので、今回みたいにICPCらしいチーム戦ができるのは初めてのはず？
本当にチーム戦って感じで、チーム戦ってこんなに楽しいのか～って気持ち。
今後だとUTPCがチーム戦なので、こっちでもまた楽しくACしていきたいね。
チームメンバーへ: 本日はありがとうございました！
