競プロとゲームをしていません

Codeforces Round #797 (Div. 3)

codeforces.com

ABCDの4完。

⬜🟥⬜
🟥🟥⬜
🟥🟥🟥

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

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

B Array Decrements

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

C Restoring the Duration of Tasks

イベントソート。

イベントソート | Kyopro Encyclopedia of Algorithms

D Black and White Stripe

累積和。

E Price Maximization

解けなかった。

どういう選び方をしても、 \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 _ jk以上最小になるように貪欲に選ぶ。

F Shifting String

解けなかった。

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

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

総括

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

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

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