Codeforces Round #577(Div.2) A~D メモ

Codeforces Round #577(Div.2) のバチャをしました。( 11/16 )

Dashboard - Codeforces Round #577 (Div. 2) - Codeforces

ABCD の 4完 ( 1:51 ) でした。

A. Important Exam

題意を理解するのに時間がかかりました。各問題に対して最も多い解答が正答だったことにすれば良いです。

B. Zero Array

これ、GP 2 で見たことがある！全ての要素を 0 にできるための必要十分条件は、1. 要素の総和が偶数、2. 要素の最大値が総和の半分以下、です。

C. Maximum Median

まず数列を昇順にソートします。操作を行う要素は後ろの \( \frac{N+1}{2} \) 個だけで良いです。それらを抜き出して、新たに数列 b を作ります。i = 0 から順に、\( (i+1) * (b _ {i+1} - b_i) \) ずつ \( b_0 \) から\( b_i \) に足していきます。このときにその分だけ k を減らしていきます。途中で k が足りなくなったらその時点で、\( b_i + \lfloor \frac{k}{i+1} \rfloor \) を答えとします。最後まで k が足りた場合は、\( b_{\frac{N+1}{2} - 1} + \lfloor \frac{k}{ \frac{N+1}{2}} \rfloor \) が答えです。

D. Treasure Hunting

かなりしんどかったです。見た瞬間に、Grid 上の DP がしたくなりますが、制約を見て一旦落ち着きます。下移動ができないので、その行にある宝物を全て拾ってからでなければ上に移動できません。このとき、全ての宝物を効率よく拾うと、最後に拾う宝物は一番左か一番右になるとわかります。最後に宝物を拾った位置から上の行に移動する際には、その宝物がある列から右を見たときに最も近くにあるsafety colmun か、左を見たときに最も近くにあるsafety column から上に移動すればいいことがわかります。これは二分探索で高速に求まります。各行で、最後に拾う宝物は高々 2 通りなので、上に移動する列は高々 4 通りになります。よって、
dp[i][j] := 下から i 行目までの宝物を全て拾い終えて、左から j 列目にいるという状態になるまでに移動した距離の最小値
という DP をすれば良いです。最後の行では、safety colmun に移動する必要が無いことに注意してください。

これ実装するの？嫌なんだけど、という気持ちになりながら実装し、WA を出してはバグを直して再提出を繰り返すこと 5 回、最終的には b がソートされていない、というバグを直して再提出したら通りました。かなりこどふぉっぽさを感じました。ソートしておいてくれ〜〜

E.

D で力と時間を使い果たした上に、インタラクティブだったので、投げ出しました。本番の Rated 内正解者数 0 でわろた。