精進7/2

https://beta.atcoder.jp/contests/arc100/tasks/arc100_a目AC。中間値でもいいし、普通に全通り試すのもよし。
https://beta.atcoder.jp/contests/arc100/tasks/arc100_b目AC。にぶたんしなくても、しゃくとりしながらdpすれば解けます。K区間ならO(NK)ですね。
https://beta.atcoder.jp/contests/arc100/tasks/arc100_c高速ベータ変換あまり使う機会ないのでこういう問題はうれしい。基本は要素0から順番にdpしていく感じです。

精進6/23-30

DP

https://agc022.contest.atcoder.jp/tasks/agc022_c面白い。場合分け系と思ったけど違った。前処理した後、大きいkから使う必要があるか見ていく。
https://agc006.contest.atcoder.jp/tasks/agc006_dやっぱり難しく考え過ぎだよなぁ…1が使えない→2で置き換えて良いとして考えていくと思ったがにぶたんでもっと簡単に解ける。
https://agc006.contest.atcoder.jp/tasks/agc006_e必要十分条件かなぁと思ったらそうだった。置換と反転が重要です。
https://agc023.contest.atcoder.jp/tasks/agc023_dこれは超良問。端をよく考えると再帰的に解ける。
https://arc068.contest.atcoder.jp/tasks/arc068_d端からとった数で場合分けをしてO(N^3)のdpを改善すればいい。
方針として再帰or必要十分条件を突き通せばどんな問題でも解ける気がしてきた。

精進6/21

久しぶりです

https://beta.atcoder.jp/contests/arc098/tasks/arc098_bえー思いつきませんでした。bitがかぶらないことが必要十分。
https://beta.atcoder.jp/contests/arc098/tasks/arc098_c最小値固定すれば、長さk以上の区間から数を取っていく問題になります。
https://beta.atcoder.jp/contests/agc024/tasks/agc024_b連続している数の最長部分列を見つければ良いことになります。
https://beta.atcoder.jp/contests/agc008/tasks/agc008_c丁寧にやればいいです。
https://beta.atcoder.jp/contests/agc022/tasks/agc022_b30000に対して20000というのがヒントです。2と3の倍数で構成します。
https://beta.atcoder.jp/contests/agc024/tasks/agc024_c数列をうしろから見ればわかりやすいです。
https://beta.atcoder.jp/contests/agc025/tasks/agc025_bnCa*nCbの言い換えが本質です。少しむずかしい。
https://agc025.contest.atcoder.jp/tasks/agc025_c
わかりましたがめっちゃこんがらがりました。普通に難しくないか?
まず問題を緩和するという発想がなかったです。N個の区間を使うのではなく、N個以下の区間を使うとします。
そうすればLi,Li+1,Ri,Ri+1に満たすべき不等式がありますが、基本的にはΣLi-ΣRiを最大化する問題になります。そうすれば貪欲に取っていけば良く、同時に不等式の条件も満たします。

codeFlyer （bitFlyer Programming Contest）

こういうセット辛すぎないか?

AB
はい
C
ちょっと詰まるよね。とりあえずjを固定して雑に数えて引くんだけど、引く時はしゃくとりが使えます。
D
累積和やるだけ。全然綺麗な方法思いつかなかった…。imos法もバグらせまくった…

ll H, W;
int N, M;
int B[2010][2010];
int D[2010][2010];
int XA[2010];
int YA[2010];

void solve() {
	cin >> H >> W;
	cin >> N >> M;
	rep(i, 0, N) {
		string str; cin >> str;
		rep(j, 0, M) {
			if(str[j] == '#') B[i][j] = 1;
		}
	}
	bool found = false;
	rep(x, 0, N) {
		rep(y, 0, M) {
			if(B[x][y]) {
				found = true;
				ll x2 = x + min(H - N, (ll)N), y2 = y + min(W - M, (ll)M);
				if(H - N + 1 > N + 1) { //xhamidasu
					XA[y + 1]++; XA[y2 + 2]--;
				}
				if(W - M + 1 > M + 1) { //yhamidasu
					YA[x + 1]++; YA[x2 + 2]--;
				}
				D[x + 1][y + 1]++; D[x2 + 2][y2 + 2]++;
				D[x + 1][y2 + 2]--; D[x2 + 2][y + 1]--;
			}
		}
	}

	if(!found) {
		cout << 0 << "\n"; return;
	}
	else {
		ll res = 0;
		rep(x, 0, 2 * N) {
			rep(y, 0, 2 * M) {
				D[x + 1][y + 1] += D[x + 1][y] + D[x][y + 1] - D[x][y];
				res += (D[x + 1][y + 1] > 0);
			}
		}
		rep(y, 0, 2 * M) {
			XA[y + 1] += XA[y];
			res += (XA[y + 1] > 0) * max(H - 2 * N, 0ll);
		}
		rep(x, 0, 2 * N) {
			YA[x + 1] += YA[x];
			res += (YA[x + 1] > 0) * max(W - 2 * M, 0ll);
		}
		res += 1ll * max(W - 2 * M, 0ll) * max(H - 2 * N, 0ll);
		cout << res << "\n";
	}
}

