WBC004 - sapphire15の日記

mario.exout.net

全完2位でした。今までで一番難しかった。

f:id:sapphire15:20210319000018p:plain

A. 79Gold

なんかタイトルが動いて笑った。解法は全体の3割が何人かを計算して、はい。

B. Linear Code

奇跡的に線形符号の性質を知っていた。答えは $\min \lbrace \mathrm{popcount}(a\oplus b)| a, b \in \lbrace C_i\rbrace , a\neq b\rbrace$ だが、線形符号であるという性質を使うと $a\oplus b\in \lbrace C_i\rbrace$ なので、 $a\oplus b = 0 \Leftrightarrow a = b$ に注意して、求めるべきは $\min\lbrace \mathrm{popcount}(C_i) | C_i \neq 0 \rbrace$ 。*1

ここまではよかったが、popcountを求めるときに__builtin_popcountllでなく__builtin_popcountを使って1WA。

なんか202点とれるらしい。（競プロ中に謎解きを始めるな）

C. Blurred Numbers

正規表現が読めるなら正規表現を見た方がわかりやすいかも。 1000の位、100の位、10の位、1の位がどこで区切られるかを全探索する。各位は空文字列でもいいことに注意。最初?がI, V, X, L, C, D, M以外になることはあるかのclarを送ろうとしたけど調べたら、そもそもローマ数字は基本3999までらしい。

D. Photosynthesis

光合成をするのに必要なコストは初めに各 $E_i$ から $C$ を引いておけばいい。これによって、 $E_K$ を含む区間で、その和が最大のものが求める問題になるが、これは累積和を使って $\Theta(N)$ で処理できる。

...がデバック出力消し忘れ+オーバーフローで4WA...

E. Link

見た目がごついが、よーく見るとギャグ。

制約から最初の状態はある１つの連結成分に含まれるノード以外はすべて次数は0。このことに気をつけると帰納的に、すべてのタイミングである１つの連結成分に含まれるノード以外はすべて次数は0で、追加されるリンクに繋がるノードのうち片方は必ずその連結成分に含まれるノード、もう片方は等確率で選ばれたノードであることが分かる。よって、最初の状態の連結成分のサイズが分かれば、時刻 $t = L$ にネットワークが連結である確率がdpで計算できる。( $dp[i][j] = (時刻iに連結成分の大きさがjである確率)$ ) したがって、最初の状態での連結成分の大きさごとの場合の数が分かればよく、これは連結成分の大きさを $K$ として、 $_{K(K+1)/2 + M_0 - K}C_{M_0-K+1}$ で計算できる。（自由に割り当てられるリンクが $M_0-K+1$ 個、割り当てる場所が $K(K+1)/2$ 個なので）

計算量は $O( (M_0 + N_0L)\min(N_0, M_0) )$

F. Maximum Flaw Problem

まず、条件を満たす流れ方が存在するかを考える。 1番目のタンクから考えるとすぐ次のタンクには流せるだけ流す必要があり、余った分も可能な限り他のタンクに回せばいい。このことを踏まえて、割れ目が最大になるようなタンクとその流出量を決め打つと、決め打ったタンクについてのみ流出量を減らして上と同じようにすればそれが実現可能かどうか判定できることが分かる。これをすべてのタンクについて二分探索すれば、計算量は $O(N(N+M)\log\max{C_i})$ で十分高速となる。

全体を通しての感想

どれもなかなか歯ごたえがあって面白かった。WBC005も期待しています！

あとブログ書くのってとても疲れる...

*1:証明が不十分ですが気持ちだけ。あとは0000......0が必ず含まれるので...という感じです