SRM557 Div1 Easy - FoxAndMountainEasy

結構な文量の解説を書いてたんだけど、下書きが消えてやる気がなくなった
てかtopcoderがマジで繋がらん
アプレットはいつも通り永遠にloadingしててアリーナすら問題読み込みに数十分かかる
ペキンのクソオンラインジャッジを遥かに超えるストレスの塊
どっかまともなOJに過去問に関する権利を全部渡して潰れてほしい

手抜き解説

sの部分の移動中にマイナスになる可能性があるのだけが問題で、それさえ避けられればs以外の部分のUとDの順番はどうでもいい
ってことはsの手前に何個Uを詰めるかだけ全部試せばok
適当にシミュレーション

class FoxAndMountainEasy {
public:
	string possible(int n, int x, int y, string s) {
		int m = s.size();
		rep(k,n-m+1) {
			int h = x+k, d = n-k-m, ng = 0;
			each(i,s) {
				if (i=='U') h++;
				else h--;
				if (h<0) ng = 1;
			}
			if (!ng && abs(h-y)<=d && abs(h-y)%2==d%2) return "YES";
		}
		return "NO";
	}
};

AOJ 2313 - ハコの魔女 (Box Witch)

フローの理解が深まる君

問題

n頂点のグラフがあり、最初は辺がm本ある
全ての辺は容量1の無向辺である
辺の追加と削除のクエリがq個与えられる
各操作後の頂点1から頂点nへの最大流を求めよ

2 <= n <= 500
1 <= q <= 1000

解法

最大流はfordfulkerson法で求めるとして計算量はO(FE)
もしクエリが辺追加クエリだけだったら、クエリ毎に増えるフローはたかだか1だからO(QE)で間に合う
辺削除クエリが問題になる
毎回フローを1から計算してるとO(QFE)になって厳しい

頂点aとbを繋ぐ辺を削除するクエリが来たとする
元々この辺をフローが流れていなかった場合、削除しても何も起こらないからただ容量を0にするだけで終わり
a->b方向に1流れていた場合、この辺の容量を0にしてからa->bに1だけフローを流してみる
流せたならこの辺の代替パスが存在するということだから、この辺を消しても問題は起こらない
流せなかったときはaから1、nからbへそれぞれ1だけフローを流す
元々流れていたのと逆方向に流すことで打ち消す感じ
これで辺をなかったことにできる

実装

del_edgeで↑の処理をする
まずfrom->toとto->fromの辺をforループで見つける
(2回ループしてるけどせっかく辺に逆辺の情報も付けてるんだからそれを使うべきだった)
ちなみに一度削除された辺がもう一度追加されることも考えられるけど一番新しいやつを拾うから大丈夫
from->toもto->fromも容量が1残ってたらフローが流れてないってことだから容量を0にして終了
そうじゃなかった場合は逆方向に流してフローを1だけ打ち消す

int n, m, q, a, b, c;

