ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ICPC2020模擬国内 参加記

とまとさん、るぎうさんと組んでの出場です。

準備

前日はライブラリの印刷をしました。去年はwordに貼り付けて適当に印刷していましたが、読みづらい(シンタックスハイライトが欲しい)上、量も増えてきたので以下のサイトを利用しました。

pazzle1230.hatenablog.com

僕らはオフラインで試しにやってみる、という話になっていたのですが、当日、急遽とまとさんがオンライン参戦に変更になったので、通話等の準備で少しばたばたしました。

流れ

僕がA、とまとさんがB、るぎうさんがCを読みます。
Aをサクっと通したのでとりあえずDを読みました。
Bは情理オリで出た問題に似ているらしく、しばらくしたらACしていました。
Dを読み終わって、C担当のるぎうさんがやりたくなさそうにしていたので考察に参戦すると、適当に正方形の辺をメモしてBFSっぽいことをすればいいね、となりました。これはとまとさんがやるのがよさそう!って二人で決めつけ、Bが終わったとまとさんに押し付けお願いしました。

その後は、とまとさんがCの実装、るぎうさんがD、僕がEを担当することになり、それぞれ格闘していました。
しばらくすると、るぎうさんが考察を終えたらしく実装を開始し、とまとさんもCをズバッと通してくださりました。

とまとさんがEに合流したのとほぼ同時くらいで僕がEの2-SATに気づき、とりあえず3乗解を書いてしまおう、となり実装を開始します。
僕の2-SATライブラリは、2-SAT部分とSCC部分に分かれていたため、とまとさんが2-SATの部分、僕がSCC部分をそれぞれ写経してドッキングしました(今回ならではっぽいムーブでニコニコしていました)。
その後、実装を終えてやっぱり遅いな~って言っていたところで、とまとさんが「二分探索でよくない?」と言っていたので書き直すと、そこそこの速度で実行が終わり、ACできました。しゃくとりは辺の削除ができないから難しいなーって言っていたのに二分探索のことを忘れていたのでちょっと悲しいです(そもそも、setでグラフを持てば辺も削除できます…)。


るぎうさんがDに苦戦しているので、時々声をかけつつ、残った二人は一番通っていたHへ。
(よくよく考えると、とりあえずFを先に見ておいて、どちらか一人をFに縛り付けるのが最適だったかもしれません…)
Hを考えていると、閉路があるときは0になって、あとはDAGパターンがわかればいいねーとなり、いろいろ考えていました。
サンプルが-1/mになっていたので、絶対違うけど出しちゃうか!wって二人で笑いながら出し、もちろんWA。その後しばらく、Hでペナを吐いたチームが自分達だけだったので少し恥ずかしくなりました…

Dがやばそうなので駆けつけると、どうやらテストケースに対し、1つだけ明らかにおかしい答えがでていました(文字列をリバースして解いても答えが同じになるはずなので、assertを入れていたそうですが、それにひっかかるケースが1つだけあるとのこと)。
そのケースは長すぎてデバッグ不可能だったので、自分が長さ18以下で全部の文字列を列挙するコードを適当に生成しつき合わせてみます。
長さが13以降の文字列に対し、なぜか上記のassertで落ちるケースが存在していましたが、どうやら、元の文字列とリバースした文字列の答えのmaxが、正しい答えになっているみたいでした。
H問題でペナを出してハイになっていた僕が「とりあえず、maxで出してみませんか?w」と言って、るぎうさんに無理やり提出させると…なぜかAC(?????????)。
よくわかりませんが、これでEまでの5完になり、そこそこの順位になりました。

最後は全員Hに集合して、この手の問題に強そうなるぎうさんが解くのを横で眺めて三人で力を合わせて考察していましたが、時間も無く途中で終わりました。

結果

対象チームの中で16位でした。この調子でいけば、自分の大学からはうちのチームと、後輩チームが1つ抜けるみたいです。わーい。

f:id:emtubasa:20201025235015p:plain

終わり

並列実装が結構あったので恩恵はやっぱりでかそうです。昨年弊学トップチームのメンバーだった先輩二人にキャリーしてもらうのは楽しい!