ganmo::cout

競技プログラミング始めました

Codeforces Round #551 (Div. 2)

こどふぉは２回目でした
青色にこそなれましたが問題の元ネタを取り巻く状況が状況なだけに複雑でした

A - Serval and Bus (500点)

問題: Problem - A - Codeforces
t>s_iでなくなるまでs_iにd_iを足すと、サーバルくんが乗ることのできるバスの時刻がわかる。つまり、t>s_iの場合にs_iにd_i \cdot \mathrm{ceil} (\frac{t-s_i}{d_i})を足したあと、s_iが一番小さいようなiを出力してAC。O(n)。

拙解 (C++14): Submission #52685192 - Codeforces

B - Serval and Toy Bricks (1000点)

問題: Problem - B - Codeforces
投影図の影でないところにレーザーを放って焼くイメージで解ける。式にすると、答えの行列は
{\displaystyle (h_{i,j})_{1\le i\le n, 1\le j\le m} = t_{i,j}\cdot \min \{ b_i, a_j\} }
となる。ブロックが置いてあるところの高さを投影図という制約で絞るように解けてAC。O(nm)。

拙解 (C++14): Submission #52689973 - Codeforces

C - Serval and Parenthesis Sequence (1500点)

問題: Problem - C - Codeforces
括弧列 (Parenthesis Sequence)と言えば '(' で+1して ')' で -1 して累積和が 0 になるかで判定できるのが有名で、これを使う。
狭義prefix（問題文参照）が括弧列として成り立ってはいけないので、累積和の最後の要素以外0になってはいけない。このためにはできるだけ正の方向に足していって0から遠ざかればいいので、自明な '?' (両端とか) 以外はすべて左側に0個以上の '(' を置いて、後の右側はすべて ')' にすればいい。これを貪欲にO(|s|)回試して最後に0になるかどうかを見る。これはBinary Indexed Tree (フェニック木)で累積和とればO(|s|log|s|)で試すことができる。これで得られた括弧列が本当に途中で０にならないかどうかをみて、大丈夫なようなら出力すればAC。O(|s|log|s|)。

…コンテスト本番中は証明なしに出してACになったけど今思えばこれBIT使う必要はないわ
')' だったところを '(' に変えれば総和は+2になるから変える個数O(1)でわかって全体O(|s|)でいけるじゃん…

拙解 (C++14, O(|s|log|s|)解): Submission #52700315 - Codeforces
拙解 (C++14, O(|s|)解, コンテスト終了後): Submission #52736372 - Codeforces

D - Serval and Rooted Tree (1750点)

問題: Problem - D - Codeforces
木は "without cycles"(問題文より引用)、つまりAcyclicで親←子という風なアークを考えると、これはDAGになる！つまり木DPができる。
根ノードに寄与するような最小の葉ノードの数を数えればいい。ということは、
dp_{ノード} := ノードに寄与する最小の葉の枚数
とすると、
\displaystyle dp_親 \gets \begin{cases} dp_親 + dp_子 & 親ノードが\min 操作 \\ \min \{ dp_親, dp_子\} & 親ノードが\max 操作 \end{cases}

とすればよくなる。よって、葉は１枚ずつ、内部ノードは初期値が単位元*1になるように
\displaystyle dp_i = \begin{cases} 1 & ノードiが葉 \\ 0 & ノードiが\min 操作 \\ \infty & ノードiが\max 操作 \end{cases}
としてから、上記の遷移をトポロジカルソート逆順（葉→幹）で行ってdp_根ノードを出力すればAC。O(n)。

拙解 (C++14, コンテスト終了後): Submission #52685192 - Codeforces

E以降

見てません

まとめ

予想通りこどふぉのほうが先に青くなりましたが、こどふぉのほうがレート変動が激しいので色はコンテストごとに点滅しそうです
院試のためにも英語に慣れておくのもよさそうだしコンテストの頻度が上がると楽しいのでこどふぉも（生活リズムが崩れない程度に）やっていきたいですね

*1:こういうのモノイドっていうんでしょうか