Codeforces Round #616 (Div. 1)

https://codeforces.com/contest/1290

ダメダメだったため、撤退…あとでちゃんと復習します。

A
勘違いして変な条件で考えてしまいました…詰めるのもめちゃくちゃ遅かった。例によって条件を整理しきらずに紙に頼ってしまった。

B
adhocだと思えば解けたかもしれない…

C
解説みたらライトを辺と置き換える言い換えすらもできてなかった。(ライトを頂点とした2部グラフで見てた。)
でも解けそうな気はしたが…

codeforcesの問題、ちゃんと考察にadhocな点が1つ2つあって、実装もまあまあ重い感じなんだよな。
AtCoderはadhocに振り切れればいいけど。失敗しているときはだいたい考察が足りてないときではある気がする。頭を動かしましょう。

AOJ2445: MinimumCostPath

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

N<400の時は愚直に求めることにします。
N>=400の時は、
左下、右上の100x100領域に注目します。
(0,0)->(左下の領域)->(真ん中の領域)->(右上の領域)->(N-1,N-1)と移動していくことになりますが、
真ん中の領域では必ず右または上のみの移動になります。

これを証明するためには、任意の経路を経路長を伸ばすことなく、真ん中の領域で右または上のみ移動する経路に変換できることを示せばよいです。
左下の領域から初めて出た場所を(x,100)とします。対称性より(100,y)の時も同様です。
0<=y<100において、障害物がない行が必ず存在します。その行を通って左下の領域から出ると、右または上のみの移動で、右上の領域に入ることが出来ます。
このとき経路長は伸びません。

この事実により、左下の領域から出た座標と右上の領域に入った座標について、最短経路の本数を求めれば良くなり、これは
https://atcoder.jp/contests/dp/tasks/dp_y
です。最後に通った障害物で包除する感じです。

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

int N, M;
int X[110], Y[110];
int B[510][510];
ll D[510][510];

void pre(int l, int r, int x, int y) {
	int n = r - l;
	rep(i, 0, n) {
		rep(j, 0, n) {
			B[i][j] = inf;
		}
	}
	rep(i, 0, M) {
		if(l <= X[i] && X[i] < r && l <= Y[i] && Y[i] < r) {
			B[X[i] - l][Y[i] - l] = -1;
		}
	}
	memset(D, 0, sizeof(D));
	x -= l;
	y -= l;
	queue<pi> que;
	que.push(pi(x, y)); 
	B[x][y] = 0;
	D[x][y] = 1;
	while(!que.empty()) {
		pi p = que.front(); que.pop();
		rep(i, 0, 4) {
			int nx = p.fst + dx[i], ny = p.sec + dy[i];
			if(0 <= nx && nx < n && 0 <= ny && ny < n && B[nx][ny] != -1) {
				if(B[nx][ny] >= B[p.fst][p.sec] + 1) {
					ADD(D[nx][ny], D[p.fst][p.sec]);
					if(B[nx][ny] > B[p.fst][p.sec] + 1) {
						B[nx][ny] = B[p.fst][p.sec] + 1;
						que.push(pi(nx, ny));
					}
				}
			}
		}
	}
}

ll qre(int x1, int y1, int x2, int y2) {
	vector<pi> vec;
	// debug(x1, y1, x2, y2);
	rep(i, 0, M) {
		if(x1 == X[i] && y1 == Y[i]) return 0;
		if(x2 == X[i] && y2 == Y[i]) return 0;
		if(x1 <= X[i] && X[i] <= x2 && y1 <= Y[i] && Y[i] <= y2) vec.pb(pi(X[i], Y[i]));
	}
	vec.pb(pi(x1, y1));
	vector<ll> dp(sz(vec), 0);
	sort(all(vec));
	rer(i, sz(vec), 0) {
		int a = vec[i].fst, b = vec[i].sec;
		dp[i] = C(x2 - a + y2 - b, x2 - a);
		rep(j, i + 1, sz(vec)) {
			int c = vec[j].fst, d = vec[j].sec;
			ADD(dp[i], mod - dp[j] * C(c - a + d - b, d - b) % mod);
		}
	}
	return dp[0];
}

