Dまで四完でした。
E. Playoff Restoration
半分全列挙。
半分全列挙は疑ったのに、半分に分けても混ぜることができない気がしてしまった。
実際は、$\sum{ i \cdot A^{p_i}}$ がハッシュなので、各$A^{p_i}$ごとにindexの総和さえ分かればよく、それならぐっと数が減るので半分全列挙が機能します。
……と、納得してツイートしたらmaspyさんに不要だと指摘されました。（指摘ありがとうございます）
Sample1で考えてみます。
決勝で勝つか負けるかは考えずに半分全列挙をし、勝った場合負けた場合、それぞれについてハッシュ値を求めると、前半については、
・[5, 3, 5, 2]のときのハッシュ値
・[5, 3, 5, 1]のときのハッシュ値
が分かっています。（こうやって列挙する数は$k=5$のとき、$2^15$個）
この、[5, 3, 5, 2]に対応する後半のハッシュがあるかを調べるためには、
・h（問題文で与えられたハッシュ値）- [5, 3, 5, 2]のときのハッシュ値
なるハッシュ値を取るものが後半の列挙した中で、かつ二位ではなく一位を使うものの中に存在すれば良いです。
これ、ハッシュが和として定義されているから、半分のハッシュの和が分かれば残り半分は全体から引くことで求められる……と、当たり前なのだけれど、半分全列挙で上手くできるのはこの性質のおかげで、私が躓いたのはこの部分だったかと思う。
そして、前半と同じように後半も列挙・調査しておけば、これが[1, 5, 5, 3]に対応しているということが分かります。
シンプルな半分全列挙で、ナップザック問題の半分全列挙のように、ソートして二分探索（もしくは尺取り）というようなことも必要ない。
半分全列挙というキーワードを思い付いたのなら、解けなくてはいけない問題でした。反省。
0 件のコメント:
コメントを投稿