Codeforces Round 1013

スポンサーリンク

A. Olympiad Date

個数を比較.

B. Team Training

ソート列を連続部分列に分ける形としてよいことが証明可能.最大値側から貪欲に連続部分列をとっていく貪欲.

C. Combination Lock

偶数のときは sum を考えると不可能.そうでないとき $A[i] = -i \bmod{N}$ でよいです.

Just a moment...

D. Place of the Olympiad

二分探索.幅の上界 $n$ を決めると,貪欲に周期 $n+1$ で置いていく場合に置ける個数が最大になります.

E. Interesting Ratio

単に $(a,ap)$ の形のものです.$a$ または $p$ ごとに数える.

F. Igor and Mountain

dp. 区間和で置き換える形になるので累積和を用意します.

G. Gleb and Boating

$s>K^2$ なら,まずゴールから距離 $K$ 未満のところに進んだあと,左に $1$ 回以上 $K-2$ 回以下進んで $\mod K-2$ での値を調整すれば,$K-2$ を達成できます($K=2$ は例外).

よって $s<K^2$ としてよく,この場合愚直な dp が高速です.私の最悪計算量見積もりは $O(K^3)$ ですが,$s$ が大きいとその分少ない反復で答が見つかってしまうため,めちゃくちゃ高速です.計算量オーダーが落ちていても不思議ではないと思いましたが,解説でも $O(K^3)$ しか証明されていませんでした.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました