第3回ドワンゴからの挑戦状 本戦 A - 計算ドリル

俺のrated500埋めの最後の問題がこれ
atcoderでこういう実装ゲーはかなり珍しい

問題

'0'〜'9'、'+'、'-' のみからなる文字列sが与えられる
これをk文字まで書き換えて得られる、逆ポーランド記法で計算できる正しい文字列のうち、計算結果の最大値を求めよ

1 <= |s| <= 52
0 <= k <= |s|

解法

メモ化しながら区間dp
数式の一番最後の文字は '+' か '-' である必要があり、それ以外の部分は2つの式に分けることができるってのがポイント
この区切りとそれぞれの区間に割り振るkを全探索して更新していく
詳細は↓のコメントの通り

string s;
int n, k, dp[55][55][55][2];
bool fin[55][55][55][2];
const int M = 10000;

// [l,r]をk文字まで変えたときの最(b?大:小)値
int rec(int l, int r, int x, bool b) {
	if (fin[l][r][x][b]) return dp[l][r][x][b];
	fin[l][r][x][b] = 1;
	int &res = dp[l][r][x][b];
	res = (b ? -M : M);
	// どう変えても正しい式にならない場合
	if ((r-l+1)%2==0) return res;
	// 1桁の場合
	if (l==r) {
		if (x) res = (b ? 9 : 0);
		else if (isdigit(s[l])) res = s[l]-'0';
		return res;
	}
	// 一番右の文字は+か-にする
	int xp = x - (s[r]!='+'), xm = x - (s[r]!='-');
	// 2つの式の和の最大値は (最大)+(最大) or (最大)-(最小)
	if (b) {
		reps(i,l,r-1) {
			rep(j,xp+1) {
				int tx = rec(l,i,j,1), ty = rec(i+1,r-1,xp-j,1);
				if (tx!=-M && ty!=-M) chmax(res, tx+ty);
			}
			rep(j,xm+1) {
				int tx = rec(l,i,j,1), ty = rec(i+1,r-1,xm-j,0);
				if (tx!=-M && ty!=M) chmax(res, tx-ty);
			}
		}
	}
	// 最小値は (最小)+(最小) or (最小)-(最大)
	else {
		reps(i,l,r-1) {
			rep(j,xp+1) {
				int tx = rec(l,i,j,0), ty = rec(i+1,r-1,xp-j,0);
				if (tx!=M && ty!=M) chmin(res, tx+ty);
			}
			rep(j,xm+1) {
				int tx = rec(l,i,j,0), ty = rec(i+1,r-1,xm-j,1);
				if (tx!=M && ty!=-M) chmin(res, tx-ty);
			}
		}
	}
	return res;
}

signed main() {
	cin >> k >> s;
	n = s.size();
	int res = rec(0,n-1,k,1);
	if (res==-M) cout << "NG" << endl;
	else cout << "OK" << endl << res << endl;
}

https://beta.atcoder.jp/contests/dwacon2017-honsen/tasks/dwango2017final_a

ARC087 F - Squirrel Migration

これ800点ってマジ?ムズすぎてハゲた

問題

n頂点の木があり、全ての頂点にリスがいる
長さnの順列pを決め、頂点iのリスを頂点p[i]に移動させる
各リスの移動距離の総和が最大になるようなpは何通りあるか

2 <= n <= 5000

解法

x-yを繋ぐ辺を通るリスの数の最大値は、xyそれぞれを根とする部分木をtx, tyとすると、
2 * min(|tx|, |ty|) である
サイズが小さい方の部分木のリスが全てもう片方の部分木に移動する場合にこうなる

○木の重心が2個ある場合
重心間の辺について↑の条件を満たせば他の全ての辺も条件を満たす
重心が2個ある場合、各重心を根とする部分木のサイズはどちらもn/2になるから、答えは{(n/2)!}^2

