すげえ〜〜〜〜〜

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";
	}
}

2020-01-28

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";
	}
}

2020-01-24

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";
}

2020-01-22

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を生やしてしまった…

2020-01-20

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";
}

2020-01-18

キーエンスプログラミングコンテスト 2020

https://atcoder.jp/contests/keyence2020

A
v = max(H, W)として、ceil(N/v)です。

B
区間スケジューリング。典型とは言え200はビビりました。

C
基本K個のSとN-K個のS+1で良いんですが、S=10^9の時だけN-K個の数を1にします。ギャグ。

D
個人的には解きやすかった。indexの距離の偶奇でAとBどちらを取るか決まります。あとはbitdpで前から順番に決めていけばよいです。
popcountすれば偶奇の判定も簡単です。

int N;
int dp[(1 << 18)][18];
int A[18], B[18];

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	rep(i, 0, N) cin >> B[i];

	rep(bit, 0, (1 << 18)) {
		rep(i, 0, N) dp[bit][i] = inf;
	}

	dp[0][0] = 0;

	rep(bit, 0, (1 << N)) {
		rep(i, 0, N) {
			if(dp[bit][i] == inf) continue;
			int cnt = 0;
			rep(j, 0, N) {
				if(bit & (1 << j)) continue;
				int v = (__builtin_popcount(bit) - j + 50) % 2 == 0 ? A[j] : B[j];
				int pv = bit == 0 ? -1 : (__builtin_popcount(bit) - 1 - i + 50) % 2 == 0 ? A[i] : B[i];
				if(pv <= v) MIN(dp[bit | (1 << j)][j], dp[bit][i] + cnt);


				cnt += ((bit & (1 << j)) == 0);
			}
		}
	}
	int res = inf;
	rep(i, 0, N) MIN(res, dp[(1 << N) - 1][i]);
	if(res == inf) cout << -1 << "\n";
	else cout << res << "\n";
}

E
まず辺にどちらの頂点が大きいかで不等式をつけてみたところ、ある1点のみに小なりの符号が集中しているとできないことが
わかりました。逆に小なりの符号が集中しているのが、2点以上の等号による連結成分ならうまく行くだろうとなり、
構成法を色々考えていたんですが、コストの大きい頂点から辺を張っていくことを
ずっと考えていたせいでわかりませんでした。(小さい方からなら簡単です)でも偶然max(D_u,D_v)みたいなコストの辺で最小全域木を作る問題を
思い出したので、(https://atcoder.jp/contests/arc098/tasks/arc098_d)
それで全域木を作ってみた所、木上で2色彩色するだけになり簡単に構成できました。
1WA出したんですがこれは一箇所MとNを入れ替えていたためです…なんか木の場合を入力に入れたら都合よくバグってくれました。

2020-01-18

KUPC2019

ちょっと気になった問題取り上げます。

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_e

木ごとにgrundyするのかなと思ったんですが、ゲームが分割されているわけではないので今回では
あんまり役に立たないです。木ごとに単なる勝ち負けを求めても、最適moveではわざと負けるみたいな
ことをする可能性もあります。なので、(i)「手番が必ず変わらない」(ii)「手番が必ず変わる」(iii)「手番が変わるかを先手が選べる」
(iv)「手番が変わるか後手が選べる」の4パターンに分類すると良いです。
すると複数の木を見て回った後の勝敗も上の4パターンに分類できます。しかし(i)は無視できるので実質3パターンです。
(iii)が一つでもあるなら、残りのN-1の勝敗パターンを見てから先手が決められるので先手の勝利です。
(iii)がないなら、(iv)を先に選んでしまうと後手が残りの木の勝敗を見て勝利するように行動できるので負けです。
よって(ii)を順番に選んでいくゲームになり、(ii)が偶数個なら後手勝ち、奇数個なら先手勝ちとなります。

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_f

まず区間ではモンスターを一点集中させるのが良いことを証明できます。これは簡単で、
区間でb_l,...,b_rとモンスターを配置したなら、argmin(A_i-b_i)に集中させても解は小さくなりません。
事前にどの地点にモンスターを配置するか決めてしまえば、解は(区間のうち配置地点を含むものの和)-(配置地点の勇者の数)
となります。ここで
dp(i):=0~i地点まで見てi地点にはモンスターを配置すると決めた時のコストの最大値とすれば、
dp(i)からdp(j)への遷移は(始点が(i,j]でjを含むような区間の和)-A_jとなり、これはjで平面走査すればO(NlogN)で行えます。
全てのiについて見ていっても合計でO(N^2logN)です。

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_g

abca
bcab
cabc
abca

これが思いつけるかが全てです。あとは端を延長することによって達成できます。

omochan's diary

AOJ2327: Sky Jump