2020/Practice/模擬国内予選 - ICPC OB/OG の会

JAG Prelim < Challenges | Aizu Online Judge

結果

振り返り

序盤 (A-D)

コンテスト開始後、さかな、おくら、僕がそれぞれ A、B、D を読む。

A、B は特に問題もなく AC 。先に C に取り掛かったさかなが解法を思いつき、後から来たおくらに確認してもらって実装に移る。

一方僕はというと、D の考察が中々が進まず「分かんね〜」と連呼していた。 しばらくして、通常の括弧列における高さ関数(?)を応用した解法を思いつき、正当性が不安になりながらも実装する。 サンプルが通ったので投げると無事 AC で一安心。

その後しばらくして C の実装が終わり AC 。 後から C を読んだが実装が結構面倒そうで、これはさかなが実装して正解だったと感じた。

中盤 (E-F)

D を通した後、おくらと僕が E を読む。読解に苦戦するも、条件が 2-SAT になっていることが分かる。 後は「左端を固定して右端を二分探索すれば $O(NM \log M)$ じゃん」となり、おくらに実装を任せることにする。

E の解法が分かった辺りでさかなが C を通したので、僕と F 以降を読むことにする。 F は露骨に苦行なので、さかながやることに。 G は幾何なのだが、一応 $O(N^3)$ が生えたので僕が実装に取り掛かる。

しばらくして E の実装が終わり、僕が少し確認して AC 。 一方で G の解法に穴がある(多角形内部を突っ切るパスが valid になる)ことに気づいて萎える。

それからしばらくして、F をさかなが AC (FA) 。 チームメイトながら正直「は？」ってなった。怖い。

終盤 (G-H)

残ったのは GH だが、なんか H が通ってるので 3 人で読む。 「後手は期待値が一番小さいのに全振りするから、実質『頂点の期待値の最小値を最大化する問題になる』」というところまでは分かったが、そこから中々進まない。

その裏で、僕が G の解法とその穴をおくらに話す。「多角形と線分の交差判定」を持ってなかったのだが、おくらが実装することに。

その後、さかなが「最大流で解けそう」ということで解法が共有される。 良さそうなのだが、「元のグラフの辺に流れる流量の和が 1 以下」という制約が表現できずに苦しむ。 その後もフローを軸に考えていると、「元のグラフの辺に重み-1 をつければ最小費用流になるのでは？」となる。 しかしそもそも整数フローではないので実装できない。悲しい。

それからかなり長いこと唸っていたが、残り 15 分くらいでさかなの「最大流による解法」を元にした、DP による解法が降ってくる。 急いで実装したのだが、5 分ほど間に合わずに時間切れになった。非常に悔しい。

なおコンテスト後しばらくして、おくらも G の実装が終わったらしい。こちらも惜しいところ。

反省

• 並列コーディング楽しい。
• A-F はかなり良かった。特に F はおかしい。
• H は正直頭が回ってなかったと感じた(さかなに言われるまで、閉路があると 0 になることに気づかなかった)。
• 幾何ライブラリを整理しよう！($n$ 回目)