○重心が1個しかない場合
重心から伸びている辺全てについて↑の条件を満たせば他の全ての辺も条件を満たす
各部分木の全リスが「元々いた部分木上の頂点」以外のどこかに行くような順列pの個数を求めればいい
これは部分木ごとにサイズが違うから重心が2個の場合ほど単純には行かない
ここで余事象の「同じ部分木に留まるようなリスが1匹以上存在する」を考える
明らかにこっちの方が考えやすそうだからこっちを包除原理で求める

重心に隣接する各頂点を根とする部分木をT1, T2, ..., Tkとする
以下数式が複雑でタイプするのめんどいからクソ汚いメモをそのまま貼ります
途中で|T|とかΣ|Ti|って何回か書いてるけどこれは明らかにn-1(重心以外の全頂点の個数)
あと最後の行のdp[|T|][x]はdp[k][x]の間違い

f:id:creep040:20181030073359p:plain

f:id:creep040:20181030073415p:plain

f:id:creep040:20181030073425p:plain

実装(プログラムの流れ)

f[i]: iの階乗 は最初に求めておく

頂点0を仮の根とし、rec()で各頂点vを根とする部分木のサイズsz[v]を求めつつ重心を探す
直接の子c[i]全てについてsz[c[i]]がn/2以下 かつ n-sz[v]もn/2以下ならvは重心
(木の重心の詳細はググって)
gが1個目の重心でggが2個目の重心

2個目の重心ggが存在する場合は{(n/2)!}^2を出力して終了

次に重心gを木の根とし、rec2()で各頂点vを根とする部分木のサイズsz[v]を求める
gに隣接する頂点を根とする部分木のサイズをvector tにしまう (tのサイズがk)
あとは↑の通りにdpして包除原理

comb(n,k) = nCk は省略

#define int long long

int n, a, b, sz[5050], g = -1, gg = -1, f[5050], k, dp[5050][5050], res;
vector<int> e[5050], t;

int rec(int v, int p) {
	bool gp = 1;
	sz[v] = 1;
	each(i,e[v]) if (i!=p) {
		int tmp = rec(i,v);
		if (tmp>n/2) gp = 0;
		sz[v] += tmp;
	}
	if (gp && n-sz[v]<=n/2) {
		if (g==-1) g = v;
		else gg = v;
	}
	return sz[v];
}

int rec2(int v, int p) {
	each(i,e[v]) if (i!=p) sz[v] += rec(i,v);
	return sz[v];
}

signed main() {
	f[0] = 1;
	reps(i,1,5050) f[i] = f[i-1]*i %mod;
	cin >> n;
	rep(i,n-1) {
		cin >> a >> b;
		a--, b--;
		e[a].push_back(b), e[b].push_back(a);
	}
	rec(0,-1);
	if (gg!=-1) return cout << f[n/2]*f[n/2] %mod, 0;
	memset(sz, 0, sizeof(sz));
	rec2(g,-1);
	each(i,e[g]) t.push_back(sz[i]), k++;
	dp[0][0] = 1;
	rep(i,k) {
		int sum = 0;
		rep(j,i) sum += t[j];
		rep(x,sum+1) rep(y,t[i]+1)
			(dp[i+1][x+y] += dp[i][x] * comb(t[i],y) %mod * comb(t[i],y) %mod * f[y]) %= mod;
	}
	rep(i,n) (res += dp[k][i] * f[n-i] * (i%2 ? -1 : 1)) %= mod;
	(res += mod) %= mod;
	cout << res << endl;
}

冷静に見ると1つ1つはそこまで難しくない典型の組み合わせなんだよな
論理的思考+典型力で解ける問題ではあるんだろうな

https://beta.atcoder.jp/contests/arc087/tasks/arc087_d

Codechef - Chef and K Segments [CHEFKO]

問題

n個の区間があり、i個目区間の左端はL[i]、右端はr[i]である
これらから好きな区間をk個選び、それら全ての共通区間の長さをスコアとする
スコアの最大値を求めよ

1 <= k <= n <= 10^5
1 <= L[i] <= r[i] <= 10^9

解法

スコアを二分探索すれば解ける
スコアをdにすることが出来るかの判定方法を考える

