Cまで三完。D、Eを考えていたが解けずに終了。ここまではっきり失敗したのは久しぶりな気がする。
D. Lost Tree
「木は二部グラフ」というキーワードすらほとんど浮かんでいない。
クエリの回数がn/2というところから、二部グラフは考えるべきなんですよね……。
そのキーワードを思い付くことが重要で、その後は、一回目のクエリで二部グラフのどちらに属しているか判断できる、と気付くところがポイントですね。
二部グラフを使おうと思いついていたとして、そこで詰まっていた可能性はありそう。
E. Lost Array
全ての要素についてクエリで聞いた回数が奇数回になれば良い、というのは分かった。では、それが実現できる最小の回数は？ というところで詰まった。
なんか条件（1の個数や3の個数を調べて……みたいな）がないかと考えていたけど、上手くいかず終了。
実際は、もっと愚直に構成できるか試してみるべきだった。
ただ、毎回それをやっていると、$k=n-1$のときにTLEしてしまう。このときは、n回聞けば良いと分かるので、場合分けしてやればACできた。
公式解説は（理解できていないが）もっと賢い方法でやっているようだけど、上記の方法はコンテスト中に考えたことをまとめただけなので、コンテスト中に通すことは可能だったはず。
計算量を気にする前に、愚直なやり方で間に合わないかを試してみるべきだった。
0 件のコメント:
コメントを投稿