2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest,D: Packmen Strike Back

http://codeforces.com/problemset/problem/883/D

これは考察系のDP。

場合分けでtrivialな場合は別で処理します。

非自明(Pが2つ以上ある)の時、まず二分探索して、距離Kすすめるとき*をすべて覆えるか?という問題を解くことを考えます。

dp(i):=i番目のPを使った時、*をカバーできる範囲が[0, l)だとして、lの最大値とします。
するとi+1番目のPがi番目の時点でカバーできているのなら、区間は必ず右に伸ばせばいいです。
カバーできてないとすると、[dp(i),P(i+1)の区間をカバーするのはi+1番目のP、またはi+2番目のPとなります。
なぜなら、i+k番目(k>=3)のPでその区間をカバーしたとすると、i+k-1番目のPは右に伸ばす場合が、dp(i+k)の候補になりえます。しかしi+k-2以下は右に伸ばすのも左に伸ばすのも自由になり、i+1番目のPでカバーしても問題ありません。

なのでdp(i)を更新するためにはdp(i-1)とdp(i-2)の値のみだけが必要で、dp(N)で求められます。
全部でO(NlogN)となり十分間に合います。

O(N)個参照しないといけないと見せて実はO(1)で済む系DPですね。
http://codeforces.com/contest/853/problem/D(解いてないけど)
とかもこれと同じ系統です。

int N, M;
string str;
int minv, maxv;
int P[1000010];
int S[1000010];
int dp[1000010];

bool exist(int l, int r) {
	return ((r > l) && (S[r] - S[l]));
}

bool C(int m) {
	rep(i, 0, M + 1) dp[i] = 0;
	rep(i, 1, M + 1) {
		int e = P[i - 1] + 1;
		if(!exist(dp[i - 1], e - m - 1)) MAX(dp[i], e);
		if(!exist(dp[i - 1], e)) MAX(dp[i], e + m);
		if(i != 1) {
			int f = P[i - 2] + 1;
			if(!exist(dp[i - 2], e - m - 1)) MAX(dp[i], f + m);
		}
	}
	// debug(m, vi(dp, dp + M + 1));
	return dp[M] > maxv;
}

void solve() {
	cin >> N >> str;
	M = 0;
	rep(i, 0, N) {
		if(str[i] == 'P') P[M++] = i;
		S[i + 1] = S[i] + (str[i] == '*');
	}
	minv = inf; maxv = -inf;
	rep(i, 0, N) {
		if(str[i] != '*') continue;
		MIN(minv, i);
		MAX(maxv, i);
	}
	if(M == 1) {
		int p = P[0];
		int lc = S[p], rc = S[N] - S[p];
		if(lc > rc) {
			cout << lc << " " << p - minv << "\n";
		}
		else if(lc < rc) {
			cout << rc << " " << maxv - p << "\n";
		}
		else { //lc == rc
			cout << lc << " " << min(maxv - p, p - minv) << "\n";
		}
		return;
	}
	C(2);
	int lv = 0, rv = N;
	while(rv - lv > 1) { //minimize
		int m = (lv + rv) / 2;
		if(C(m)) rv = m;
		else lv = m;
	}
	cout << S[N] << " " << rv << "\n";
}

CODE FESTIVAL 2017 qual C,F: Three Gluttons

https://code-festival-2017-qualc.contest.atcoder.jp/tasks/code_festival_2017_qualc_f

解説と完全に同じことしたけどそれでも結構バグらせた。

頑張って問題を変形していくと、解説の2つめの四角で囲ってあるような問題に落とし込めます。
ここからが難しくて、ctがどのような条件を満たすか考えていきます。
作業を後ろからみると(ここが思いつかない)ctはa(t+1),b(t+1),c(t+1)以降に含まれず、かつ(a0,a1,...,at,b0,b1,...,bt)に含まれない要素になります。この数をf(it, jt, t)とすると、求めるのはΠf(it,jt,t)の和です。ここでdp(i,j,t):=(it'=i,jt'=jの時のΠ(1,..,t')f(it,jt,t))の和と定義すると、
dp(i,j,t)=f(i,j,t)*Σ(x < i,j < y)dp(x,y,t-1)となるので遷移がいい感じにまとめられてO(N^3)になります。

後ろから見る考え方はよくあるけどこういう複雑な問題でなかなか使えないですね。
あとctというある要素1つだけに注目して考えるというのも大事です。

この問題からわかるように、DPの計算量を落とすときは、簡単な数式の形に変形して遷移をじっくり見ることが重要になりそうです。そうするとsegtreeに落とし込めたり、累積和が使えたりします。

int N, n;
ll dp[400][400][134];
bool circ[400][400][400];
int cnt[410][410];
int A[410], B[410];

int f(int i, int j, int t) {
	return max(N - 3 * (n - t) - cnt[i][j], 0);
}

void solve() {
	cin >> N; n = N / 3;
	rep(i, 0, N) {
		cin >> A[i]; A[i]--;
	}
	rep(i, 0, N) {
		cin >> B[i]; B[i]--;
	}
	if(A[0] == B[0]) {
		cout << "0\n";
		return;
	}
	rep(i, 0, N + 1) {
		rep(j, 0, N + 1) {
			if(j - 1 >= 0) {
				rep(k, 0, N) circ[i][j][k] = circ[i][j - 1][k];
				circ[i][j][B[j - 1]] = 1;
			}
			else if(i - 1 >= 0) {
				rep(k, 0, N) circ[i][j][k] = circ[i - 1][j][k];
				circ[i][j][A[i - 1]] = 1;
			}
			cnt[i][j] = accumulate(circ[i][j], circ[i][j] + N, 0);
		}
	}
	rep(i, 0, N) {
		dp[i][0][1] = 1; dp[0][i][1] = 1;
	}
	rep(i, 1, N) {
		rep(j, 1, N) {
			rep(k, 1, n + 1) {
				if(!circ[i][j][A[i]] && !circ[i][j][B[j]] && A[i] != B[j]) {
					dp[i][j][k] = dp[i - 1][j - 1][k - 1] * f(i + 1, j + 1, k) % mod;
				}
				ADD(dp[i][j][k], (dp[i - 1][j][k] + dp[i][j - 1][k] - dp[i - 1][j - 1][k] + mod) % mod);
			}
		}
	}
	ll res = dp[N - 1][N - 1][n];
	rep(i, 0, n) {
		MUL(res, (N - i * 3 - 1) * (N - i * 3 - 2) % mod);
	}
	cout << res << "\n";
}

MLEしまくった…。

AtCoder Regular Contest 085F: NRE

https://beta.atcoder.jp/contests/arc085/tasks/arc085_d

配るDPともらうDPでわけわかんなくなってしまった…。
配るDPは操作を考えて、1手進めるとどこに遷移するかを考えるのが基本となります。
対して、もらうDPは漸化式を立ててからメモ化再帰に持っていく感じで、1手すすめるとかそういう考え方はあまりしないです。

今回のはdp(i,j):=[i,j)まで1が連続しているとしてiまでのハミング距離の差、と定義すると、
iをi+1に持っていくのを1手として遷移を考えるっていう感じになります。するといい感じにsegtreeが使えてO(NlogN)となります。

でもDPを考察する際はやっぱり小さい問題から簡単な遷移で大きな問題を解けないか考えてみて、操作についてはそのあとコードに落とす際に考えればいいかなと思いました。

int N, Q;
int B[MAX_N];
vector<int> L[MAX_N];
segtree seg;
bool used[MAX_N];

ll bitmin(ll a, ll b) {
	return -a + min(a, b);
}

void solve() {
	cin >> N;
	rep(i, 0, N) {
		cin >> B[i];
	}
	cin >> Q;
	rep(i, 0, Q) {
		int a, b;
		cin >> a >> b; a--;
		L[a].pb(b);
	}
	seg.init(N + 1);
	rep(i, 0, sz(L[0])) {
		int v = L[0][i];
		used[v] = true;
	}
	rep(i, 0, N + 1) {
		if(used[i] || !i) continue;
		seg.update(i, i + 1, N);
	}
	rep(i, 1, N + 1) {
		seg.update(i, N + 1, (1 != B[i - 1]));
		int tv = seg.get(i - 1, i).v;
		seg.update(i, i + 1, bitmin(seg.get(i, i + 1).v, tv + (0 != B[i - 1])));
		rep(j, 0, sz(L[i])) {
			int to = L[i][j];
			seg.update(to, to + 1, bitmin(seg.get(to, to + 1).v, seg.get(i, to + 1).v));
		}
	}
	cout << seg.get(N, N + 1) << "\n";
}

Codeforces Bubble Cup X - Finals,E: Casinos and travel

http://codeforces.com/problemset/problem/852/E

初全方位木DPです。

観察するとGood Moodになる方法とBad Moodになる方法は同じ数だけあります。なのでGood Moodのみ考えれば良くて、
全方位木DPをすれば簡単に求められます。

全方位木DPについてですが、これは簡単で木から1つ子を除いた場合を考えて根からdfsするだけです。

int N;
vector<int> E[MAX_N];
ll g[MAX_N];
ll G[MAX_N];
int ts[MAX_N];

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 invf(ll a) {
	return mod_pow(a, mod - 2);
}

ll dfs1(int v, int p) {
	ll res = 1;
	ts[v] = 1;
	bool found = false;
	rep(i, 0, sz(E[v])) {
		int n = E[v][i];
		if(n == p) continue;
		MUL(res, dfs1(n, v));
		ts[v] += ts[n];
		found = true;
	}
	if(!found) return g[v] = 1;
	else return g[v] = 2 * res % mod;
}

void dfs2(int v, int p, ll pv) {
	// debug(v, p, pv);
	G[v] = 2;
	rep(i, 0, sz(E[v])) {
		int n = E[v][i];
		if(n == p) MUL(G[v], pv);
		else MUL(G[v], g[n]);
	}
	rep(i, 0, sz(E[v])) {
		int n = E[v][i];
		if(n == p) continue;
		if(ts[n] == N - 1) dfs2(n, v, 1);
		else dfs2(n, v, G[v] * invf(g[n]) % mod);
	}
}

void solve() {
	cin >> N;
	if(N == 1) {
		cout << 1 << "\n";
		return;
	}
	rep(i, 0, N - 1) {
		int a, b;
		cin >> a >> b; a--; b--;
		E[a].pb(b);
		E[b].pb(a);
	}
	dfs1(0, -1);
	dfs2(0, -1, 1);
	ll ans = 0;
	// debug(vi(g, g + N));
	// debug(vi(G, G + N));
	rep(i, 0, N) ADD(ans, G[i]);
	cout << ans << "\n";
}

テストケースが12個しかないんですがこれは大丈夫なんですかね…

SRM 642

Easy
dp[i]:=時刻iにバスがつく確率、でdpを更新して期待値求めればいいです。

struct WaitingForBus {
  vector<int> time;
  vector<int> prob;
  int s;
  double dp[200110];

  double whenWillBusArrive(vector<int> _time, vector<int> _prob, int _s) {
    time = _time, prob = _prob, s = _s;
	int n = sz(time);
	dp[0] = 1;
	rep(i, 0, s) {
		rep(j, 0, n) {
			dp[i + time[j]] += dp[i] * prob[j] / 100.0;
		}
	}
	double res = 0;
	rep(i, 0, 100000 + 10) {
		res += dp[s + i] * i;
	}
    return res;
  }
};

5 minutes 39 secs。これでも5分かかってるんか…

AtCoder Regular Contest 084D: Small Multiple

https://beta.atcoder.jp/contests/arc084/tasks/arc084_b

iからi+1に移動する際、cost 1で、i*10に移動する際cost 0と考えてiのmodKのグラフで最短経路長を求めればいいです。
と言われると簡単だけど絶対本番思いつかない。

解説に01bfsとかいうのが載っていたのでそれで実装しました。queue内は必ず最短経路長が短い順番で並ぶので、各頂点について1回の更新しか行われないのがポイントです。計算量は結局辺の数で決まります。ダイクストラはそれを実現させるため頂点に加え、長さも持っているんですね。

int K;
int d[100010];

void solve() {
	cin >> K;
	fill(d, d + K, inf);
	d[1] = 1;
	deque<int> que;
	que.push_front(1);
	while(!que.empty()) {
		int v = que.front(); que.pop_front();
		int to = (v + 1) % K;
		// if(d[v] != inf) continue; //don't need this kind of things
		if(d[to] > d[v] + 1) {
			d[to] = d[v] + 1;
			que.push_front(to);
		}
		to = (v * 10) % K;
		if(d[to] > d[v]) {
			d[to] = d[v];
			que.push_back(to);
		}
	}
	cout << d[0] << "\n";
}
 

AtCoder Regular Contest 084E: Finite Encyclopedia of Integer Sequences

https://beta.atcoder.jp/contests/arc084/tasks/arc084_c

0-originでfloor((X+1)/2)-1番目を求める問題です。Xが十分大きければ、最初の文字は(K+1)/2になり、
Nを1つ減らした時の((X+1)/2)-1-(X%2)番目を求めればいいです。なので、X%2の累積分を考えると必ずNよりも小さいので((X+1)/2)-1がNよりも大きい間は必ず最初の文字は(K+1)/2になります。なので、その間は(K+1)/2を取り続け、N未満になったらXの値は普通にlong longに収まるので愚直に計算すればいいです。

床関数の扱いが下手で無限に±1の差で悩んだ…考察の際||だとわかりにくいのでfloor()と書くようにしましょう。
辞書順の問題が苦手という先入観もさっさと取りさらいたい。

int N, K;
ll powK[300010];
ll powS[300010];

void solve() {
	cin >> K >> N;
	if(K % 2 == 0) {
		cout << (K + 1) / 2 << " ";
		rep(i, 0, N - 1) {
			cout << K << " ";
		}
		return;
	}
	memset(powK, -1, sizeof(powK));
	memset(powS, -1, sizeof(powS));

	powK[0] = 1;
	powS[0] = 0;
	rep(i, 1, N + 1) {
		powK[i] = powK[i - 1] * K;
		powS[i] = powS[i - 1] + powK[i];
		if((powS[i] + 1) / 2 > N) break;
	}
	int at = 0, off = 0;
	while(powS[N - at] == -1) {
		cout << (K + 1) / 2 << " ";
		off += (N - at - 1) % 2;
		at++;
	}
	ll m = (powS[N - at] + 1) / 2 - 1 - off;
	while(true) {
		ll xnext = powS[N - at] / K;
		cout << (m / xnext) + 1 << " ";
		m %= xnext;
		if(m == 0) return;
		else m--;
		at++;
	}
}

rep(i,1,N+1)をrep(i,1,N)にしてREした。朝起きて見たら気づいたけど、絶対コンテスト中気づかない…
あと(i%2)を全部足し合わせると(N-1)/2になるので(K+1)/2,(K+1)/2,...,(K+1)/2の(N-1)/2だけ前の数列を考えればいいだけですね…無駄に再帰的に考えてしまった。