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

第5回ドワンゴからの挑戦状予選に参加しました！
第5回ドワンゴからの挑戦状予選旧版
 第5回ドワンゴからの挑戦状予選 beta版

解けた問題だけ解説をしていきますー

要項

第5回ドワンゴからの挑戦状予選
rated 2800
11/24(土) 20:00 ～ 22:00 (120分)
200-400-600-800(500)-1000 (5問)
ペナルティ: 5分

方針

ABCdの3完1部分点を高速に、多分予選は通過できないけどパフォーマンスはかなり良くなるはず

A - Thumbnail

まず、平均点を求めます。
この時、平均点を求めると小数点以下の値で誤差を発生させる可能性があるため、あえて平均点の $N$ 倍を求めます。
次に各 $a_i$ について $Na_i$ と平均点の $N$ 倍との差を求め、差が最小のものを選びます。
計算量は ${\rm O}(N)$ です。

#include<iostream>
using namespace std;
int main() {
	int N, a[100];
	cin >> N;
	int sum = 0; // 平均点のN倍は総和に等しい
	for (int i = 0;i < N;++ i) {
		cin >> a[i];
		sum += a[i];
		a[i] *= N; // N倍することで誤差を消す！
	}
	int diff = abs(sum - a[0]), ans = 0;
	for (int i = 0;i < N;++ i) {
		if (diff > abs(sum - a[i])) { // もし、より差が小さいものを見つけたら更新
			ans = i;
			diff = abs(sum - a[i]);
		}
	}
	cout << ans;
	return 0;
}

まず、連続した数列の和……は累積和なので予め $S_i=\sum_{j=1}^i a_j$ を計算しておきましょう。
累積和が計算されているなら $\frac{N(N+1)}{2}$ 個の部分列を列挙するのも ${\rm O}(N^2)$ でできます。
次に、ビットごとの論理積を計算するという事は、少なくとも $K$ 個の部分列で同一のビットが立っていないと立たせることができません。
逆に、そのようなビットでかつ最も高い位置にあるビットは立たせた方が良いです。
よって、一番上のビット( $N \max(a_i) \leq 10^{12} \leq 2^{40}$ )から順に $K$ 個のビットが立つか貪欲に見ていき、立たせることができるならそれを立たせると良いです。
その時、ついでにそのビットが立たないもの全てを0埋めしておくとバグを防ぐこともできます。
計算量は ${\rm O}(N^2 \log(N\max(a_i))$ です。

C - k-DMC

制約より $Q$ がかなり小さいので、 ${\rm O}(NQ)$ を考えます。
各クエリについて独立っぽいので、1回のクエリについては ${\rm O}(N)$ で解く必要があるようです。
まず、カウンターとして $d = 0, m = 0, c = 0$ を定義します。
そして左から順にみていき、'D'が出てきたら $d$ を1増やします。
次に、'M'が出てきたら、今まで'D'が出てきた個数分だけ $m$ を増やします。すなわち $m += i$ ですね。
次に、'C'が出てきたら $c$ を $m$ だけ増やします。
これは、 $m$ というのは'D'と'C'に囲まれた'M'の個数(複数の'D'と共有して挟まれたならその個数だけ掛けたもの)を指すので、これがそのまま答えに足すべき個数だからです。
また、 $c-a < k$ の制約があるので、最後に $k$ 個前に'D'が出てきたなら $k$ 個前から今の地点までの'M'の個数分だけ $m$ を減らします。
これは、予め'M'について出現個数を累積和で求めておけば ${\rm O}(1)$ で求めることができますね。
以上の操作により、左から順に全ての操作を ${\rm O}(1)$ で求められたので、各クエリについて ${\rm O}(N)$ 、よって計算量は ${\rm O}(NQ)$ となりました。