「みんなのプロコン」本選C: 倍数クエリ

https://yahoo-procon2017-final-open.contest.atcoder.jp/tasks/yahoo_procon2017_final_c

平方分割やるだけです。

初期化の時にセグフォ起こしたのでそれだけ気をつけましょう。

const int BLOCK = 300;
const int CNT = MAX_N / BLOCK + 10;

int N, M;
int Q;

ll A[MAX_N];
int B[CNT];
int C[CNT][BLOCK];
int D[CNT][MAX_N];

void push(int id) {
	for(int i = id * BLOCK; i < (id + 1) * BLOCK; i++) {
		A[i] += B[id];
		A[i] %= M;
	}
	B[id] = 0;
}

void pull(int id, bool first = false) {
	rep(i, 0, BLOCK) {
		if(!first) D[id][C[id][i]]--;
		C[id][i] = A[id * BLOCK + i];
		D[id][C[id][i]]++;
	}
}

void update_block(int id, int k) {
	B[id] += k;
	B[id] %= M;
}

int get_block(int id) {
	return D[id][(M - B[id]) % M];
}

void solve() {
	cin >> N >> M >> Q;
	rep(i, 0, N) {
		cin >> A[i];
		A[i] %= M;
	}
	rep(id, 0, N / BLOCK + 1) pull(id, true);

	while(Q--) {
		int l, r, k;
		cin >> l >> r >> k; l--;
		k %= M;

		int cnt = 0;

		int lid = l / BLOCK, rid = r / BLOCK;
		push(lid); push(rid);
		while(l < r && l < (lid + 1) * BLOCK) {
			A[l] += k;
			A[l] %= M;
			if(!A[l]) cnt++;
			l++;
		}
		while(l < r && r > rid * BLOCK) {
			A[r - 1] += k;
			A[r - 1] %= M;
			if(!A[r - 1]) cnt++;
			r--;
		}
		pull(lid); pull(rid);
		for(int id = lid + 1; id < rid; id++) {
			update_block(id, k);
			cnt += get_block(id);
		}
		cout << cnt << "\n";
	}
}

第4回 ドワンゴからの挑戦状 予選,E: ニワンゴくんの家探し

https://dwacon2018-prelims.contest.atcoder.jp/tasks/dwacon2018_prelims_e

これはそんなに難しくない。

重心分解して、一番部分木が大きい頂点から列挙します。
重心がsだとして、子が{a, b, c, d, e}だったとします。
そしたら(a,b)をまず聞いてaだったらaの木に潜りbだったらbの木に潜ります。0だったら(c,d)を聞きます。
同じようにして(c,d)が0の時は(s,e)を聞いてeならeの木に潜り、sならsを出力します。

こうすれば(a,b)で潜る木が確定すれば1回の質問で元の木の1/2未満に、
(c,d)で潜る木が確定すれば2回の質問で元の木の1/3未満に、
(e,s)で潜る木が確定すれば3回の質問で元の木の1/5未満になります。

効率的に一番劣っているのは(e,s)で潜る木が確定する場合ですが、
5^(12/4)=625なのでN=2000なら12回質問することで候補を3頂点に絞れ、あとの2回で求める頂点を確定できそうだとわかります。

あとendlで出力しないとTLEするので注意しましょう。

namespace CD { //centroid decomposition

	struct edge { int to, length; };

	vector<edge> G[MAX_N];
	bool centroid[MAX_N];
	int subtree_size[MAX_N];

	void init(int n) {
		rep(i, 0, n) G[i].clear();
	}
	void add_edge(int a, int b, int c) {
		G[a].push_back((edge){b, c});
		G[b].push_back((edge){a, c});
	}

	int compute_subtree_size(int v, int p) {
		int c = 1;
		rep(i, 0, (int)G[v].size()) {
			int w = G[v][i].to;
			if(w == p || centroid[w]) continue;
			c += compute_subtree_size(G[v][i].to, v);
		}
		subtree_size[v] = c;
		return c;
	}