共通区間の左端右端はそれぞれ、n個の区間のどれかの左端右端と一致するはず
よって左端右端の候補はそれぞれn通りしかない
左端をL[i]とすると、
1) 左端がL[i]以下
かつ
2) 右端がL[i]+d以上
区間がk個存在すれば良い
与えられる区間を左端の昇順にソートして左から順に1個ずつ見ていくことにすると、条件1を満たすのは今見ている区間と今まで見た区間だけになる
更にその中に条件2を満たすものが何個あるかを数えたい
これは降順priority_queueに今まで見た区間の右端の座標を入れていけばわかる
queue.top()が今の条件2を満たすまでpopし続け、その後のqueueのサイズが条件を両方とも満たすような区間の個数になる
区間は左端の昇順に並んでるから、見る区間を右にずらしていくと条件2は単調に厳しくなっていくため、一度popした要素は二度と使うことはない

O(n(logn)^2)で、TLが1sで0.93sかかってる
こういうやたら厳しいTLって極限まで定数倍高速化した愚直解とかbitsetで高速化みたいなのが間違って通らないためにやってんだろうけど、ちょっと定数倍が遅いくらいのまともな解法が落ちるよりはそっちのが不幸な人減らない?

int Q, n, k;
pair<int,int> p[100100];

bool ok(int d) {
	priority_queue<int, vector<int>, greater<int> > q;
	rep(i,n) {
		q.push(p[i].second);
		while (!q.empty() && q.top()<p[i].first+d) q.pop();
		if (k<=q.size()) return 1;
	}
	return 0;
}

signed main() {
	cin >> Q;
	while (Q--) {
		cin >> n >> k;
		rep(i,n) cin >> p[i].first >> p[i].second;
		sort(p, p+n);
		int l = 0, r = 1<<30;
		while (r-l>1) {
			int m = (l+r)/2;
			(ok(m) ? l : r) = m;
		}
		cout << l << endl;
	}
}

https://www.codechef.com/problems/CHEFKO

CF519 F - Make It One

良問だった

問題

n個の整数aが与えられる
aの部分集合のうち全要素のgcdが1になるようなもののサイズの最小値を求めよ
(存在しない場合は-1)

1 <= n <= 3*10^5
1 <= a[i] <= 3*10^5

解法

2*3*5*7*11*13 < 3*10^5 < 2*3*5*7*11*13*17
より答えはたかだか7であることがまずわかる
dp[i][j]: i個の要素を含み、それらのgcdがjになるような部分集合の個数
とすると包除原理より
dp[i][j] = (a[]のうちjで割り切れるものをi個選ぶ組み合わせの数) - Σdp[i][k] (k: jを除くjの倍数)
となる
d[i]: iで割り切れるa[j]の個数 を事前に求めておき、dpテーブルをjの降順に埋めていけばO(mlogm)で求められる
(m: max(a))
dp[i][1]>0を満たす最小のiが答え

int n, a[300300], b[300300], dp[10][300300], d[300300];

signed main() {
	cin >> n;
	rep(i,n) {
		cin >> a[i];
		b[a[i]]++;
	}
	reps(i,1,300200) for (int j=i; j<=300200; j+=i) d[i] += b[j];
	reps(i,1,8) for (int j=300200; j>=1; j--) {
		dp[i][j] = comb(d[j], i);
		for (int k=j*2; k<=300200; k+=j) (dp[i][j] += mod - dp[i][k]) %= mod;
	}
	reps(i,1,8) if (dp[i][1]) return cout << i << endl ,0;
	cout << -1 << endl;
}

http://codeforces.com/contest/1043/problem/F

CF519 D - Mysterious Crime

超凡ミスで2問落としてまた1893まで落ちちゃった
マジで深夜はパフォーマンス落ちる

問題

長さnの順列がm個与えられる
それぞれの順列の先頭と末尾からいくつかの数字を消し、全ての順列を一致させたい
数字の消し方は何通りあるか

1 <= n <= 10^5
1 <= m <= 10

