IMO

解けそうなやつ解いてみました。

2017 5番
N+1要素以上の単調増加列を使って構成する方法をまず考えましたが、うまく行かず。
そのときに数の区間で考える発想が浮かんだので、1-N+1,N+2-2(N+1),...,(N-1)(N+1)+1-N(N-1)のN個に分割してみました。
そうすると数の大小を考えずに区間が同じやつが隣同士になれば良いという条件になるので考えやすくなりました。
ここまでくれば後は楽勝です。先頭からN+1個見れば鳩の巣原理から区間が同じペアが存在します。その区間の全ての数、ペアよりも前に存在した数を全部消すと、残りの数列の長さLはL>=N(N+1)-2N=N(N-1)となります。N-1の場合に帰着できたので帰納法で解けました。

やっぱり対称性の高くしてあげるとうまくいく場合が多いですね。こういう感覚身につけたい。

2015 6番
k+ak≠l+alが意味不明なので言い換えます。すると、
1 <= bk <= 2015を満たす長さmの数列があって、次の操作を繰り返すことと同じになります。
1.bkのうち1つ選んでこれを数列aに追加する。
2.他の要素について全て-1する。
3.bに2015を追加する。
です。m <= 2015であり、mは単調増加なので、あるmで固定して考えます。

(bの長さ)=mとなったところからaに追加された要素の合計をS,Σbk=S'とします。
すると(S+S')next=(S+S')current+(2016-m)となることがわかります。なので問題文のbを2016-mとしてあげて、
Σbk-b=S''とすれば(S+S'')=constとなります。最初はS=0なのでconstはS''に依存します。
あとbは上の操作から作られることを考えると、(m-1)(3m-4030)/2<=S''<=(m-1)m/2が成立するので、
constも同じ条件が成立します。S=S''-constなので|S| <= (m-1)m/2-(3m-4030)(m-1)/2=(m-1)(2015-m)となります。
(m-1)(2015-m)はm=1008で最大で1007^2となるので示せました。

これもmが本質になることを感じ取って、mを中心に議論を展開すれば解ける問題でした。

AGC023

https://agc023.contest.atcoder.jp/

A
map
B
(i,j)と同じでなければならないのは(j+B-A,i+A-B)です。よってB-Aの値だけが重要なのでO(N^3)です。
C
あーなるほどなぁ。

自分の中で全ての問題は貪欲orDPに落とせるって考えていたのが間違えでした。
なのでDPしようしようとずっと漸化式立ててたんですがうまく行かず。
これはいわゆる数学ゲーですね。ちょっと見方を変えると実は式がうまく立てられるパターンのやつです。
必要条件十分条件で攻めるのも数学ゲーの一種だと思っても良さそうです。数学ゲーのポイントはやはり「見方」ですね。

今回の問題は終了するまでの回数Kでまとめられたかが肝となりました。
僕はコンテスト中、ずっとDPしようDPしようと思っていたので、回数Kでまとめるなんて解法としてありえないと思ってしまいました。

全ての問題は貪欲orDPor数学ゲーであると思うのが良さそうですね。

CSA Round #78

https://csacademy.com/contest/round-78/summary/

A
はい
B
set
C
dp[桁][Nより小さいか][桁を始めたか]の桁dp。典型らしい。
D
結合性( (a+b)+c=a+(b+c) )が成り立てばsegtreeにできるというやつ。

例えば
https://yahoo-procon2017-qual.contest.atcoder.jp/tasks/yahoo_procon2017_qual_d
などがある。
http://d.hatena.ne.jp/DEGwer/20131211/1386757368
DEGwerさんのこの記事も役に立ちます。

今回はnodeにV[i][j]:=iからjに行く時の最大コストのようにすればsegtreeを構成できる。

最近2のべき乗で高速化する問題解いてなかったので全く思いつきませんでしたね…。DPテーブルいじったりダブリング考えてたらコンテスト終わりました。(ダブリングは結構いい線ではあったが)

int N;

struct node {
	ll V[5][5];
	node() {
		rep(i, 0, 5)
			rep(j, 0, 5) V[i][j] = -inf;
	}
};

node merge(const node& L, const node& R) {
	node res;
	rep(i, 0, 5) {
		rep(j, 0, 5) {
			rep(k, 0, 5) {
				MAX(res.V[i][k], L.V[i][j] + R.V[j][k]);
			}
		}
	}
	return res;
}

