精進GW

随時更新していきます。

https://beta.atcoder.jp/contests/code-festival-2017-qualc/tasks/code_festival_2017_qualc_c
xを抜いてまず成立するか確認します。あとはxを適切に挿入していくだけです。

https://beta.atcoder.jp/contests/ddcc2016-qual/tasks/ddcc_2016_qual_c
実は10^9以下の整数の約数は2000個もありませんというやつです。

https://beta.atcoder.jp/contests/soundhound2018/tasks/soundhound2018_c
FLOW。辺の張り方わすれてWA結構出した…

https://beta.atcoder.jp/contests/tenka1-2016-qualb/tasks/tenka1_2016_qualB_b
DP。O(N^3)でいいですが無駄にO(N^2)にした。

https://beta.atcoder.jp/contests/dwacon2017-prelims/tasks/dwango2017qual_c
場合分けしっかりしましょう。

https://beta.atcoder.jp/contests/agc001/tasks/agc001_b
個人的に好き。実はgcd。

https://beta.atcoder.jp/contests/agc002/tasks/agc002_c
「Ai+Ai+1>=Lとなるiが存在する」が必要条件ですが実は十分でしたってやつ。

https://beta.atcoder.jp/contests/agc010/tasks/agc010_b
とりあえず1回の作業で隣通しのmodNの値が1増えるなぁと思ったのでそれを書いて出したら流石にWAでした…6casesWAと割といい線いくけど。でもそういう見方できるようになったのは成長かなぁ。

https://beta.atcoder.jp/contests/agc019/tasks/agc019_b
とりあえず回文をひっくり返したら同じだなぁと思ってたんですが、そこからもう少し条件をゆるくして、端が同じ文字だったらどうなんだろうと考えたらACできました。本質にピント合わせるのがうまくできましたねこれは。

https://beta.atcoder.jp/contests/agc014/tasks/agc014_b
これも全ての点が偶数回出てることが十分だよなぁと思ったら実は必要でもありましたパターンでした。

https://beta.atcoder.jp/contests/agc013/tasks/agc013_b
徐々に頂点を増やしていくやつ。過去に解説見たことあった。

https://beta.atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_a
dpっぽくしようと思ったら解けた。

https://beta.atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_c
10000なら01111になるわけですがS=a1^a2^...a^nとすれば、a1=10000ならS->S^11111となるわけです。つまり、Sを11111...にxorする作業ができるので、あとは0にできるかどうか確かめればよいです。方法はtrivialなものを除けば1通りに定まります。

https://beta.atcoder.jp/contests/code-festival-2016-qualb/tasks/codefestival_2016_qualB_c
kruskalやるだけ。

https://beta.atcoder.jp/contests/cf17-final-open/tasks/cf17_final_c
N<=12は全探索、N>12なら1or0なのでどっちか確かめるのをO(N)でやるという方針をとったんですが1caseだけWAです。これは通せる気がしません…書き直します。

思ったこと
O(NlogN)の計算量なるのって、mergeする時とsortくらいしかなくですか…?
segtreeもmergeしたものを更新していく作業だし、二分探索もsegtree上で値を見ていると言ってもいいですし。
流石にいろいろ反例があると思いますが、割と当てはまっていると個人的に思いました。

Codeforces Round #477 (rated, Div. 1, based on VK Cup 2018 Round 3)

http://codeforces.com/contest/925

Virtualで参加しました。

A
エレベーターと階段の8箇所試せばよいです。いろいろ勘違いしてめっちゃWAした。
B
後ろの方から愚直に使うのが良いです。
C
順列の存在判定ってめちゃくちゃ難しいのはわかりますね。だからおそらくなんかの貪欲法だとわかります。
そこまでくればleading bitに注目すれば思いつけるでしょう。
D
これも10^5頂点のグラフの最短路はdijkstraしかないことに気づけばなんか特殊な性質があるのだろうと思えます。
そうすれば距離2のpathが存在すれば必ず距離4でゴールにたどり着けることがわかるので、あとは場合分けをしっかりしましょう。

コンテスト中はABCしか解けなかったけどDが解けても良かったね。
「できないこと」がわかれば素早く解けるようになるかなぁと感じたコンテストでした。

Combination

Combinationが肝となる問題って数学ゲーとか言われて結構難しくないですかってことでいろいろ考察してみました。

(a+b)Caはa+b人いる中でa人を選び、b人を除外するときの場合の数です。
これは経路数にも言い換えられて、タテaマスヨコbマスのgridで左下から右上に行く際の場合の数とも見ることができます。
さらに経路数といえば禁止領域ですね。途中でy-x>=kとはなっては行けない時の場合の数も簡単に求まります。カタラン数とかこれで求められます。

以上をまとめると、Combinationは2値a,bについての演算で、a+b、a-bの条件が付いている時のみ使用可能ということです。
ここで言いたいことはCombinationは相当単純なシチュエーションじゃないと出てこないということです。なぜなら２値の和と差のみが条件になる数え上げにしか使えないからです。
つまり問題を解いていてこれはCombinationを使う問題だなと思ったら特定の2つの値に注目すればいいということになります。
https://beta.atcoder.jp/contests/agc021/tasks/agc021_e
こういう問題とか解いてみると言っていることが解ると思います。

他にも、
https://beta.atcoder.jp/contests/agc018/tasks/agc018_e
こんな問題がありますが、これを見てわかる通り、経路数は長方形領域の和に強いです。つまり式で言えばa=constの時の和、またはb=constの時の和に強いということです。パスカルの三角形上で見ても同じことが言えます。
でもCombinationのΣとか入る複雑な式になりそうだと思った時はとりあえず経路数で言い換えるのが汎用的な解法だと思います。

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のうち１つ選んでこれを数列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";
}