解法

1個目の順列が 1,2,3,... となるように各順列の数字を変換する
(2,1,4,3 -> 1,2,3,4 とすると 2->1, 1->2, 4->3, 3->4 という変換ルールが出来るということ)
すると、最終的な数列のうち1個目の順列のk番目を左端とするものの最長の長さは
min(各順列のkから右にk+1, k+2, ...と1ずつ増えていくような列の長さの最大値)
となる
この長さの最大値は単純なdpで求められる
左端と最長の長さLが決まれば、kを左端とする長さ1,2,...,Lの数列は全て作れるから、左端を全部試して答えにLを足していけばいい

今見るとめちゃくちゃ簡単なんだけど眠すぎてボケてたのか、本番では長さの最大値をdpするって発想が出てこなくて二分探索してた
二分探索だと4,5,6と4,6,5の区別が付かないからダメ & 計算量的にも危険

int n, m, a[11][100100], res, p[11][100100], dp[11][100100];
map<int,int> con;

signed main() {
	cin >> n >> m;
	rep(i,m) rep(j,n) cin >> a[i][j];
	rep(i,n) con[a[0][i]] = i+1;
	rep(i,m) rep(j,n) a[i][j] = con[a[i][j]], p[i][a[i][j]] = j;
	rep(i,m) for (int j=n-1; j>=0; j--) {
		if (a[i][j]==a[i][j+1]-1) dp[i][j] = dp[i][j+1] + 1;
		else dp[i][j] = 1;
	}
	reps(j,1,n+1) {
		int mn = 1<<30;
		rep(i,m) chmin(mn, dp[i][p[i][j]]);
		res += mn;
	}
	cout << res << endl;
}

http://codeforces.com/contest/1043/problem/D

Tenka1 Programmer Contest 2018 E - Equilateral

はてなブログたまに写真表示されなくならないか?

問題

h*wのグリッドがあり、いくつかのマスにはコインが置かれている
相異なるコイン3つの組のうち、どの2つのコイン同士のマンハッタン距離も同じであるようなものは何個あるか

1 <= h, w <= 300

解法

マンハッタン距離ってことでとりあえず45度回転して考える
2点X, Yの max(x座標の差, y座標の差) をdとすると、3点X, Y, Zが問題の条件を満たすには、X, Yそれぞれを中心とした1辺2dの正方形の交線上にZがある必要がある
↓はX, Yのx座標とy座標が共に異なり、共通範囲が点になる場合
f:id:creep040:20181028170807p:plain
結局↑のように3点のうち2点のx座標かy座標は等しくなることがわかる
f:id:creep040:20181028170819p:plain
よってx座標 or y座標が等しい2個のコインのペアを全て見て、この↑交線上にあるコインの個数を足し合わせていけばO(h^3 + w^3)で答えが得られる
ただし同一正方形の3 or 4角にコインがある場合は同じ組を重複カウントしてしまう
3角にコインがある正方形は1個につき1、4角の正方形は1個につき4だけ答えから引けばきれいに重複を消せる
(絵描いてみればわかる)

実装

重複を消すのは、x座標が等しい2点のペアを全部試す時に「同じ正方形の3角にコインがある」ことを確認する度に1引けばok
こうすれば3角の正方形は1回、4角の正方形では4回引っかかるからちょうど重複を消せる

hs: ヨコ方向の累積和
vs: タテ方向の累積和

int h, w, a[666][666], hs[666][666], vs[666][666], res;
string s[333];