const int MAXV = 555;
class FordFulkerson {
private:
	struct edge {int to, cap, rev;};
	vector<edge> g[MAXV];
	bool used[MAXV];
	int flow;
public:
	void add_edge(int from, int to, int cap = 1) {
		g[from].push_back((edge){to, cap, (int)g[to].size()});
		g[to].push_back((edge){from, cap, (int)g[from].size()-1});
	}
	int dfs(int v, int t, int f) {
		if (v==t) return f;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			edge &e = g[v][i];
			if (!used[e.to] && e.cap>0) {
				int d = dfs(e.to, t, min(f,e.cap));
				if (d>0) {
					e.cap -= d;
					g[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	int getflow(int s, int t) {
		while (1) {
			memset(used,0,sizeof(used));
			int f = dfs(s,t,1<<30);
			if (f==0) return flow;
			flow += f;
		}
	}
	void del_edge(int from, int to) {
		int x, y;
		rep(i,g[from].size()) if (g[from][i].to==to) x = i;
		rep(i,g[to].size()) if (g[to][i].to==from) y = i;
		if (g[from][x].cap && g[to][y].cap) {
			g[from][x].cap = g[to][y].cap = 0;
			return;
		}
		if (g[to][y].cap==0) swap(from,to), swap(x,y);
		g[to][y].cap = 0;
		if (dfs(from,to,1)) return;
		if (flow) flow--;
		memset(used,0,sizeof(used));
		dfs(from,0,1);
		memset(used,0,sizeof(used));
		dfs(n-1,to,1);
	}
};

FordFulkerson ff;

signed main() {
	cin >> n >> m >> q;
	rep(i,m) {
		cin >> a >> b;
		a--, b--;
		ff.add_edge(a,b);
	}
	while (q--) {
		cin >> c >> a >> b;
		a--, b--;
		if (c==1) ff.add_edge(a,b);
		else ff.del_edge(a,b);
		cout << ff.getflow(0,n-1) << endl;
	}
}

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

SRM556 Div1 Easy - XorTravelingSalesman

問題

n個の町があり、i番目の町の価値はa[i]である
最初は町0にいてスコアはa[0]
スコアがpの状態で町iに移動するとスコアはp xor a[i]に変化する
好きな町で終了できるときスコアの最大値を求めよ

1 <= n <= 50
0 <= a[i] <= 1023

解法

d[i][j]: 町iにスコアjでたどり着けるかどうか
というboolのテーブルを再帰で埋めるだけ

class XorTravelingSalesman {
public:
	int n, res = 0;
	bool d[55][1<<10] = {};
	vector<int> a;
	vector<string> e;

	void rec(int v, int x) {
		chmax(res, x);
		d[v][x] = 1;
		rep(i,n) if (e[v][i]=='Y' && !d[i][x^a[i]]) rec(i,x^a[i]);
	}

	int maxProfit(vector<int> a_, vector<string> e_) {
		a = a_, e = e_, n = a.size();
		rec(0,a[0]);
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12175&rd=15178

AOJ 2293 - Dangerous Tower

最小費用流の勉強になった

問題

n個の積み木があり、i番目は1*a[i]*b[i]の直方体の形をしている
これらを積み重ねてなるべく高い塔を作りたい
長さ1の辺を奥行き方向に用いて、他の2辺を横方向と縦方向に1つずつ割り当てる(どっちをどっちにしてもok)
積み上げるとき、上の段の積み木は下の段の積み木より横の長さが厳密に短くなければいけない
作れる塔の高さの最大値を求めよ

1 <= n <= 10^3
1 <= a[i], b[i] <= 10^6

解法

最小費用流に落とし込んで解く

横の長さが異なるように積み木を選べばそれらは全て使える
つまり順番は考えなくてよく、一度横の長さとして使った長さは二度と使えないという条件に言い換えられる
また、塔の高さを点数とすると、「積み木iを使う場合、横の長さをa[i]にするとb[i]点、逆ならa[i]点得られる」と言える
これらをうまく最小費用流で表現するには・・↓

aとbという2n個の値から重複を取り除き、それぞれに1から始まる番号を付ける(座標圧縮)
便宜上これらをまとめてXと呼び、n個の積み木たちはYと呼ぶ
で、↓のように有向辺を張る
・始点からXの各値(各頂点)に容量1コスト0の辺を張る
・Yの各頂点iに向かって、「Xのa[i]に対応する頂点」から容量1コスト-b[i]の辺、「Xのb[i]に対応する頂点」から容量1コスト-a[i]の辺を張る
・Yの各頂点から終点に容量1コスト0の辺を張る
・始点から終点に容量無限コスト0の辺を張る
最後の辺の流量は使わない積み木の個数に対応する
見づらいけどサンプル1は↓のようになる
f:id:creep040:20181018125147p:plain
このグラフで最小費用流を求めて-1をかければそれが答え

実装

各値には1からid-1までの番号が付く
始点: 0
Xの各頂点: 1〜id-1
Yの各頂点: id〜n-1
終点: id+n
という対応

const int MAXV = 4040;
class MCF {
private:
	struct edge {int to, cap, cost, rev;};
	vector<edge> g[MAXV];
	int V, h[MAXV], dist[MAXV], prevv[MAXV], preve[MAXV];
public:
	// fromからtoへ向かう容量capコストcostの辺をグラフに追加する
	void add_edge(int from, int to, int cap, int cost) {
		g[from].push_back((edge){to, cap, cost, (int)g[to].size()});
		g[to].push_back((edge){from, 0, -cost, (int)g[from].size()-1});
	}
	// sからtへの流量fの最小費用流を求める (流せない場合は-1)
	int getflow(int s, int t, int f, int n) {
		V = n;
		int res = 0;
		fill(h, h+V, 0);
		if (0<f) {
			fill(h, h+V, 1<<30);
			h[s] = 0;
			while (1) {
				bool upd = 0;
				for (int i=0; i<V; i++) for (auto &e : g[i]) if (e.cap) {
					if (h[i]==(1<<30)) continue;
					if (h[e.to] > h[i]+e.cost) {
						h[e.to] = h[i] + e.cost;
						upd = 1;
					}
				}
				if (!upd) break;
			}
		}
		while (0<f) {
			priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > que;
			fill(dist, dist+V, 1<<30);
			dist[s] = 0;
			que.push({0,s});
			while (!que.empty()) {
				pair<int,int> p = que.top(); que.pop();
				int v = p.second;
				if (dist[v]<p.first) continue;
				for (int i=0; i<g[v].size(); i++) {
					edge &e = g[v][i];
					if (0<e.cap && dist[e.to] > dist[v]+e.cost+h[v]-h[e.to]) {
						dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
						prevv[e.to] = v, preve[e.to] = i;
						que.push({dist[e.to], e.to});
					}
				}
			}
			if (dist[t]==(1<<30)) return -1;
			for (int v=0; v<V; v++) h[v] += dist[v];
			int d = f;
			for (int v=t; v!=s; v=prevv[v]) d = min(d, g[prevv[v]][preve[v]].cap);
			f -= d;
			res += d*h[t];
			for (int v=t; v!=s; v=prevv[v]) {
				edge &e = g[prevv[v]][preve[v]];
				e.cap -= d;
				g[v][e.rev].cap += d;
			}
		}
		return res;
	}
};

int n, a[1010], b[1010], id = 1;
map<int,int> m;
MCF mcf;

signed main() {
	cin >> n;
	rep(i,n) {
		cin >> a[i] >> b[i];
		if (!m[a[i]]) m[a[i]] = id++;
		if (!m[b[i]]) m[b[i]] = id++;
	}
	reps(i,1,id) mcf.add_edge(0,i,1,0);
	rep(i,n) {
		mcf.add_edge(m[a[i]],id+i,1,-b[i]);
		mcf.add_edge(m[b[i]],id+i,1,-a[i]);
		mcf.add_edge(id+i,id+n,1,0);
	}
	mcf.add_edge(0,id+n,n,0);
	cout << -mcf.getflow(0,id+n,n,id+n+1) << endl;
}

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

ARC064 F - Rotated Palindromes

creep06.hatenablog.com
これにだいぶ似てる

問題

以下の条件を全て満たす数列aを用意する
1) 長さn
2) 各要素は1以上k以下の整数
3) 回文(∴ aを逆順にした数列はaと一致する)
その後aを好きな回数rotateする
最終的なaとしてあり得るものは何通りか

1 <= n <= 10^9
1 <= k <= 10^9

解法

回文の条件があるから、rotateする前のaは手前半分を決めるともう半分は勝手に決まる
手前半分ってのは ceil(n/2) 文字
つまり最初のaとしては k^ceil(n/2) 通り考えられる
またそれぞれについて0〜n-1回rotateできるから、答えは単純に考えると計 n * k^m 個
ただしaが同じ数列を周期的に繰り返すようなときは、n回未満のrotateでaが元に戻るため、実際の答えはこんなに多くない
うまく重複を除く必要がある

最小でd回rotateすると元に戻るようなaは↑と同様に考えると k^ceil(d/2) 個存在する
またそれぞれについてrotate後のaがd通りあり得る
dの値はnの約数全通りあり得る
これらを踏まえて、包除原理の要領で
k^ceil(d/2) - Σ k^ceil(s/2)
(d: nの約数全て、s: dの約数でd以外のもの全て)
にdをかけたものを足し合わせていくと答えが求められる

ってのは嘘
rotate前のaが異なっていてもrotateによって同じ数列になるケースがある
つまり↑だとまだ足しすぎている
具体的にはdが偶数のときは「ある数列a」と「aをd/2回rotateした数列」で2重カウントしてしまう
(例えばn=8, d=4のとき、1221-1221と2112-2112なんかが重複する)
よってdが奇数のときは↑にdをかけたもの、偶数のときはd/2をかけたものを足し合わせていけばいい

ll n, k, num[2020], res;
vector<ll> d;

signed main() {
	cin >> n >> k;
	for (int i=1; i*i<=n; i++) if (n%i==0) {
		d.push_back(i);
		if (i*i!=n) d.push_back(n/i);
	}
	sort(all(d));
	rep(i,d.size()) {
		num[i] = mop(k, (d[i]+1)/2);
		rep(j,i) if (d[i]%d[j]==0) (num[i] += mod - num[j]) %= mod;
		(res += num[i] * d[i] / (d[i]%2 ? 1 : 2)) %= mod;
	}
	cout << res << endl;
}

https://beta.atcoder.jp/contests/arc064/tasks/arc064_d

天下一プログラマーコンテスト2013 決勝 D - 天下一ボディービルコンテスト

包除原理🤤

問題

高橋くんにはn個の筋肉があり、これからd日間毎日トレーニングをする
高橋くんは毎日筋肉を1つ選んでトレーニングしてその筋肉を1kg増やす
またi番目の筋肉は最低でもa[i]kgは増やすという目標がある
n個全ての目標を達成するようなトレーニングスケジュールは何通りあるか

1 <= n <= 30
1 <= d <= 10^9
1 <= a[i] <= 30

解法

「全ての目標を達成」の余事象は「1つ以上の目標を達成しない」になる
f(S): 少なくとも集合Sに含まれる目標は全て達成しないようなトレーニングスケジュールの個数
とすると、答えは包除原理より
Σ f(S) * (-1)^|S|
となる

達成しない目標の集合Sとしては空集合を除いた2^n - 1個ある
まともに計算するのはきついからdpでうまく状態をまとめたい
dp[i][j][k]: i番目まででj個の目標を選び、それらを全て達成しないように計k回のトレーニングを割り振るような場合の数
とすると、j個以上の目標を達成しないようなトレーニングスケジュールの個数は、
Σ dp[n][j][k] * (k回のトレーニングをd日のうちどこに配置するか)
* (残りd-k日を選ばなかったn-j個の筋肉に適当に割り振る組み合わせ)
= Σ dp[n][j][k] * dCk * (n-j)^(d-k) (0 <= k <= Σa[])
というふうに求められる
故に答えは Σ ↑ * (-1)^(j)

dpの遷移は以下の通り

(i番目の目標は考慮しない場合)
dp[i+1][j][k] += dp[i][j][k]

(i番目の目標を考慮に入れる場合)
i番目の筋肉をL (0 <= L < a[i]) 回鍛えるとして、
dp[i+1][j+1][k+L]
+= dp[i][j][k] * (既にあるj個のトレーニングの列の隙間j+1個に重複ありでL個入れる)
= dp[i][j][k] * (j+1)H(L)

実装

dがクソデカいからdCkがちょっとめんどい
事前にdcinit()でテーブルを作っておく
分子と分母をメモしながらkを1増やしていき、(分子)*(分母の逆元) で求めてる(フェルマーの小定理)

dが絡まない組み合わせの数は俺の好きなパスカルの三角形☺️

#define int long long

int n, d, a[33], dp[33][33][1010], pa[1010][1010], dcomb[1010], res;

int comb(int n, int r) {
	if (r<0 || r>n) return 0;
	if (r==0) return 1;
	if (pa[n][r]) return pa[n][r];
	return pa[n][r] = (comb(n-1, r-1) + comb(n-1, r)) %mod;
}

void dcinit() {
	dcomb[0] = 1;
	int num = 1, den = 1;
	reps(i,1,1010) {
		(num *= d-i+1) %= mod;
		(den *= i) %= mod;
		dcomb[i] = num * mop(den,mod-2) %mod;
	}
}

signed main() {
	cin >> n >> d;
	rep(i,n) cin >> a[i];
	dp[0][0][0] = 1;
	rep(i,n) rep(j,n) rep(k,1010) if (dp[i][j][k]) {
		(dp[i+1][j][k] += dp[i][j][k]) %= mod;
		rep(l,a[i]) (dp[i+1][j+1][k+l] += dp[i][j][k] * comb(k+l,l)) %= mod;
	}
	dcinit();
	rep(i,n+1) rep(j,min(1010ll,d+1))
		(res += dp[n][i][j] * dcomb[j] %mod * mop(n-i,d-j) * (i%2 ? -1 : 1)) %= mod;
	(res += mod) %= mod;
	cout << res << endl;
}

https://beta.atcoder.jp/contests/tenka1-2013-final/tasks/tenka1_2013_final_d

SRM603 Div1 Medium - PairsOfStrings

包除原理🤤

問題

以下の条件を満たす文字列のペア(a,b)の個数を求めよ
1) aとbの長さはどっちもn
2) aもbもアルファベットの最初のk文字のみからなる
3) a+c = c+bとなるような文字列cが存在する