int M, Q;
ll A[5][50010];
node segtree[100010];

node start(int at) {
	node res;
	rep(i, 0, N) {
		rep(j, 0, N) {
			if(abs(j - i) <= 1) {
				MAX(res.V[i][j], A[i][at]);
			}
		}
	}
	return res;
}

void update(int k, const node& v) {
	k += M - 1;
	segtree[k] = v;
	while(k > 0) {
		k = (k - 1) / 2;
		segtree[k] = merge(segtree[k * 2 + 1], segtree[k * 2 + 2]);
	}
}


void solve() {
	cin >> N >> M >> Q;
	rep(i, 0, N)
		rep(j, 0, M) cin >> A[i][j];

	int m = 1;
	while(m < M) m *= 2;
	M = m;

	rep(i, 0, M) segtree[i + M - 1] = start(i);

	rer(i, M - 1, 0) {
		segtree[i] = merge(segtree[i * 2 + 1], segtree[i * 2 + 2]);
	}
	while(Q--) {
		ll a, b, c;
		cin >> a >> b >> c; a--; b--;
		A[a][b] = c;
		update(b, start(b));
		node res = segtree[0];
		ll ans = 0;
		rep(i, 0, N) {
			rep(j, 0, N) {
				MAX(ans, res.V[i][j]);
			}
		}
		cout << ans << "\n";
	}
}

E