	pi search_centroid(int v, int p, int t) { 
		pi res = pi(inf, -1);
		int s = 1, m = 0;
		rep(i, 0, (int)G[v].size()) {
			int w = G[v][i].to;
			if(w == p || centroid[w]) continue;

			MIN(res, search_centroid(w, v, t));

			MAX(m, subtree_size[w]);
			s += subtree_size[w];
		}
		MAX(m, t - s);
		MIN(res, pi(m, v));
		return res;
	}


	void solve_subproblem(int v) {
		compute_subtree_size(v, -1);
		int cen = search_centroid(v, -1, subtree_size[v]).sec;
		centroid[cen] = true;

		set<pi> s;

		rep(i, 0, (int)G[cen].size()) {
			int n = G[cen][i].to;
			if(centroid[n]) continue;
			s.insert(pi(-subtree_size[n], n));
		}

		while(sz(s) >= 2) {
			auto p1 = (*s.begin()); s.erase(p1);
			auto p2 = (*s.begin()); s.erase(p2);
			int a = p1.sec, b = p2.sec;
			int c;
			cout << "? " << a + 1 << " " << b + 1 << endl;
			cin >> c;
			if(c == a + 1) {
				solve_subproblem(a);
				return;
			}
			else if(c == b + 1){
				solve_subproblem(b);
				return;
			}
		}
		if(sz(s) == 1) {
			auto p1 = (*s.begin());
			int a = p1.sec, b = cen;
			int c;
			cout << "? " << a + 1 << " " << b + 1 << endl;
			cin >> c;
			if(c == a + 1) {
				solve_subproblem(a);
				return;
			}
		}
		cout << "! " << cen + 1 << endl;
		return;

		centroid[cen] = false;
	}
}

int N, Q;

void solve() {
	cin >> N >> Q;
	rep(i, 0, N - 1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		CD::add_edge(a, b, 1);
	}
	CD::solve_subproblem(0);
}

重心分解するしかないからだいぶ見通しがつきやすいですね。

AtCoder Grand Contest 012E: Camel and Oases

https://agc012.contest.atcoder.jp/tasks/agc012_e

アイディア自体はすんなりいけたけどいろいろ勘違い+バグで無限に時間がかかった…。

とり方を見てみると、容量Vでジャンプしないで取るオアシスの区間,V/2で取る区間、(V/2)/2で取る区間…があって、それぞれの区間が互いに独立であることがわかります。つまり、スタート地点を含むVの区間でstrip,V/2でstrip...としていき、全オアシスが取れればPossible、そうでなければImpossibleとなります。この操作を逆に見ると、端から区間を好きな順番で取っていく操作になります。なので、
dp[bit]:=i番目のbitが立っている時、容量i番目の区間をすでにとっているとする。その時端から最大どこまで取れるか
として左端右端についてdpをしてあげればどの範囲がスタート地点として適しているか求めることができます。
doublingとかして高速化すればO(N(logN)^2)となり、低数倍も軽いので余裕で通ります。

といえば簡単だけど、意外と範囲がややこしくて結構苦戦しました。

さらに-1で初期化をしないと行けないところを0で初期化してバグらせました…。考察実装ともにパフォーマンスがひどいですねこれは…。

int N, V;
int M, SM;

int T[22][MAX_N];
int nex[22][MAX_N];

int dp[(1 << 22)], rdp[(1 << 22)];
int ok[MAX_N];

vector<ll> v;
ll A[MAX_N];

void pre(int dp[MAX_N]) {
	rep(i, 0, M) {
		rep(j, 0, N - 1) {
			T[0][j] = (abs(A[j + 1] - A[j]) > v[i]) ? j : (j + 1);
		}
		T[0][N - 1] = N - 1;
		rep(q, 0, 20) {
			rep(j, 0, N) {
				T[q + 1][j] = T[q][T[q][j]];
			}
		}
		rep(j, 0, N) {
			nex[i][j] = T[20][j];
		}
	}
	fill(dp, dp + (1 << SM), -1);
	rep(bit, 0, (1 << SM)) {
		if(dp[bit] == N - 1) continue;
		rep(i, 0, SM) {
			if(bit & (1 << i)) continue;
			MAX(dp[bit | (1 << i)], nex[i][dp[bit] + 1]);
		}
	}
	rep(bit, 0, (1 << SM)) {
		if(dp[bit] == N - 1) continue;
		dp[bit] = nex[SM][dp[bit] + 1];
	}
}