signed main() {
	cin >> h >> w;
	rep(i,h) {
		cin >> s[i];
		rep(j,w) if (s[i][j]=='#') a[i+j+1][i-j+300] = 1;
	}
	reps(i,1,600) reps(j,1,600) {
		hs[i][j] += a[i][j] + hs[i][j-1];
		vs[i][j] += a[i][j] + vs[i-1][j];
	}
	reps(i,1,600) reps(j,1,600) reps(k,j+1,600) {
		int d = k-j;
		if (a[i][j] && a[i][k]) {
			if (i-d>=0) {
				res += hs[i-d][k] - hs[i-d][j-1];
				res -= a[i-d][j] + a[i-d][k];
			}
			if (i+d<=600) {
				res += hs[i+d][k] - hs[i+d][j-1];
				res -= a[i+d][j] + a[i+d][k];
			}
		}
		if (a[j][i] && a[k][i]) {
			if (i-d>=0) res += vs[k][i-d] - vs[j-1][i-d];
			if (i+d<=600) res += vs[k][i+d] - vs[j-1][i+d];
		}
	}
	cout << res << endl;
}

後からなら何でも言えるけどD捨てれば解けてた
まあ反省するべきはそれよりDが解けなかったことだな
構築っぽくて見ただけで拒否反応が出たけど閃きが必要な問題ではなかったから冷静に考えれば解けたはず
Cで割と萎えてたのはあると思う

https://beta.atcoder.jp/contests/tenka1-2018/tasks/tenka1_2018_e

Codechef - Country Tour [CTOUR]

Encoderっていうコンテストの最後の問題
何気なく参加してみたけどこの問題は個人的に面白かった

問題

n頂点の木が与えられ、根は頂点1である
辺iは頂点a[i]とb[i]を繋ぎ、通る時c[i]円貰える
(c[i]が負のこともあり、そういうときは逆に-c[i]円払わないといけない)
q個のクエリが与えられるので、頂点a[i]からb[i]に行くまでに得られる金額の最大値 or 払わないといけない金額の最小値を求めよ
ただし、頂点aからbに移動する最中、向きを変えることが出来るのは一度だけである

※向きってのは根に向かって進む方向と根から離れる方向の2通りだけ考える
例えば1-2-3って木で3から2に向かう場合、1まで進んでから向きを変えて2に戻るって動きが出来る

解法

一直線にaからbに移動する場合のコストは、事前に頂点1と各頂点のパス上のコストの和を求めておき、aとbのLCAを求めることでO(logn)で求められる
向きを1度だけ変えられるってのを上手く利用して更にコストを増やしたい
始点aと終点bのLCAをvとする

・a=vのとき
aから根方向に進んで、コストが最大になるところで向きを変え、bまでまっすぐ進む
or bまで進んでから更に根と反対方向に進み続け、コストが最大になるところで向きを変え、bに戻る

・b=vのとき
aから根と反対方向に進んで、〜、bまで進む
or bまで進んでから更に根方向に進み続け、〜、bに戻る

・どちらでもないとき
aからvに進んでから更に根方向に進み続け、〜、vに戻り、そのままbまで進む

この3通りが考えられる
あとは各頂点から「根方向に進むときのコストの和の最大値」と「根と逆方向に進むときのコストの和の最大値」を求められれば解ける
これらはどちらも累積和っぽい再帰で求められる

int n, Q, a, b, c, pa[100100], ch[100100], s[100100];
vector<pair<int,int> > e[100100];
LCA lc;

int rec(int v, int p, int sum, int mn) {
	s[v] = sum, pa[v] = sum - mn;
	each(i,e[v]) if (i.first!=p) {
		int tsum = sum + i.second;
		int mx = rec(i.first, v, tsum, min(mn, tsum));
		chmax(ch[v], mx + i.second);
	}
	return ch[v];
}

signed main() {
	cin >> n >> Q;
	rep(i,n-1) {
		cin >> a >> b >> c;
		a--, b--;
		e[a].push_back({b,c}), e[b].push_back({a,c});
		lc.add(a,b);
	}
	rec(0,-1,0,0);
	lc.init(n,0);
	while (Q--) {
		cin >> a >> b;
		a--, b--;
		int v = lc.lca(a,b);
		int res = s[a] + s[b] - s[v]*2;
		if (a==v) res += max(pa[a], ch[b])*2;
		else if (b==v) res += max(ch[a], pa[b])*2;
		else res += pa[v]*2;
		cout << res << endl;
	}
}

https://www.codechef.com/ENCO2018/problems/CTOUR