第5回ドワンゴからの挑戦状 予選
第5回ドワンゴからの挑戦状の予選に出場しました。 本番は残念ながら1完に終わりましたが2問目まで解いたので自分なりの考察を書きます。
A - Thumbnail
入力としてN個の整数が渡されます。
その平均値をN_Aとした時、N_Aとの差が最も小さい整数の番号を出力します。(差が等しいものがある時は番号が最も小さいもの)
この問題は普通に平均値を計算し差を愚直に計算すればよいです。
B - Sum AND Subarrays
入力として長さがNの整数列が渡されます。
N(N + 1)/2個の連続した部分列に対して、部分列の和が美しさとして定義されます。
N(N + 1)/2個の連続した部分列からK個を選び、それらの論理積を取った時の最大値を出力します。
この問題本番では解けませんでした。。。
ここからは解説を聞いた上で自分なりのまとめを書きます。
まず、部分列の個数はO(N2)であるため列挙が可能です。
列挙したものから論理積の最大値を求めるのですが、ここで求められている演算が論理積であることに注目します。
各部分列を2進数として考えます。
2つの2進数の比較は辞書順比較で行うことができます。
よって、求める最大値は辞書順で最大の値ということになります。
辞書順の最大値は貪欲法で求めることができます。
具体的には、bit列の先頭からこのbitを1にすることができるか試していきます。
これは、可能か判定したいbit列をAとしたとき、部分列iの美しさBiに対して(A & Bi) == Aiが成り立つか調べ、成り立つ部分列の数をカウントしそれがK以上であれば可能、K未満であれば不可能とすることで可能です。
求める値は辞書順の最大値であるため、一度1になったbitは最大値でも必ず1になります。
よって、m桁のbit列があるとき、最初はA=100....0からスタートしi桁目が1になるならばそこを1に固定しAを更新しながら1桁目まで処理を行うことで最大値を求めることができます。
今回の問題ではm=40で大丈夫です。
