A問題「Thumbnail」

とけた。えらいえらい

B問題「Sum AND Subarrays」

考察

コンテスト中の考察

とりあえず部分列が必要なので全部列挙した（このときは累積和しか思いつかなかったけど、普通にループで求められた）。これは$O(N^2)$で余裕
あとは判定するだけ。とりあえず降順ソートして、順番にANDをとるけど案の定WA（これでは簡単すぎるため）。その解法だと、以下のようなケースに対応できない

4 4
2 5 2 5

テストケース1では部分列を全部列挙すると以下のようになる。$K=4$のとき、上から4つを取るため、答えは$0$になってしまう。なので、もっと良い方法を考える必要がある。

(14) 1110
(12) 1100
( 9) 1001
( 7) 0111
( 7) 0111
( 7) 0111
( 5) 0101
( 5) 0101
( 2) 0010
( 2) 0010

ビットごとに考えて、上の方から取っていくと良いのでは？と思った（これが解法に一番近い考察だった）。ビットの性質上、上のビットを優先して立てていけば良さそうなので。でも、この方針ではダメだと思った。数の選び方はたくさんあり、複雑なのである程度列挙みたいな処理が必要だと思った。
なので、とりあえず再帰を欠いてからDPにしようと思った。でも再帰が書けずにコンテスト終了。戻り値有りの再帰が未だに書けない。

理想の考察

とりあえず部分列を列挙する。計算量は余裕があるから普通に実装する。
あとはこれを使って上手いこと最大値を求める。
部分列を降順にソートしてANDを取る方法が直感的に最初に思いつく。だが、この方針は不安がある。最上位にあるビットが常に$K$個以上あるとは限らないので、この方法は良くない気がする。
全通り試すとしても、$_{N^2}C_K$とかになるのかな？とりあえず計算量がヤバイ（つたさんによると、$2^{40} × N(N-1)/2$でもできるらしい）
ANDを取る問題なので、bitで見てみる。すると、MSBから優先的に採用していくべきだとわかる。
ちょっとした証明をしたい。仮に、MSBからを優先的に採用しなかったとする。すると、aビット目は立てられないけど、a-1bit目は立てられるかも知れない。でも、明らかに上のbitであるaビット目を立てた方がお得である。a未満のbitを全て立てても、aビット目を立てた方が大きくなる。よって、MSBから優先的に採用した方が良い。
画像にすると以下のような感じ。MSBを優先的に取った方が明らかにお得。

あとは、そのbitが立っている部分列の個数が$K$個以上あれば、そのbitを立てることが出来る。
その後の操作は、部分列のそのbitが立っていることが前提になる。そのbitが立っていなければその部分列は排除して考える。
考察終了！！

解法

部分列を列挙して配列に格納する
$2^{40}$から順番に$2^0$までのbitを走査する。この順番で見ていって、このbitが含まれる部分列が$K$個以上あれば答えにそのbitを乗せる。
乗せたbitは更新していく

コード

#include <bits/stdc++.h>
using namespace std;

#define int long long

int N, K;
int a[1111];
vector<int> cand;

// 渡されたbitを含む部分列の個数をカウントする
int countMask(int a) {
   int ret = 0;
   for (int x : cand) {
      if ((x & a) == a) { // これ頭良い
         ret++;
      }
   }
   return ret;
}

signed main() {
   // 入力
   cin >> N >> K;
   for (int i = 0; i < N; i++) {
      cin >> a[i];
   }

   // 部分列全列挙
   for (int i = 0; i < N; i++) {
      int sum = 0;
      for (int j = i; j < N; j++) {
         sum += a[j];
         cand.push_back(sum);
      }
   }

   int mask = 0; // これが答えになる。条件を満たすbitをここに付け加えてく
   for (int i = 40; i >= 0; i--) {
      if (countMask(mask | (1LL << i)) >= K) {
         mask |= (1LL << i);
      }
   }

   cout << mask << endl;

   return 0;
}

要点

(x & a) == aでaのbitがxに含まれているかを確認する。
- これ頭良い。
bit系の問題はbitの性質を考える
- 今回はビットの性質を考えればMSBから優先的にビットを立てていけば良いことが分かる。
関数に分ける
- 処理書いてて頭が爆発しそうなら関数に分ける。
- 以下のような部分とか。maskを投げるとカウントして返してくれる関数を書けば、考えることが減る。maskを全列挙する部分と、maskを元にカウントする部分が完全に分かれるので。

for (int i = 40; i >= 0; i--) {
  if (countMask(mask | (1LL << i)) >= K) {
    mask |= (1LL << i);
  }
}

最大値を考える
- $10^9$が$10^3$個ある場合が一番数が大きくなるときで、$10^{12}$になる。
- なので、ループが$2^{40}$からスタートしている
- 後日解き直してみて$2^{35}$でWAになるまで気づかなかった。

感想

最近コンテストの結果ひどいし、昨日のコンテストも散々だったので競プロ辞めようかと思ってたんですが、レートちょっと上がったので続けようと思いました（単純）。
考察はまあわかる。実装頭良いなーって思った。考察分かっても実装が自分で出来なかったため。aのbitが含まれるかを(x & a) == aで判定するのは頭良いと思った。
あと、答えにOR演算子でbitを乗せてくのも頭良いと思った。

第5回ドワンゴからの挑戦状

1完

～僕が弱いんじゃ無くて、みんなが強いんです～

A問題「Thumbnail」

B問題「Sum AND Subarrays」

考察

コンテスト中の考察

理想の考察

解法

コード

要点

感想