Eまで。ただし、Gは典型だったようなので、ちゃんと復習したい。
コンテスト後のツイート
D 同じプログラムの次の位置へ反映させるDP、かと思いきや、一つ前に反映させて良い。
— titia (@titia_til) February 27, 2023
E ある行/列で塗られているマスは連続してなくてはダメ。そうなるよう処理した後、間を結ぶよう最低限のマスを塗り、また同じ処理をする。
F. Halve or Subtract
解説AC。
難しいけれど、そこそこ時間があったのだから解きたい問題だったなぁ。
Aを大きい順に並び替えたとき、
・halve and subtract → halve → subtract →halve → 何もしない
という順序になるので、最初の二つの区間の長さを全探索する。
まず、
・subtractした後、halveするのは無駄
を押さえた上で、
・何もしない区間があるとすれば、一番小さい部分
と気付かなくてはいけない。
その上で、
・残りの区間でsubtractする部分は、連続な箇所になる
と気付くのが重要。
これは、bの前後が一番subtractの効果が大きいと気付けば直感にも適する。
はじめから上記に気付くのは難しいが、二乗が通る制約なのだから、何かの区間と何かの区間を全探索できないか？ と考えていけば気付けたかもしれない。
G. Count Voting
解説AC。
理解してしまえば確かに典型なのだが、解説を見て包除原理というキーワードを知っても理解するまでなかなか苦労した。
包除原理を使う。
まず、チームごと、投票する人が決まっている場合を考えよう。
このときは、「k人以上同じチームに投票した場合の数」を求めると、包除原理を使って答えが求められる。（包除原理を使うときは、「～以上」または「～以下」の数え上げをすることになるので、そういう数え上げができないか考えるのが大事そう）
k人が同じチームに投票し、残りの人の投票先がチームごとにx票、y票だった場合、残りの人の投票先の決め方は、$(n-k)!/(x!*y!)$のようになる。分子は後からかけることにし、分母の部分をDPで求める。
ただし、同じチームから複数人が自分のチームに投票する場合は、「チームの中で誰を選んだか？」を考慮しなくてはいけないことを忘れずに。
チーム内に複数投票先がある場合は、上記のことを各チームごとに行う。
そして、そのDP結果をmergeしていけば（畳み込みも使えるが、今回は必要ない）最終的なDP結果を求めることができる。
0 件のコメント:
コメントを投稿