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 状態削減ってわかっているんですが実践できませんでしたね。

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

精進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は相当単純なシチュエーションじゃないと出てこないということです。なぜなら2値の和と差のみが条件になる数え上げにしか使えないからです。
つまり問題を解いていてこれは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のΣとか入る複雑な式になりそうだと思った時はとりあえず経路数で言い換えるのが汎用的な解法だと思います。