べつにそんな難しくはないですね…。
行列Bにtを2^k回作用させた時得られた行列Cについて、
C[0][0]=B[0][0]^B[2^k][0]^B[0][2^k]^B[2^k][2^k]となります。なので、
K回(0<=K<2^(k+1))tを作用させた行列を求めたい時、
K>=2^kなら、Bnext[i][j]=B[i][j]^B[i][j + 2^k]^B[i+2^k][j]+B[i + 2^k][j + 2^k]として、
BnextにtをK-2^k回作用させた行列を求めればよいです。
このBnextを求めるのには2^(2*k)*4回の演算が必要ですが、
今N*M<=5*10^6であり、Bnextは一回の計算でBの半分以下になるので、K'を2^K'<=max(N,M)を満たす最大の値とすれば、
0<=i<2^(K'+1)の全ての場合について求められます。
大きいKの場合は上のbitは無視できるので、結局O(1)/queryで求められます。

int N, M, Q, K; //(1 << K) <= max(N, M)
int ans[2000100];


void pre(int k, int bit, const vector<vector<int>>& A) {
	if(k == -1) {
		ans[bit] = A[0][0];
		return;
	}
	pre(k - 1, bit, A);
	int n = sz(A), m = sz(A[0]);
	int bk = (1 << k);
	int vn = min(n, bk);
	int vm = min(m, bk);
	vector<vector<int>> vec(vn, vector<int>(vm, 0));
	rep(i, 0, vn) {
		rep(j, 0, vm) {
			vec[i][j] ^= A[i][j];
			if(i + bk < n) vec[i][j] ^= A[i + bk][j];
			if(j + bk < m) vec[i][j] ^= A[i][j + bk];
			if(i + bk < n && j + bk < m) vec[i][j] ^= A[i + bk][j + bk];
		}
	}
	pre(k - 1, (bit | (1 << k)), vec);
}

void init(const vector< vector<int> >& A) {
	K = 0;
	while((1 << (K + 1)) <= max(N, M)) K++;
	pre(K, 0, A);
}

int query(int q) {
	q %= (1 << (K + 1));
	return ans[q];
}

AOJ-ICPC埋め

国内予選出るので精進します。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2743&lang=jp

4隅を必ず含む解が存在することが言える。それを元に丁寧に場合分けすればできる。面倒だけど一発AC。

int H, W, N;
ll A[210][210];
ll S[210][210];

ll get(int x1, int y1, int x2, int y2) { //[x1 x2)*[y1 y2)
	return S[x2][y2] - S[x1][y2] - S[x2][y1] + S[x1][y1];
}

bool divide1(int x1, int y1, int x2, int y2, ll m) { //O(1)
	return get(x1, y1, x2, y2) >= m;
}

bool divide2(int x1, int y1, int x2, int y2, ll m) { //O(N)
	bool ok = false;
	rep(i, x1, x2) {
		ok |= (divide1(x1, y1, i, y2, m) & divide1(i, y1, x2, y2, m));
	}
	rep(i, y1, y2) {
		ok |= (divide1(x1, y1, x2, i, m) & divide1(x1, i, x2, y2, m));
	}
	return ok;
}

bool divide3(int x1, int y1, int x2, int y2, ll m) { //O(N)
	bool ok = false;
	rep(i, x1, x2) {
		if(divide1(x1, y1, i, y2, m)) {
			ok |= divide2(i, y1, x2, y2, m);
			break;
		}
	}
	rer(i, x2, x1) {
		if(divide1(i, y1, x2, y2, m)) {
			ok |= divide2(x1, y1, i, y2, m);
			break;
		}
	}
	rep(i, y1, y2) {
		if(divide1(x1, y1, x2, i, m)) {
			ok |= divide2(x1, i, x2, y2, m);
			break;
		}
	}
	rer(i, y2, y1) {
		if(divide1(x1, i, x2, y2, m)) {
			ok |= divide2(x1, y1, x2, i, m);
			break;
		}
	}
	return ok;
}

bool divide4(ll x1, ll y1, ll x2, ll y2, ll m) {
	bool ok = false;
	rep(i, x1, x2) {
		if(divide1(x1, y1, i, y2, m)) {
			ok |= divide3(i, y1, x2, y2, m);
			break;
		}
	}
	rer(i, x2, x1) {
		if(divide1(i, y1, x2, y2, m)) {
			ok |= divide3(x1, y1, i, y2, m);
			break;
		}
	}
	rep(i, y1, y2) {
		if(divide1(x1, y1, x2, i, m)) {
			ok |= divide3(x1, i, x2, y2, m);
			break;
		}
	}
	rer(i, y2, y1) {
		if(divide1(x1, i, x2, y2, m)) {
			ok |= divide3(x1, y1, x2, i, m);
			break;
		}
	}
	rep(i, 0, H) {
		rep(j, 0, W) {
			if(divide1(0, 0, i, j, m)) {
				int x = 0, y = 0;
				while(x <= H && !divide1(0, j, x, W, m)) {
					x++;
				}
				while(y <= W && !divide1(i, 0, H, y, m)) {
					y++;
				}
				if(x <= H && y <= W) {
					if((x <= i && y >= j) || (x >= i && y <= j)) {
						ok |= divide1(x, y, H, W, m);
					}
				}
			}
		}
	}
	return ok;
}

void solve() {
	cin >> H >> W >> N;
	rep(i, 0, H) {
		rep(j, 0, W) {
			ll a; cin >> a;
			S[i + 1][j + 1] += a + S[i + 1][j] + S[i][j + 1] - S[i][j];
		}
	}
	ll lv = -1, rv = inf;
	while(rv - lv > 1) {
		ll m = (lv + rv) / 2;
		if(N == 2) {
			if(divide2(0, 0, H, W, m)) lv = m;
			else rv = m;
		}
		else if(N == 3) {
			if(divide3(0, 0, H, W, m)) lv = m;
			else rv = m;
		}
		else {
			if(divide4(0, 0, H, W, m)) lv = m;
			else rv = m;
		}
	}
	cout << lv << "\n";
}

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2646&lang=jp

dp(l, r, k):=区間[l, r)内でトーナメント表を作るとして2^kが優勝するときの最小変更回数
とすれば区間はたかだかO(M*N)個しかないのでO(M*N^2)で計算できて間に合います。1回dp tableがでかくしすぎてMLEした。
こういうの制約が大きいから貪欲的に考えがちだけど、DPにも頭を働かせられるようになるといいですね。

int N, M, K; //K:=num of interval
pl I[MAX_N];
pi nex[MAX_N];
int D[MAX_N]; //depth
int S[MAX_N]; //-1 or else
ll A[10010], B[10010];

ll dp[MAX_N][31];

void init(ll l, ll r, int k, int d) {
	I[k] = pl(l, r);
	D[k]= d;
	int at = upper_bound(A, A + M + 1, l) - A;
	ll m = (l + r) / 2;
	if(A[at] >= r) {
		S[k] = B[at - 1];
	}
	else {
		S[k] = -1;
		nex[k] = pi(K + 1, K + 2);
		K += 2;
		init(l, m, nex[k].fst, d + 1);
		init(m, r, nex[k].sec, d + 1);
	}
}

ll loop(int at, int s) {
	if(dp[at][s] != -1) return dp[at][s];
	else if(S[at] != -1) {
		ll l = I[at].sec - I[at].fst;
		ll sub = 0;
		if(S[at] > D[at]) {
			sub = (1LL << (S[at] - (D[at] + 1)));
		}
		else if(S[at] <= D[at]) {
			sub = (s == S[at]);
		}
		return l - sub;
	}
	else {
		ll lv = loop(nex[at].fst, s) + loop(nex[at].sec, D[at] + 1);
		ll rv = loop(nex[at].fst, D[at] + 1) + loop(nex[at].sec, s);
		return dp[at][s] = min(lv, rv);
	}
}

void solve() {
	cin >> N >> M;
	rep(i, 0, M + 1) cin >> A[i];
	rep(i, 0, M) cin >> B[i];
	K = 0;
	init(0, (1LL << N), 0, 0);
	memset(dp, -1, sizeof(dp));
	cout << loop(0, 0) << "\n";
}

ARC096

https://beta.atcoder.jp/contests/arc096

C.
Cを全通り試します。

ll A, B, C, X, Y;

void solve() {
	cin >> A >> B >> C >> X >> Y;
	ll ans = linf;
	for(int c = 0; c <= max(X, Y) * 2; c += 2) {
		ll res = 0;
		res += C * c;
		res += A * max(X - c / 2, 0ll);
		res += B * max(Y - c / 2, 0ll);
		MIN(ans, res);
	}
	cout << ans << "\n";
}

D.
折り返す場所を全通り試します。

int N; ll C;
ll X[MAX_N], V[MAX_N];
ll L1[MAX_N], L2[MAX_N], R1[MAX_N], R2[MAX_N];

void solve() {
	cin >> N >> C;
	rep(i, 0, N) {
		cin >> X[i] >> V[i];
	}

	ll vs = 0, l1m = 0, l2m = 0;
	rep(i, 0, N) {
		vs += V[i];
		MAX(l1m, vs - X[i]);
		MAX(l2m, vs - 2 * X[i]);
		L1[i + 1] = l1m;
		L2[i + 1] = l2m;
	}
	vs = 0; ll r1m = 0, r2m = 0;
	rer(i, N, 0) {
		vs += V[i];
		MAX(r1m, vs - (C - X[i]));
		MAX(r2m, vs - 2 * (C - X[i]));
		R1[i] = r1m;
		R2[i] = r2m;
	}
	ll res = 0;
	rep(i, 0, N + 1) {
		MAX(res, L1[i] + R2[i]);
		MAX(res, L2[i] + R1[i]);
	}
	cout << res << "\n";
}

E.
うわー2byte差で落とすというね…。
包除原理します。
そして、dp[i][j]:=iケタ0or1にするときその中で1を含む数の個数がjの時の場合の数とします。
するとdp[i][j]は簡単な遷移で求められて、
あとはiケタ0or1にするときの場合の数は、
ΣC(N,i)*2^(2^(N-i))*2^((N-i)*j)*dp(i,j)となるのでO(N^2)で求められます。
しかし、注意すべきことはpow(2,pow(2,N-i,mod),mod)としないことです。正しくは
pow(2,pow(2,N-i,mod-1),mod)です。2^(p-1)=1だからですね。これさえ気づければ通っていた…。

ll dp[3010][3010];

void solve() {
	cin >> N >> mod;
	C_init(N + 10);

	dp[0][0] = 1;
	rep(i, 0, N) {
		rep(j, 0, N) {
			if(dp[i][j] == 0) continue;
			ADD(dp[i + 1][j + 1], dp[i][j]);
			ADD(dp[i + 1][j], dp[i][j] * (j + 1) % mod);
		}
	}
	ll ans = 0;
	rep(i, 0, N + 1) {
		ll dps = 0;
		ll pown = mod_pow(2, mod_pow(2, N - i, mod - 1), mod);
		ll pp = mod_pow(2, N - i, mod);
		ll d = 1;
		rep(j, 0, i + 1) {
			ll pows = pown * d % mod;
			MUL(d, pp);
			ADD(dps, dp[i][j] * pows % mod);
		}
		if(i % 2 == 0) {
			ADD(ans, (C(N, i) * dps % mod));
		}
		else {
			ADD(ans, mod - (C(N, i) * dps % mod));
		}
	}
	cout << ans << "\n";
}

mod-1の件があったにせよ、解法を詰めるのが遅すぎですね…場合の数の計算に自信が持てないのはなんとかしないと…。

AGC015E: Nuske vs Phantom Thnook

https://agc015.contest.atcoder.jp/tasks/agc015_c

この発想に至るまでが時間かかる気がする。

森の数=木の頂点数-木の辺数と言い換えられれば勝ちです。
あとは累積和適当に取れば通ります。

実装なんですがB,S,E,U,D,L,Rと7つも2010*2010の配列を作ってしまったことは反省するべきですね。
工夫すれば4つとかになるはずです。

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int N, M, Q;
int B[2010][2010]; //blocks
int S[2010][2010]; //num of blocks;
int E[2010][2010]; //num of edge
int U[2010][2010], D[2010][2010], L[2010][2010], R[2010][2010];

void solve() {
	cin >> N >> M >> Q;
	rep(i, 0, N) {
		rep(j, 0, M) {
			char b; cin >> b;
			B[i][j] = (b == '1');
		}
	}
	rep(i, 0, N) {
		rep(j, 0, M) {
			S[i + 1][j + 1] += B[i][j] + S[i][j + 1] + S[i + 1][j] - S[i][j];
			int e = 0;
			rep(k, 0, 4) {
				int nx = i + dx[k], ny = j + dy[k];
				if(0 <= nx && nx < N && 0 <= ny && ny < M) {
					e += B[nx][ny] * B[i][j];
				}
			}
			E[i + 1][j + 1] += e + E[i][j + 1] + E[i + 1][j] - E[i][j];
		}
	}
	rep(i, 0, N) {
		rep(j, 0, M) {
			int u = 0, d = 0;
			if(i != 0) {
				u = (B[i][j] && B[i - 1][j]);
			}
			if(i != N - 1) {
				d = (B[i][j] && B[i + 1][j]);
			}
			U[i][j + 1] += U[i][j] + u;
			D[i][j + 1] += D[i][j] + d;
		}
	}
	rep(j, 0, M) {
		rep(i, 0, N) {
			int l = 0, r = 0;
			if(j != 0) {
				l = (B[i][j] && B[i][j - 1]);
			}
			if(j != M - 1) {
				r = (B[i][j] && B[i][j + 1]);
			}
			L[i + 1][j] += L[i][j] + l;
			R[i + 1][j] += R[i][j] + r;
		}
	}
	while(Q--) {
		int a, b, c, d; cin >> a >> b >> c >> d; a--; b--; c--; d--;
		int e = (E[c + 1][d + 1] - E[a][d + 1] - E[c + 1][b] + E[a][b]);
		e -= U[a][d + 1] - U[a][b];
		e -= D[c][d + 1] - D[c][b];
		e -= L[c + 1][b] - L[a][b];
		e -= R[c + 1][d] - R[a][d];
		cout << (S[c + 1][d + 1] - S[a][d + 1] - S[c + 1][b] + S[a][b]) - e / 2 << "\n";
	}
}

CODE THANKS FESTIVAL 2017,F: Limited Xor Subset

https://code-thanks-festival-2017-open.contest.atcoder.jp/tasks/code_thanks_festival_2017_f

こういうの最近Codeforcesでも見た。

とりあえずdpを書いてみます。
dp[i][a]:=要素iまで見た時xor sumがaになるものの場合の数。
これはO(NK)になってとても間に合いませんが、iを固定して良くみるとdp[i][a]は0またはある値しかとりえません。
なのである値ansとansを取るものの集合Sを管理すればO(KlogK+N)で求められます。

int N, K;
bool S[MAX_N * 2];

void solve() {
	cin >> N >> K;
	ll ans = 1;
	S[0] = 1;

	rep(i, 0, N) {
		ll a;
		cin >> a;
		if(!S[a]) {
			rep(i, 0, (1 << 17)) {
				if(S[i]) {
					S[i ^ a] = true;
				}
			}
		}
		else MUL(ans, 2);
	}
	if(S[K]) cout << ans << "\n";
	else cout << 0 << "\n";
		
}