void solve() {
	int bound = 100;
	cin >> N >> M;
	C_init(2 * N);
	rep(i, 0, M) {
		cin >> X[i] >> Y[i];
		X[i]--; Y[i]--;
	}
	if(N < 400) {
		pre(0, N, 0, 0);
		cout << D[N - 1][N - 1] << "\n";
	}
	else {
		vector<pair<pi, pl>> vl, vr;
		pre(0, bound, 0, 0);
		rep(i, 0, bound) {
			if(B[i][bound - 1] != -1)
			vl.pb(make_pair(pi(i, bound), pl(B[i][bound - 1] + 1, D[i][bound - 1])));
			if(B[bound - 1][i] != -1)
			vl.pb(make_pair(pi(bound, i), pl(B[bound - 1][i] + 1, D[bound - 1][i])));
		}
		pre(N - bound, N, N - 1, N - 1);
		rep(i, 0, bound) {
			if(B[i][0] != -1)
			vr.pb(make_pair(pi(N - bound + i, N - bound - 1), pl(B[i][0] + 1, D[i][0])));
			if(B[0][i] != -1)
			vr.pb(make_pair(pi(N - bound - 1, N - bound + i), pl(B[0][i] + 1, D[0][i])));
		}
		ll md = inf;
		rep(i, 0, sz(vl)) {
			rep(j, 0, sz(vr)) {
				ll v = vl[i].sec.fst + vr[j].sec.fst + (vr[j].fst.sec - vl[i].fst.sec) + (vr[j].fst.fst - vl[i].fst.fst);
				MIN(md, v);
				// debug(v, vl[i], vr[j]);
			}
		}
		// debug(md, vl, vr);
		ll res = 0;
		rep(i, 0, sz(vl)) {
			rep(j, 0, sz(vr)) {
				if(md == vl[i].sec.fst + vr[j].sec.fst + (vr[j].fst.sec - vl[i].fst.sec) + (vr[j].fst.fst - vl[i].fst.fst)) {
					ADD(res, vl[i].sec.sec * vr[j].sec.sec % mod 
							* qre(vl[i].fst.fst, vl[i].fst.sec, vr[j].fst.fst, vr[j].fst.sec) % mod);
				}
			}
		}
		cout << res << "\n";
	}
}

2パートあるだけで実装辛くなる…

AOJ2327: Sky Jump

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

すげえ〜〜〜〜〜

x座標がXに到達した時のYの最大値と最小値を求めてしまえば、そこの間の値はtを連続的に動かすことにより取ることができるのでYes or Noの判定が出来ます。

最小値はロケットのうちどれか1つだけ使えば達成できます。

最大値を考えます。
max f(t_1,....,t_n) = (Σw_i-1/2 g t_i^2)
where
h(t_1,...,t_n)=0, t_1>=0, t_2>=0, ... ,t_n>=0
です。

fにマイナスを掛けて最小値問題にした後、KKT条件は以下のようになります。

∇(-f)+\mu_1 ∇(-t1)+...+\mu_n ∇(-tn)+\lambda ∇(h)=0
\mu_i t_i = 0
\mu_i >= 0 t_i >= 0
h=0

∇をt_iごとに展開すると、
-w_i+g t_i - \mu_i + \lambda v_i = 0
となります。

t_i,\mu_iを削除することを目標にすると、以下のように変形できます。

Σ(v_i^2/g \mu_i - v_i^2/g \lambda) = X - Σv_i w_i / g
\mu_i = max(v_i \lambda - w_i, 0)
t_i = max((w_i - v_i \lambda)/g,0)

これで\lambdaで条件を書き表すことが出来ました。
u(\lambda)=Σ(v_i^2/g \mu_i - v_i^2/g \lambda)とすると、最初の式はu(\lambda) = X - Σv_i w_i / g となります。
さらにu(\lambda)は単調減少であり、\lambda-> -∞ のときu(\lambda) -> -∞, \lambda -> +∞のときu(\lambda) = -Σv_i w_i / g となるので、条件を満たすような\lambdaはただ1つだけ存在します。
単調性より\lambdaは二分探索で求めることができます。boundですが[-20000, 1000]とすれば十分です。
\lambdaが求まれば\t_i,さらにはfもわかるので最大値が求められます。

int N;
double X, Y;
double V[1010], W[1010];

double f(double lamb) {
	double res = 0;
	rep(i, 0, N) {
		res += max(V[i] * lamb - W[i], 0.0) * V[i] / 9.8 - V[i] * V[i] / 9.8 * lamb;
	}
	return res;
}