void solve() {
	cin >> N >> V;
	rep(i, 0, N) cin >> A[i];
	while(V >= 1) {
		v.pb(V);
		V /= 2;
	}
	v.pb(0);
	M = sz(v);
	SM = M - 1;

	reverse(all(v));
	
	pre(dp);

	reverse(A, A + N);
	pre(rdp);

	rep(bit, 0, (1 << SM)) rdp[bit] = N - 1 - rdp[bit];

	rep(bit, 0, (1 << SM)) {
		int rbit = (1 << SM) - 1 - bit;
		int l = dp[bit], r = rdp[rbit];
		l++;
		if(l > r) {
			ok[l]--;
			ok[r]++;
		}
	}
	rep(i, 0, N) {
		ok[i + 1] += ok[i];
		if(ok[i]) cout << "Possible\n";
		else cout << "Impossible\n";
	}
}

DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦,D: シャツの部屋

https://ddcc2016-final.contest.atcoder.jp/tasks/ddcc_2016_final_d

これは本当に良問だと思います。

まずi-1回洗濯するとすると、i+k回洗濯すると破れる服は全部i回とみなせます。
Mが小さければdp[i][j]:=i回洗濯する服まで見てj日シャツを着られる方法で最小コストのもの
で簡単にできますが今回はMが破滅的にデカイので無理です。
でも感覚的にはB/Aが小さいものを使うのが良くて、実際B/Aが最小の服がm回洗濯すると破れる服ならば、他の服はm回以上使わないことが示せます。これはmodで考えるとわかります。

m<500であり、(服の持つ日数)<500なので(最小の服以外の日数の合計)<500*500となります。なので、
dp[i][j]:=i回洗濯する服まで見てj日シャツを着られる方法で最小コストのもの(上の式と全く同じ)と定義して無制限個数ナップサック問題をときます。あとは最小の服を使ってM日に達するようにした時の最小コストを求めます。これで計算量はO((maxA)^3)となり解けました。

状態から攻めるパターンのDPですね。このタイプはなかなか見ないので苦手です。さらにm回が上界なのも結構非自明で難しいとおもいます。
chokudaiさんが作問者ということで、マラソンすればこういうの得意になるのかも?

数式に走ったんですがやっぱりダメですね。DPしようという気分になるべきでした。

int N; ll M, C;
ll cost[MAX_N];
ll dp[500 * 520];

bool comp(const pl& p1, const pl& p2) {
	return p1.fst * p2.sec < p1.sec * p2.fst;
}

void solve() {
	cin >> N >> M >> C;
	rep(i, 1, 500 + 1) cost[i] = inf;
	rep(i, 0, N) {
		ll a, b;
		cin >> a >> b;
		MIN(cost[a], b);
	}
	rer(i, 500, 1) MIN(cost[i], cost[i + 1]);
	rep(i, 0, 500 * 500) dp[i] = linf;

	pl ratio = pl(inf, 0);
	dp[0] = 0;

	ll ans = linf;
	rep(i, 1, 500 + 1) {
		ll b = cost[i];
		if(comp(pl(b, i), ratio)) ratio = pl(b, i);
		if(b == inf) break;
		rep(j, 0, 500 * 500) {
			MIN(dp[j + i], dp[j] + b);
		}
		ll B = ratio.fst, A = ratio.sec;

		rep(j, 0, 500 * 500) {
			MIN(ans, C * (i - 1) + B * max(0LL, (M - j + A - 1) / A) + dp[j]);
		}
	}
	cout << ans << "\n";
}

CODE FESTIVAL 2016 Grand Final,E: Water Distribution

https://cf16-exhibition-final-open.contest.atcoder.jp/tasks/cf16_exhibition_final_e

初手が難しい…。

