SRM 339 div1 level3

ポイントは、起点となるランクの人を決めた時、その人が最大金星を取れたとして、更に負けるべき人も最大金星を取れて・・・というツリー探索を、常に上位のランクの人から最大金星をつぶしていくようにすること。そしてつぶせればその人は起点となりえ、つぶせなければその人が優勝することは不可能。最上位を負かせる人から勝負していかないといけないので、常にランク順にソートしてランクの上のものからサーチしなければいけない。常に次のレベルの枝に移る時にＡｒｒａｙ．ｓｏｒｔしてみる。

なるべくランクの低い人を起点するよう調べなければいけないが、最低ランクから順に調べると2^16かかる。ソートしていることを考慮すると間に合わない。

なるべくランクの低い人を探すということは、ソートされた配列をサーチするのと同じであると気付けば、バイナリサーチすればよい。i=2^n番目から始めて、i番目の人が起点になりえれば、次はi = i | 2^(n-1)番目の人、とサーチしていけばn回の試行でよい。上記のArray.sortは全く問題なくなる。

既存の配列をサーチするときだけでなく、引数を順にインクリメントしながら関数を実行して最大／最小の引数を求める場合などでもサーチのアルゴリズムは使えることを思い出す。また、バイナリサーチの実装も覚えておく。

• 最大金星の範囲内のものが更に最大金星をとって・・・と範囲の重なりでどんどん範囲を広げていくものをinterval treeというものらしい。
• 消去法でつぶしていく時は、先からつぶしていくか手前からつぶしていくか考えないとコンフリクトする
• i = i | 2^(k-1)番目の要素と比較してバイナリサーチを実装
• 比較は単に既存のデータの比較ではなく、関数の実行結果の比較でも使える