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でグラフを持てば辺も削除できます…)。

https://twitter.com/emtsu_ba/status/1320278050727055360

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

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

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