Dまで四完。Eは大まかな解法は合っていたようなのだけど……。
コンテスト後のツイート
Good Bye 2022: 2023 is NEAR pretestはDまで
— titia (@titia_til) December 30, 2022
A 最小のものを更新
B N,1,N-1,2,...
C 差と小さい方を全列挙。差がx(<=N)で割り切れるものの小さい方の集合がx個あるとダメ
D 個数の少ない数字から決める。残り1個ならそれを採用。残り二個なら片方採用して答え二倍。A[i]=B[i]で残り一個なら答えn倍。
E. Koxia and Tree
解説・解法ツイートなどを見て苦労してAC。特に、このツイートのおかげで理解できました。とりゐさんに感謝。
蝶というより質点として考えていた。xの質点とyの質点が辺の両端にあるとき、辺に方向をつけると、(x+y)/2の質点二つに変化する。
そうやって移動しても、質点が質点をおいこすことがないため、移動した辺以外の辺については、x側の質点の個数やy側の質点の個数は変わっていない。それを利用して答えを計算できそう。
……と、ここまで（Editorialに書いてある内容）はコンテスト中に分かっていた。
問題は、答えにどう反映させるか。
質点がxからx+kに増えるのだから、その差分kと反対側にある個数を掛けたものだけ増える……とか考えて混乱していた。
今回、初期状態での答えが分かるため、差分計算で考えたくなるが、今回はそうしない方が良い。各辺を有向にしたごとに、その辺の寄与を考えていく。
その際、
・x側に質点があり、y側にはなくて、x→yに移動するとき
・x側に質点があり、y側にはなくて、移動しないとき
……
と、一つ一つ場合分けして考えるのが重要。
質点の重さみたいに考えてしまったが、それらはあくまで確率。片側にあるか/ないかの確率が分かっている。なら、あるかないか全て場合分けして考えれば良い。
なんとなくのイメージで考えてしまったのが失敗の原因だった。あるかないかの確率が分かっているのだから、あるときとないときで場合分けして考える、というのは何が既知かを理解していれば自然だった。
0 件のコメント:
コメントを投稿