チームHiCoderで参加しました。メンバーはオータム(@autumn_314)とおがーたそん(@Ogtsn99)と私(@kametaro49)
ちなみに国内予選は65位だった。
お菓子の処遇
前日のリハまで手を付けませんでした!
本番
朝早かったけど起床成功。一応ICPCのTシャツを着る。メンバーとはDiscordで通話しながらである。
スタート!
A問題を見る。中学の技術でやった投影図みたいなシルエットが与えられるから、それが構成可能かどうか判定しろとのこと。英語なので読むのにちょい時間がかかった。
- 3方向から見て埋まってるなら埋めることをする。
- 今度は逆に埋めたものからシルエットを作成する。
- 与えられたものとシルエットが一致すれば構成可能、そうでなければ構成不可。
A問題AC 0:22 17位!
B問題を見る。穴あき配列が与えられるから条件を満たすように埋めよとのこと。貪欲でいけそうだという話をして、おがーたそんと並列コーディング。書いてる途中でおがーたそんがB問題AC 0:53
オータムさんが次はJかなという話をする。
C問題を見る。与えられる迷路を解ける最小行数のコードを作れとのこと。GOTOやIFすら存在できるので、こんなに自由度のある問題は全探索以外無理ではという気がする。左手法でもいけそうだと思う。左手法も存在することだしコード行数がそんなに大きくなることはないのではと薄々感じる。とりあえず全探索を書き始める。
TLEの予感がムンムンする。しかし実行時間も10秒まで許されているので、信じて書き続ける。おがーたそんとオータムさんはJを解いている。
- コード長を1から順に指定してDFSでコードを生成。
- 迷路内でコードを使ってシミュレーション。
- Setと状態<位置、方向、コード位置>を用いて、ループを検知したら終了。
- ゴールに辿り着いたら答えとして出力。
C問題WA
TLEじゃなくてWA!?と驚きながら問題とコードを眺める。
コード行を0-indexedで提出してしまっていたことに気づく。
修正してこれならTLEやろと提出、C問題AC 1:49
Jは解いてくれそうなのでGを読む。
読んでるとおがーたそんがJ問題AC 2:14 17位!!
Gの問題理解にかなり手間取る。オータムさんが一通り問題を読んで考察を入れてくれている。
条件を満たす最小のしきい値を求めなければならない。
しきい値を決めたら、UnionFindのfindとrankを使えば条件を満たすかは判別できることに気がつく。しかし、全ての値を調べるとUnionFindに時間がかかりG問題TLE(2回)。しきい値が2分探索の性質を満たしていないことも確認。online dynamic connectivityか?(削除可能unionfind)という話に、java版が見つからないので頓挫。
かなり疲れが溜まっていたので停滞…
おがーたそんがEを書いてて誤差が出ているらしい。2分探索と角度という話なので、確かに!と自分もEを書き始める。が、
TIMEOVER!!
結果27位!。順位表的に4完では最上位。でも全員賞があるらしい、やったね!
懇親会は疲れと眠気でほぼダウンしていた模様