ICPC 2020 Asia Yokohama Regional 参加記

チームHiCoderで参加しました。メンバーはオータム(@autumn_314)とおがーたそん(@Ogtsn99)と私(@kametaro49) 

ちなみに国内予選は65位だった。 

お菓子の処遇

前日のリハまで手を付けませんでした!  

本番

朝早かったけど起床成功。一応ICPCのTシャツを着る。メンバーとはDiscordで通話しながらである。 

スタート!

A問題を見る。中学の技術でやった投影図みたいなシルエットが与えられるから、それが構成可能かどうか判定しろとのこと。英語なので読むのにちょい時間がかかった。

  1. 3方向から見て埋まってるなら埋めることをする。
  2. 今度は逆に埋めたものからシルエットを作成する。
  3. 与えられたものとシルエットが一致すれば構成可能、そうでなければ構成不可。

A問題AC 0:22 17位!

f:id:kametaro49:20210322162039p:plain

B問題を見る。穴あき配列が与えられるから条件を満たすように埋めよとのこと。貪欲でいけそうだという話をして、おがーたそんと並列コーディング。書いてる途中でおがーたそんがB問題AC 0:53

オータムさんが次はJかなという話をする。

C問題を見る。与えられる迷路を解ける最小行数のコードを作れとのこと。GOTOやIFすら存在できるので、こんなに自由度のある問題は全探索以外無理ではという気がする。左手法でもいけそうだと思う。左手法も存在することだしコード行数がそんなに大きくなることはないのではと薄々感じる。とりあえず全探索を書き始める。

TLEの予感がムンムンする。しかし実行時間も10秒まで許されているので、信じて書き続ける。おがーたそんとオータムさんはJを解いている。

  1. コード長を1から順に指定してDFSでコードを生成。
  2. 迷路内でコードを使ってシミュレーション。
  3. Setと状態<位置、方向、コード位置>を用いて、ループを検知したら終了。
  4. ゴールに辿り着いたら答えとして出力。

C問題WA

TLEじゃなくてWA!?と驚きながら問題とコードを眺める。

コード行を0-indexedで提出してしまっていたことに気づく。

修正してこれならTLEやろと提出、C問題AC 1:49

Jは解いてくれそうなのでGを読む。

読んでるとおがーたそんがJ問題AC 2:14 17位!!

f:id:kametaro49:20210322162113p:plain

Gの問題理解にかなり手間取る。オータムさんが一通り問題を読んで考察を入れてくれている。

条件を満たす最小のしきい値を求めなければならない。

しきい値を決めたら、UnionFindのfindとrankを使えば条件を満たすかは判別できることに気がつく。しかし、全ての値を調べるとUnionFindに時間がかかりG問題TLE(2回)しきい値が2分探索の性質を満たしていないことも確認。online dynamic connectivityか?(削除可能unionfind)という話に、java版が見つからないので頓挫。

かなり疲れが溜まっていたので停滞…

おがーたそんがEを書いてて誤差が出ているらしい。2分探索と角度という話なので、確かに!と自分もEを書き始める。が、

TIMEOVER!!

 

結果27位!。順位表的に4完では最上位。でも全員賞があるらしい、やったね!

 

懇親会は疲れと眠気でほぼダウンしていた模様