グラフの水の容量がB,水をやり取りする辺の距離の合計をA,都市の数をKとすると、なんと最大値は(B-A)/Kであることが証明できます。
Aは都市K個の最小全域木のコストにするのが最適なのは自明ですね。
あとは連結成分が複数ある場合を考えればいいです。これはよくあるO(N*3^N)のDPでできます。

絶対二分探索でしょ、って思いましたが全然違いましたね…。見通し悪かったらすぐ方針を変えるべきなのはわかっているけどなかなかできないです…。必要条件が実は十分条件でもある場合のように、上界を見つけたらそれが最大値かどうか見てみるのも重要ですね。

typedef pair<pi, double> pd;

int N;
double C[(1 << 15)];
double dp[(1 << 15)];

double X[15], Y[15], cap[15];

int par[MAX_N];

int find(int p) {
	if(p == par[p]) return p;
	else return par[p] = find(par[p]);
}

double dist(int a, int b) {
	double dx = X[a] - X[b], dy = Y[a] - Y[b];
	return sqrt(dx * dx + dy * dy);
}

double pre(int bit) {
	vector<pd> e;
	rep(i, 0, N) {
		rep(j, i + 1, N) {
			if(!(bit & (1 << i)) || !(bit & (1 << j))) continue;
			e.pb(make_pair(pi(i, j), dist(i, j)));
		}
	}
	sort(all(e), [](const pd& p1, const pd& p2){return p1.sec < p2.sec;});

	rep(i, 0, N) par[i] = i;
	double res = 0;
	for(auto p : e) {
		int a, b;
		tie(a, b) = p.fst;
		double d = p.sec;
		a = find(a); b = find(b);
		if(a != b) {
			res -= d;
			par[a] = b;
		}
	}

	int cnt = 0;
	rep(i, 0, N) {
		if(!(bit & (1 << i))) continue;
		cnt++;
		res += cap[i];
	}
	return res / cnt;
}

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> X[i] >> Y[i] >> cap[i];
	rep(bit, 1, (1 << N)) {
		C[bit] = pre(bit);
	}
	rep(i, 0, (1 << N)) dp[i] = -inf;

	dp[0] = inf;
	rep(bit, 0, (1 << N)) {
		vector<int> vec;
		rep(i, 0, N) {
			if(!(bit & (1 << i))) vec.pb(i);
		}
		int sn = sz(vec);
		rep(bit2, 1, (1 << sn)) {
			int sbit = 0;
			rep(i, 0, N) {
				if(!(bit2 & (1 << i))) continue;
				sbit |= (1 << vec[i]);
			}
			dp[bit | sbit] = max(dp[bit | sbit], min(dp[bit], C[sbit]));
		}
	}
	cout << dp[(1 << N) - 1] << "\n";
}

比較関数をオシャレにラムダ式でキメてみました。
あと3^N*DPのもっと良い書き方があるみたいなので後で見ておきます。今は配列使っていて定数倍めちゃくちゃ重いです。

CODE FESTIVAL 2017 Final,E: Combination Lock

https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_e

まず区間の真ん中をまたぐ部分は考えなくていいです。
すると区間は左or右に寄った形になりますが、右にある区間を左に移しても問題ありません。
よって左半分に操作を行って右半分の文字列に一致させる問題になりました。

