Codeforces Round #797 (Div. 3)

ABCDの4完。

⬜🟥⬜
🟥🟥⬜
🟥🟥🟥

⬜🟥⬜
⬜🟥⬜
🟥🟥⬜
🟥🟥🟥

⬜🟥⬜
🟥🟥⬜
🟥🟥⬜
🟥🟥🟥

自明。 $a_i = 0$ のときに注意。

イベントソート。

累積和。

解けなかった。

どういう選び方をしても、 $\left \lfloor\frac{a _ i}{k} \right \rfloor$ はコストに含まれる。

$a _ i \mod k$ が重要。

$\left \lfloor\frac{a _ i \% k + a _ j \% k}{k} \right \rfloor$ は1か0。

$a _ i , a _ j$ を $a _ i + a _ j$ が $k$ 以上最小になるように貪欲に選ぶ。

解けなかった。

サイクルごとに分解。サイクルの周期のLCMが答え。

サイクル分解の実装は、DFSして接続した点々をDSUに入れるとよさそう。

ABCDを解くのに1時間9分かかっている。ちょっとコーディングが遅い。

Eは余剰に着目するというアイデアを思いつきたい。

Fは自分の能力でも解けるので解いておきたかった。

hotarunx's diary