E
multisetやるだけ。これもめんどくさい…

ll Y, W, D;
int N, M;
ll A[110];
map<ll, int> S;
vl vec[MAX_N];
ll res;

ll bet(ll nd, ll d) {
	if(1 <= d - nd - 1 && d - nd - 1 <= D) {
		return d - nd - 1;
	}
	else return 0;
}

void del(ll d, ll e) { // S is bigger than 1
	S[d]--;
	if(S[d] == 0) {
		auto at = S.lower_bound(d);
		if(at == (--S.end())) {
			auto p = at; p--;
			res -= bet(p->fst, at->fst);
		}
		else if(at == S.begin()) {
			auto p = at; p++;
			res -= bet(at->fst, p->fst);
		}
		else {
			auto pp = at, np = at; pp--; np++;
			if(bet(pp->fst, np->fst) == 0) {
				res -= bet(pp->fst, at->fst);
				res -= bet(at->fst, np->fst);
			}
			else res++;
		}
		S.erase(d); res--;
	}
	d += e;
	S[d]++;
	if(S[d] == 1) {
		auto at = S.lower_bound(d);
		if(at == (--S.end())) {
			auto p = at; p--;
			res += bet(p->fst, at->fst);
		}
		else if(at == S.begin()) {
			auto p = at; p++;
			res += bet(at->fst, p->fst);
		}
		else {
			auto pp = at, np = at; pp--; np++;
			if(bet(pp->fst, np->fst) == 0) {
				res += bet(pp->fst, at->fst);
				res += bet(at->fst, np->fst);
			}
			else res--;
		}
		res++;
	}
}

void solve() {
	cin >> Y >> W;
	cin >> N >> M >> D;
	rep(i, 0, N) {
		cin >> A[i]; A[i]--;
		S[A[i]]++;
	}
	rep(i, 0, M) {
		ll a, b;
		cin >> a >> b; a--; b--;
		S[a * W + b]++;
		vec[b].pb(a * W + b);
	}
	if(N + M <= 1) {
		rep(i, 0, W) cout << N + M << "\n";
		return;
	}
	res = sz(S);
	ll prev = -linf;
	for(pl a : S) {
		res += bet(prev, a.fst);
		prev = a.fst;
	}
	rep(i, 0, W) {
		cout << res << "\n";
		rep(j, 0, N) {
			del(A[j]++, 1);
		}
		rep(j, 0, sz(vec[i])) {
			del(vec[i][j], W);
		}
	}
}

こういうコンテストで勝てるようになったらすごい強くなれそうだけどなぁ。

Codeforces Round #483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov!]

Math

http://codeforces.com/contest/983

A
えーABCの中で一番手間取った。QとBの最大公約数gをとってQをgで割ることを繰り返す。こういうの苦手。
B
dpしてまたdp
C
dp[i][j][k][l][m][n]:=i番目の人までみて、場所jにいる。エレベーターに乗っている人はk,l,m,nである時の最小コストとやると、2*10^8となって辛いです。しかし、i番目の人が乗った場合行き先がbiの人が必ずいるので、それを利用するとnを10試す必要がなくなって2で大丈夫になります。これで2*10^7*2で通ります。2*10^8/(4!)が通ってしまうのは少し解せない…。コードがだいぶエグい。

int N;
int A[MAX_N], B[MAX_N];
int dp[2010][9][10][10][10][2]; //i,at j,floor at; k, l, m floor to visit, B[i], visited?

