Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選

https://beta.atcoder.jp/contests/dwacon5th-prelims

アー

A
Nかけましょう。
B
なぜかバグらせた…上からbit決めましょう。
C
なんで思いつかなかったのかなぁ…ちゃんと順番決めて見ていかないからダメ。DとMの数もってしゃくとりすればいいです。

int N, Q;
string S;

void solve() {
	cin >> N;
	cin >> S;
	cin >> Q;
	while(Q--) {
		int k; cin >> k;
		ll res = 0;
		int D = 0, M = 0;
		ll cnt = 0;
		rep(i, 0, k) {
			if(S[i] == 'D') D++;
			if(S[i] == 'M') {
				M++;
				cnt += D;
			}
			if(S[i] == 'C') res += cnt;
		}
		rep(i, k, N) {
			if(S[i - k] == 'D') {
				D--; cnt -= M;
			}
			if(S[i - k] == 'M') M--;

			if(S[i] == 'D') D++;
			if(S[i] == 'M') {
				M++;
				cnt += D;
			}
			if(S[i] == 'C') res += cnt;
		}
		cout << res << "\n";
	}
}

D
わかったけどもっと速く詰められたよなぁ…値が3個だけというのはすぐ気づけたのに、累積和にすぐ言い換えられなかった…。
最大最小は和と交換可能、100回唱えます。
E
これもiteration回そうぜ…
問題自体はめちゃくちゃ面白いです。多項式の係数のgcdってこんな扱いできるのか。

int N;
ll A[MAX_N];

ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a % b);
}

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	sort(A, A + N);
	ll res = 1;
	rep(i, 0, N) MUL(res, gcd(A[i], i));
	cout << res << "\n";
}

C解けていれば赤パフォだったと思うと悔しすぎる。

自分で決めたルールをちゃんと守れていない感。