1 <= n <= 10^9
1 <= k <= 26

解法

3つ目の条件は、
(aの先頭x文字) = (bの末尾x文字) かつ (aの末尾n-x文字) = (bの先頭n-x文字)
となるようなx (0 <= x <= n)が存在すること と言い換えられる
(これを満たすときはc=(aの先頭x文字)とすれば成り立つ)
つまりbはaを0〜n-1回rotateしたものであればいい
aはk^n通り考えられ、bは1個のaに対してn通り考えられる
ただaをn未満回rotateした時点でaに戻るようなときはbを重複してカウントしてしまうから、その分をいい感じに引いてやる必要がある

aをd(<n)回rotateすると元に戻るってのは、例えばabcabc(d=3)とかbb(d=1)みたいに、aに周期があるようなときである
こういうaはk^d通り存在し、それぞれに対応する重複しないbはd個(aを0〜d-1回rotateしたもの)存在する
このdはnの約数全通りあり得る
これらより答えは包除原理の要領で
Σ [k^d - Σ(k^s)] * d (d: nの正の約数全て、 s: dの正の約数のうちd以外のもの)
となる
例えば周期6のものは一部周期1・2・3のものと重複してるからその分を引く、みたいな感じ

10^9以下の正整数の約数の個数は最大で1344個しかないから計算量はその2乗でも大丈夫
modpowで更にlognが付くけどまあ大丈夫

class PairsOfStrings {
public:
	int getNumber(int n, int k) {
		vector<int> d;
		for (int i=1; i*i<=n; i++) if (n%i==0) {
			d.push_back(i);
			if (i*i!=n) d.push_back(n/i);
		}
		sort(all(d));
		ll m = d.size(), res = 0, num[2020] = {};
		rep(i,m) {
			num[i] = mop(k,d[i]);
			rep(j,i) if (d[i]%d[j]==0) (num[i] += mod - num[j]) %= mod;
			(res += num[i] * d[i]) %= mod;
		}
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12788&rd=15836