さらに
[l, r],[l, r'](r < r')のような2つの区間は[l, r],[r, r']と言い換えられます。
これを適用することで、すべての[l, r]について、あるlに対してはrが１つのみ対応する形になります。
setをmergeしていくunionfindを使えばO(N(logN)^2)でこの形を求めることができます。

ここまでできればあとはBITを使って端から文字列を一致させていけばいいです。

割と実装重かったけどそんなにてこずらなくてよかった。

int N, Q;
int A[MAX_N];
vector<int> G[MAX_N];
int to[MAX_N];
BIT bit;

struct mergeUF { //O((logn)^2)
	int n;
	vector<set<int>> g;
	vector<int> gat;

	int find(int p) {
		if(gat[p] == p) return p;
		else return gat[p] = find(gat[p]);
	}

	void init() {
		n = N / 2 + 1;
		g.resize(n); gat.resize(n);
		rep(i, 0, n) {
			rep(j, 0, sz(G[i])) {
				int v = G[i][j];
				g[i].insert(v);
			}
			gat[i] = i;
		}
	}


	void unite(int x, int y) {
		int a = find(x), b = find(y);
		if(a == b) return;
		if(sz(g[a]) > sz(g[b])) swap(a, b);
		gat[a] = b;

		for(int s : g[a]) {
			g[b].insert(s);
		}
		g[a].clear();
	}

	bool same(int x, int y) { return find(x) == find(y); }
} uf;


void solve() {
	string str;
	cin >> str;
	N = sz(str);
	rep(i, 0, N) A[i] = str[i] - 'a';

	cin >> Q;
	rep(i, 0, Q) {
		int a, b;
		cin >> a >> b; a--; b--;
		int m1 = (N - 1) / 2, m2 = N / 2;
		if(a <= m1 && m2 <= b) {
			if(m1 - a <= b - m2) a = N - 1 - a + 1;
			else b = N - 1 - b - 1;
		}
		if(a >= m2) {
			int ta = a, tb = b;
			a = N - 1 - tb;
			b = N - 1 - ta;
		}
		b++;
		if(b > a) G[a].pb(b);
	}

	uf.init();
	bit.init(N / 2 + 10);

	rep(i, 0, N / 2) bit.update(i, i + 1, A[i]);
	memset(to, -1, sizeof(to));

	rep(i, 0, N / 2) {
		int a = uf.find(i);
		if(uf.g[a].empty()) continue;
		auto it = uf.g[a].begin();
		int tmp = *it;
		to[i] = tmp;
		uf.g[a].erase(it);
		uf.unite(i, tmp);
	}

	rep(i, 0, N / 2) {
		int a = bit.get(i, i + 1) % 26, b = A[N - 1 - i] % 26;
		if(to[i] == -1) {
			if(a != b) {
				cout << "NO\n";
				return;
			}
		}
		else {
			int t = (b - a + 26) % 26;
			bit.update(i, to[i], t);
		}
	}
	cout << "YES\n";

}

想定解はまず累積和をかんがえて、区間の端を+1-1する操作に言い換えています。これは思いつきたかった。
そこからがすごい頭良くて感心しました(こなみかん)

「みんなのプロコン 2018」E: グラフの問題

https://yahoo-procon2018-qual.contest.atcoder.jp/tasks/yahoo_procon2018_qual_e

検索するとこんなのが出てきます。

次数 (グラフ理論) - Wikipedia

ここにある式をそのまま使えばいいです。

1を足す時でも式で考えれば一番小さい次数を1上げれば良いことがわかります。

ただ式を勘違いして読んで無限にWAを出した…流石に不注意がすぎる。

int N;
ll A[MAX_N];
ll S[MAX_N], SD[MAX_N];

ll f(ll at) {
	ll lv = -1, rv = N;
	while(rv - lv > 1) {
		int m = (lv + rv) / 2;
		if(A[m] < at) rv = m;
		else lv = m;
	}
	ll v = max(rv, at);
	ll res = (S[N] - S[v]) + (v - at) * at;
	return res;
}

bool ok() {
	sort(A, A + N, greater<ll>());

	memset(S, 0, sizeof(S));
	memset(SD, 0, sizeof(SD));

	rep(i, 0, N) S[i + 1] = S[i] + A[i];

	rep(i, 0, N) {
		if((S[i + 1] - S[0]) - f(i + 1) > 1LL * i * (i + 1)) {
			return false;
		}
	}
	return true;
}

int sub_solve() {
	ll s = 0;
	rep(i, 0, N) s += A[i];
	if(s % 2 == 0) {
		if(ok()) return 0;
		else return 2;
	}
	else {
		A[0]++;
		if(ok()) return 1;
		else return 2;
	}
}

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	int s = sub_solve();
	if(s == 0) cout << "YES\n";
	else if(s == 1) cout << "NO\n";
	else cout << "ABSOLUTELY NO\n";
}