解けた・解けなかった集 220204

最近競プロ再開しました。

 

解けた問題、解けなかった/解説ACした問題について、示唆があったものメモを書いていくことにします。

解けた方は橙パフォ以上か解法に癖があるもの、解けなかった方は純粋に勉強になったことを書きます。

 

今回は 2/4までにACしたものについて。

 

 

  • ARC134E  Modulo Nim

E - Modulo Nim

赤パフォ900だけど自力で解けて嬉しかったやつ。

 

lose configuration を数え上げる前にまず条件を考える必要があって、特に同じ個数の山がないものとしてよい。

手で実験すると負けパがとても少なく、また (1,), (2,), (4,8) などが負けとわかるけど、それ以上はよくわからない。

そこでコードを書いて実験すると、上記以外の負けパは要素が全て12の倍数であると予想でき、実際それが示せる。

それ以上は法則がわからないが、山の個数が200個以下と小さいので、全探索すれば絞り込める。

あとは各々の負けパに対して山の決め方をカウントするとよい。これは包除原理でそれなりに高速に計算できて、パターン数自体もさほど多くないので、全体でも制限時間内に計算できる。

 

 

  • ABC228H Histgram

H - Histogram

解説AC. まるで方針が立たなかったが、DPするくらいは思いついてもよかった。今回は最終的にデータ構造を使うわけだけど、それが最初から思いつかなくとも、まず解けそうな問題まで噛み砕くことが大事な気がする。

 

とりあえずAについてソートして、近いところ同士を合わせるものとしてよい。正確には、いくつかのAの値を決めて、それらを最終目標に他のAをずらすものとしてよい。なお、一番大きい値は自動的に選ぶ。

(たとえば、A = [1, 2, 3, 4, 5], 選ぶのが[3, 5]なら、1->3, 2->3, 4->5とずらす)

これは局所最適化による状態数削減の一環。

 

そこからDPする。前 i 項での最小化をDP[i]とすると、DP[i]への遷移について、iより前の項のうちどの項までをA[i]まで引き上げるかで遷移が書ける。たとえば A[j+1] から A[i-1] なら、DP[j] + (引き上げる量) + (種類数の増加ペナ) となる。

このままだと遷移が O(i)で全体O(N^2)となってダメだが、計算式をうまく変形すると j ごとに決まる一次関数のx=A[i]での値、という形にできるので、Convex Hull Trickが使えて O(Nlog(N)) か O(N) になる。

 

 

ABC235G Gardens

G - Gardens

空いた庭がOKなら単なる掛け算だがそれはNGなので、「k個の庭が空いた状態での場合の数」を計算して包除原理するとよい。

そしてどのパターンでも、r を固定した S_r[n] = sum_{k=1}^{k=n} kCr という和を求めることになる。これについてはパスカルの三角形を意識すると、S_r[n] がnについて遷移がO(1)のDPで出せるとわかる。

 

ちなみにS_r[n] は確か 、たまごをはしごの段から落として耐久段位を求めるってパズルで、n回実験できて卵がr個まで使えるときの最適手順を求めるときに使えた気がする。