Cまで三完と悲惨な出来。
D. Paths on the Tree
解法ツイートを見てAC。本番中1500人近くも通していたから簡単なのかと思ったら、解法も実装も難しくてびっくりした。
・各頂点の重複度の最大値と最小値が高々1しか離れない
と気付くのがポイント。
これは直観的にそうだよね、と思いたい。
頂点xの重複度がyで、子の数がcのとき、xの子たちの重複度は、y/cの切り捨てか切り上げになる。これを繰り返しても、（頂点1の重複度である）kを、pathをたどったとき現れる子の数c_1, c_2, ...の積で割ったものの切り捨てまたは切り上げになる。割り算の式から不等号を導けば、証明できたが、そんなことをしなくてもまあ直感的に（あるいは知識として）正しいと分かっておきたいもの。
これを利用して木DPすれば解けるのだが、実装もなかなか大変だった。
E1. Joking (Easy Version)
解法ツイートを見てAC。
0, 1, 2の3要素が残ったとして、
・｛1,2｝を聞く
→”NO"なら{1}を聞く
→"YES"なら{1,3}に、"NO"なら{2,3}に絞れる
→"YES"なら再度{1,2}を聞く
→"YES"なら{1,2}に絞れる。"NO"なら最初に"NO"が来たときと同じ手順を踏む
とすれば三回で2/3くらいになってACできる。
試行錯誤するしかないけれど、Aと￢Aを質問するのは意味が変わらない、ということには早く気付くべきだった。そうすれば、三等分するという方針には早くたどり着けたと思う。（が、三等分してからも難しい。コンテスト中も三等分することは一応考えたけど、その後が思いつけていないので……）
0 件のコメント:
コメントを投稿