void solve() {
	cin >> N;
	rep(i, 0, N) {
		cin >> A[i] >> B[i];
		A[i]--; B[i]--;
	}
	rep(i, 0, N + 1) {
		rep(j, 0, 9) {
			rep(k, 0, 10) {
				rep(l, 0, 10) {
					rep(m, 0, 10) {
						rep(n, 0, 2) {
							dp[i][j][k][l][m][n] = inf;
						}
					}
				}
			}
		}
	}
	dp[0][A[0]][9][9][9][0] = A[0];
	//i, j, k, l, m, n
	rep(i, 0, N) {
		rep(k, 0, 10) {
			rep(l, 0, 10) {
				rep(m, 0, 10) {
					rep(n, 0, 2) {
						rep(j, 0, 9) {
							if(dp[i][j][k][l][m][n] == inf) continue;
								// debug(i, j, k, l, m, n);
							if(k == 9) { //visited
								MIN(dp[i + 1][A[i + 1]][B[i]][l][m][0], dp[i][j][k][l][m][n] + abs(A[i + 1] - j));
							}
							else {
								MIN(dp[i][k][9][l][m][n], dp[i][j][k][l][m][n] + abs(k - j));
							}

							if(l == 9) {
								MIN(dp[i + 1][A[i + 1]][k][B[i]][m][0], dp[i][j][k][l][m][n] + abs(A[i + 1] - j));
							}
							else {
								MIN(dp[i][l][k][9][m][n], dp[i][j][k][l][m][n] + abs(l - j));
							}

							if(m == 9) {
								MIN(dp[i + 1][A[i + 1]][k][l][B[i]][0], dp[i][j][k][l][m][n] + abs(A[i + 1] - j));
							}
							else {
								MIN(dp[i][m][k][l][9][n], dp[i][j][k][l][m][n] + abs(m - j));
							}

							if(n == 1) { //visited
								MIN(dp[i + 1][A[i + 1]][k][l][m][0], dp[i][j][k][l][m][n] + abs(A[i + 1] - j));
							}
							else {
								MIN(dp[i][B[i]][k][l][m][1], dp[i][j][k][l][m][n] + abs(B[i] - j));
							}
						}
					}
				}
			}
		}
	}
	int res = inf;
	rep(i, 0, 9) {
		MIN(res, dp[N - 1][i][9][9][9][1]);
	}
	cout << res + 2 * N << "\n";
}

Codeforces Round #482 (Div. 2)

Segment Tree

http://codeforces.com/contest/979

順位はそんな悪くないんですが…

A
n=0〜
B
奇数偶数やろ…となるんですが違います
C
えぇ…
D
追加は約数個のオーダーだし、答える時は、segtreeっぽく範囲を狭めていきます。問題文が無駄に複雑。やめて。
考察は一瞬でしたが、なかなか実装が辛かった。

int Q;
set<int> S[100010];//can be divisible by i

void loop(const vector<pi>& vec, int at, int x, int cur) {
	if(at == sz(vec)) {
		S[cur].insert(x);
		return;
	}
	rep(i, 0, vec[at].sec + 1) {
		loop(vec, at + 1, x, cur);
		cur *= vec[at].fst;
	}
}

void add(int x) {
	vector<pi> vec;
	int tx = x;
	for(int i = 2; i * i <= tx; i++) {
		if(tx % i == 0) {
			int cnt = 0;
			while(tx % i == 0) {
				tx /= i;
				cnt++;
			}
			vec.pb(pi(i, cnt));
		}
	}
	if(tx != 1) vec.pb(pi(tx, 1));
	loop(vec, 0, x, 1);
}


int get(int k, int y, int x) {
	set<int>& s = S[k];
	int a = 0, b = y + 1;
	int l = 0, r = (1 << 17);
	rer(i, 17, 0) {
		// debug(l, r, x, vi(all(s)));
		int m = (r + l) / 2;
		if((1 << i) & x) { //i bit should be 0
			int tlv = max(a, l), trv = min(b, m);
			if(trv - tlv > 0 && s.lower_bound(trv) != s.lower_bound(tlv)) {
				r = m;
			}
			else {
				tlv = max(a, m), trv = min(b, r);
				if(trv - tlv > 0 && s.lower_bound(trv) != s.lower_bound(tlv)) {
					l = m;
				}
				else return -1;
			}
		}
		else { //i bit should be 1
			int tlv = max(a, m), trv = min(b, r);
			if(trv - tlv > 0 && s.lower_bound(trv) != s.lower_bound(tlv)) {
				l = m;
			}
			else {
				tlv = max(a, l), trv = min(b, r);
				if(trv - tlv > 0 && s.lower_bound(trv) != s.lower_bound(tlv)) {
					r = m;
				}
				else return -1;
			}
		}
	}
	return l;
}