void solve() {
	while(true) {
		cin >> N;
		if(N == 0) break;
		rep(i, 0, N) cin >> V[i] >> W[i];
		cin >> X >> Y;
		double sum = X;
		rep(i, 0, N) sum -= V[i] * W[i] / 9.8;
		double ok = -20000, ng = 1000;
		rep(_, 0, 60) {
			double m = (ok + ng) / 2.0;
			if(f(m) >= sum) ok = m;
			else ng = m;
		}
		double mf = 0.0;
		rep(i, 0, N) {
			double t = max((W[i] - V[i] * ok) / 9.8, 0.0);
			mf += W[i] * t - 9.8 * 0.5 * t * t;
		}
		// debug(mf, ok);
		bool ans = true;
		if(mf + eps < Y) ans = false;
		double found = false;
		rep(i, 0, N) {
			double t = X / V[i];
			if(W[i] * t - 9.8 * 0.5 * t * t <= Y) found = true;
		}
		if(!found) ans = false;
		if(ans) cout << "Yes\n";
		else cout << "No\n";
	}
}

DISCO presents ディスカバリーチャンネル コードコンテスト2020 本戦C: Smaller-Suffix-Free Sequences

https://atcoder.jp/contests/ddcc2020-final/tasks/ddcc2020_final_c

本番はさんざんでしたが…良問です。

実はiにおける答えはiS[j...N]を満たす最小のindexです。つまり、suffix array順でiがjの後に来るものを
見れば良いです。O(NlogN)となります。

証明はeditorialを参考にしてください。

suffix arrayを使うのが本質だと思ってしまい、ずっとsuffix arrayをこねくり回してしまったのが敗北原因です。ちゃんと条件を整理しに行く必要が有りました。
algorithmな解法は最後まで取っておくのが吉です。

あとsuffix arrayの使い方を忘れてしまったのも良くなかったです。文字の種類数を200000とかにしたら壊れるかなと思ったんですが壊れません。SA-ISすごいね。

int N;
vi vec;
int ans[MAX_N];
int I[MAX_N];

void solve() {
	cin >> N;
	vec.resize(N);
	rep(i, 0, N) {
		cin >> vec[i];
		vec[i]--;
	}
	SA sa; sa.init(vec, 200000);
	rep(i, 1, N + 1) {
		I[sa.sa[i]] = i - 1;
	}
	// debug(vi(I, I + N));
	segtree seg; seg.init(N);
	rer(i, N, 0) {
		int v = seg.get(0, I[i]).v;
		ans[i] = min(v, N);
		seg.update(I[i], I[i] + 1, i);
	}
	rep(i, 0, N) {
		cout << ans[i] << "\n";
	}
}

ABC128F: Frog Jump

https://atcoder.jp/contests/abc128/tasks/abc128_f

超良問。

A-B=Cとして場合分けします。

(i)(N-1)%C != 0のとき
0, C, 2C, 3C, ..., kC
N - 1, N - 1 - C, N - 1 - 2C, N - 1 - 3C, ..., N - 1 - kCと取ることができます。

(ii)(N-1)%C==0のとき
(i)とだいたい同様ですが、取る場所がかぶってはいけないので、kC < N - 1 - kCが成り立つkについて取ることができます。

Cとkすべて試すとO(N(1 + 1/2 + 1/3 + ...)) = O(NlogN)です。

ちなみに(i)(ii)よりN-1に減点なしで到達できるA,Bの必要十分条件
A <= floor(N/2)のとき、N-1=A(mod A-B), N-1≠0(mod A-B)
A > floor(N/2)のとき、N-1=A(mod A-B)
です。最初はこっちの条件から解こうとしました。

int N;
ll D[MAX_N];

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> D[i];
	ll res = 0;
	rep(k, 1, N - 1) {
		if((N - 1) % k == 0) {
			ll tmp = 0;
			for(int i = 0; i < N - 1 - i; i += k) {
				tmp += D[i]; tmp += D[N - 1 - i];
				MAX(res, tmp);
			}
		}
		else {
			ll tmp = 0;
			for(int i = k; i < N - 1 - k; i += k) {
				tmp += D[i]; tmp += D[N - 1 - i];
				MAX(res, tmp);
			}
		}
	}
	cout << res << "\n";
}

yukicoder contest 234

https://yukicoder.me/contests/247

実装重い~~~~

A
偶数でYesを出力しそうになった…

B
N変数でN個の線形独立な式があるので求められます。対称なので全部足せば良いです。

C
これ4方向に行けると勘違いして時間を溶かした…dpの更新式が決まります。無駄にdijkstraしてしまいました…
ちなみに4方向の時はO(HWK)で解けると思います。

D
良問。まず中間値は1要素で良くて、固定(indexをiとする)してしまえば、N-1~N-kまでとi-1~i-kの範囲にある要素を
取ればいいことになります。kは二分探索で決められます。

E
とりあえず3乗解は簡単です。あとは累積和などで高速化すれば良いんですがめんどくさくてやめた…

