精進6/23

https://agc022.contest.atcoder.jp/tasks/agc022_c面白い。場合分け系と思ったけど違った。前処理した後、大きいkから使う必要があるか見ていく。

精進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!]

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)

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

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要復習ですね。

Google Code Jam Round 1C 2018

A
dfsっぽくやって途中でexitすれば速いです。
B
InteractiveっぽかったのでSkip
C
なんでこれ解けないのかなぁ…。

dp[at][count]:=atまで見た時count個stackしたとする。その時の重さの最小値でO(N^2)で、実はcount<=200と言えるので間に合うという、定番中の定番だったけど全然見えなかったです。

まず謎貪欲を考えてしまったのが原因。最初に一番条件が厳しそうなやつを固定して…という方針をとりました。これで不等式をごちゃごちゃしていたんですが、O(N^3)から改善できませんでした。

出てきた不等式が固定したものに依存する形だったのでO(N^2)かかるはずだと冷静に考えればわかるんですが、本番はそこから抜け出せなかったですね。

終了1時間前にめでたくdp思いついたんですが、そこからO(N^2)を改善できなかったのもだめでした。
O(N^2)のdpの改善は累積和or segtree or 状態削減ってわかっているんですが実践できませんでしたね。

こういう泥沼から逃れるための方法がほしいなぁ。
今回の経験で学んだことは「不等式は単調性が成り立つ時のみしかほとんど有用ではない」ってことですね。