void solve() {
	cin >> Q;
	while(Q--) {
		int type; cin >> type;
		if(type == 1) {
			int x; cin >> x;
			add(x);
			// rep(i, 1, 30) {
			// 	debug(i, vi(all(S[i])));
			// }
		}
		else {
			int x, k, s;
			cin >> x >> k >> s;
			if(x % k != 0) cout << "-1\n";
			else cout << get(k, s - x, x) << "\n";
		}
	}
}

E
えぇ…pathの偶奇みるだけ。ちょっと前計算すればO(N^4)。

int N, P;
ll pre[110][2];

ll dp[51][51][51][51];
ll pow2[110];
int A[51];

void solve() {
	cin >> N >> P;
	rep(i, 0, N) cin >> A[i];
	C_init(N + 10);

	rep(i, 0, N + 1) {
		rep(j, 0, i + 1) {
			ADD(pre[i][j % 2], C[i][j]);
		}
	}
	pow2[0] = 1;
	rep(i, 0, N) pow2[i + 1] = pow2[i] * 2 % mod;

	dp[0][0][0][0] = 1;

	rep(wo, 0, N) {
		rep(we, 0, N) {
			rep(bo, 0, N) {
				rep(be, 0, N) {
					if(dp[wo][we][bo][be] == 0) continue;
					int i = wo + we + bo + be;

					if(A[i] != 1) { //black
						ADD(dp[wo][we][bo + 1][be], dp[wo][we][bo][be] * pow2[we + bo + be] % mod * pre[wo][0] % mod);
						ADD(dp[wo][we][bo][be + 1], dp[wo][we][bo][be] * pow2[we + bo + be] % mod * pre[wo][1] % mod);
					}

					if(A[i] != 0) { //white
						ADD(dp[wo + 1][we][bo][be], dp[wo][we][bo][be] * pow2[wo + we + be] % mod * pre[bo][0] % mod);
						ADD(dp[wo][we + 1][bo][be], dp[wo][we][bo][be] * pow2[wo + we + be] % mod * pre[bo][1] % mod);
					}
				}
			}
		}
	}
	ll res = 0;
	rep(wo, 0, N + 1) {
		rep(we, 0, N + 1) {
			rep(bo, 0, N + 1) {
				rep(be, 0, N + 1) {
					if(wo + we + bo + be == N && (bo + wo) % 2 == P) {
						ADD(res, dp[wo][we][bo][be]);
					}
				}
			}
		}
	}
	cout << res << "\n";
}

ABでHackされてDで1WA。速度もそんな速くなくて悔しいですね…。
HackしてもらえなかったらCDのみだったことを考えるとヒヤッとしますね。コーナーケースをよく見極めないとやけどするので気をつけないと…

ARC097

DP Tree

https://beta.atcoder.jp/contests/arc097/tasks

思考法を自分の中で確立して初めてのコンテストだったんですがうまくいったので舞い上がってます。

C
グッと睨むと5文字ずつとってsortすれば良いことがわかる。
D
グラフにすればわかる。
E
条件がO(N)個あって、すべて不等式なのであまり問題自体がいい構造をしてないことがわかります。なのでDPです。
dp[i][j]:=前からi個白を、j個黒を並べた時のmincostとして、累積和の前処理をO(N^2)でやっておけば遷移もO(1)で求められてO(N^2)です。
これを一瞬で出来たのは流石に成長ですね。この時点で25位でした。
F
多分オイラーtourで全辺を2回ずつ回って、どれかのpathを取り除くのではと思えたのは良かったです。しかし数式の変形をうまくできずだめでした。Eまで解いて満足してしまった感はあります。具体例で考えず、一般論で考えていたのもよくなかったです。あと木の問題を解くのが久しぶりすぎて木DPのやり方とか、端のBの削除の仕方とかわからなかったのは反省ですね。

木DP要復習ですね。