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が1つのみ対応する形になります。
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";
}

CODE FESTIVAL 2017 Final,F: Distribute Numbers

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

なんでこれ結構解かれているんだろう…

editorialそのままです。違う構成法を考えてハマっていたので、いろいろ試してみようくらいしかこの問題から学べないと思うんですがね…

あと見通しのいい図がかけるかどうかとか?

でもこういう問題は本当に思いつきませんね…

int K = 38, N = K * K - K + 1, P = K - 1;

void solve() {
	cout << N << " " << K << "\n";
	rep(i, 0, P + 1) {
		cout << N << " ";
		rep(j, 0, P) cout << i * P + j + 1 << " ";
		cout << "\n";
	}
	rep(i, 0, P) {
		rep(j, 0, P) {
			rep(k, 0, P) {
				cout << k * P + (j + i * k) % P + 1 << " ";
			}
			cout << P * P + i + 1 << "\n";
		}
	}
}

CODE FESTIVAL 2017 Final,G: Mancala

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

答えは(f(a)の期待値)*(K+1)^Nなのでf(a)の期待値を求めることにします。

まず最小値を達成する操作とはどのようなものなのか考えます。
i番目の値Aiについて最初からAi>iであれば何も操作を行えませんが、Ai<=iなら操作を保留しておいて、i以降で操作を行ったあと、Aiについて出来る限りやると言い換えても良いです。

なので、
dp(i,j):=(i,N]において操作がj回行われる確率
とすれば、期待値の線形性により
f(a)=ΣiΣjΣk G(i, j)*u(i,j,k+l)となります。
ただしu(i,j,s):=s%i(j<=i),s(j>i)です。

問題はjがどのくらい大きくなるかですが、ΣN/iと同じような計算になってO(NlogN)くらいだろうという予測が立ちます。
実際適当なコードで実験すればj<=2000とわかるので、O(2000*N*K)で間に合います。

int N, K;

ll dp[110][2000];
ll S[110];


ll mod_pow(ll a, ll n) {
	if(n == 0) return 1;
	ll res = mod_pow(a, n / 2);
	if(n % 2 == 0) return res * res % mod;
	else return a * res % mod * res % mod;
}


ll f(int i, int k, int s) {
	if(k <= i) return s % i;
	else return s;
}

void solve() {
	cin >> N >> K;
	dp[N][0] = 1;
	rer(i, N + 1, 2) {
		rep(j, 0, 2000) {
			if(!dp[i][j]) continue;
			rep(k, 0, K + 1) {
				if(k <= i) {
					ADD(dp[i - 1][j + (j + k) / i], dp[i][j]);
				}
				else ADD(dp[i - 1][j], dp[i][j]);
			}
		}
	}
	rep(i, 1, N + 1) {
		rep(j, 0, 2000) {
			if(!dp[i][j]) continue;
			rep(k, 0, K + 1) {
				ADD(S[i], dp[i][j] * f(i, k, j + k) % mod);
			}
		}
	}
	ll ans = 0;
	rep(i, 1, N + 1) ADD(ans, S[i] * mod_pow(K + 1, i - 1) % mod);
	cout << ans << "\n";
}

そんな苦戦しなかったけど細部を詰めるのに時間がかかった。