F
デートする日を決めてしまえば後の日はバイトすればいいです。ここで半分全列挙してくれといわんばかりの制約なのでします。
2^26要素の全探索をしないといけないように見えますが、デートする日は連続しないのでかなり状態が減って余裕で間に合います。
分割の境でデートするかしないかの条件をバグらせてWAを生やしてしまった…

Codeforces Round #614 (Div. 1)

https://codeforces.com/contest/1292

A
点を共有するおじゃまマスが存在してはいけません。隣接している箇所の個数のみを保持すればいいです。

B
まずどっかの点に行ってから上or下に順番に取っていくのが最適です。点を全列挙する際にオーバーフロー
に注意しなければならないですが、僕はx > sx + t || y > sy + tでbreakしました。

C
ある辺に0を書き込んでから両端に1,2,3...とpathを延長していくのが最適です。するとコストは、
s(k) = (0を通るpathの本数)+(0,1を通るpathの本数)+...+(0,1,2,...,kを通るpathの本数)とすれば、s(N-1)となります。

ここでdp[u][v]:=uからvのpath上に0~dist(u,v)-1を書き込んだ時のs(dist(u,v)-1)の最大値

とします。path上にあってuと隣接している点をpとすれば、chmin(dp[u][v],dp[p][v]+cost[u][v])で更新できます。
vも同様にやります。ここでcostはuからvのpathを丸々含むpathの本数となるので、これを前計算で求めておきます。
これが結構難しかったです。根付き木でu,vのsubtreeの頂点数を足し引きするみたいな方針でやったんですが、適当にやったら
lca(u,v)=uの時に破滅しました。このときはcost[u][v]=(N-|subtree(p)|)*|subtree(v)|としなければならず、pをいちいち求めていると
3乗になってTLEします。なのでN=3000であることを活かしてまず最初にlca(u,v)=uとなるような頂点のpairについて頂点の親を順番にみていきながら
求め、残りのpairは|subtree(u)|*|subtree(v)|となることを利用して求めました。最初lcaが必要かなと思ったんですが結局いらずにO(N^2)でした。

上記の嘘で1WA、オーバーフローで1WAしました。絶妙にオーバーフローするんだよね…
あと更新の際pを見つけるのにdeg(u)=O(N)かかる場合があるからO(N^3)になりそうな気がするんですが、
あるuを固定するとdeg(u)かかるのがvの数、つまりN個かかるので、N deg(u)となり、uを全て見てもN 2*(N-1)にしかならずO(N^2)です。
これはかなり非直感的なので勉強になりました。

int N;
vi G[MAX_N];
int cost[3010][3010];
int dist[3010][3010];
int par[3010];
ll dp[3010][3010];
int sub[3010];

void pre(int v, int p) {
	sub[v] = 1;
	par[v] = p;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(n == p) continue;
		pre(n, v);
		sub[v] += sub[n];
	}
}

void qre(int root, int v, int p, int c) {
	dist[root][v] = c;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(n == p) continue;
		qre(root, n, v, c + 1);
	}
}

ll loop(int v, int u) {
	if(v == u) return 0;
	else if(v > u) return loop(u, v);
	else if(dp[v][u] != -1) return dp[v][u];
	else {
		ll res = 0;
		int d = dist[v][u];
		rep(i, 0, sz(G[v])) {
			int n = G[v][i];
			if(dist[n][u] < d) {
				MAX(res, loop(n, u) + cost[v][u]);
			}
		}
		rep(i, 0, sz(G[u])) {
			int n = G[u][i];
			if(dist[v][n] < d) {
				MAX(res, loop(v, n) + cost[v][u]);
			}
		}
		return dp[v][u] = res;
	}
}

void solve() {
	cin >> N;
	rep(i, 0, N - 1) {
		int a, b; cin >> a >> b; a--; b--;
		G[a].pb(b);
		G[b].pb(a);
	}
	pre(0, -1);
	rep(i, 0, N) {
		qre(i, i, -1, 0);
	}
	rep(i, 0, N) {
		int at = i;
		while(at != 0) {
			int nat = par[at];
			cost[i][nat] = (N - sub[at]) * sub[i];
			cost[nat][i] = cost[i][nat];
			at = nat;
		}
	}
	rep(i, 0, N) {
		rep(j, 0, N) {
			if(i == j) continue;
			if(!cost[i][j]) {
				cost[i][j] = sub[i] * sub[j];
			}
		}
	}
	memset(dp, -1, sizeof(dp));
	ll res = 0;
	rep(i, 0, N) {
		rep(j, i + 1, N) {
			MAX(res, loop(i, j));
		}
	}
	cout << res << "\n";
}