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だけ前の数列を考えればいいだけですね…無駄に再帰的に考えてしまった。

AtCoder Regular Contest 084F: XorShift

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

bitの扱いもうちょっとわかってたらもうちょっと早く思いついたかな。

すべての数がある数Pによって構成できることが証明できます。これときPはgcdに他なりません。
なのでgcdをユークリッドの互除法チックなことをして求めればいいです。

Pで構成できる数のうちX以下の数の個数を数え上げるのは簡単なDPでできます。しかし、場合分けをミスってWA。最後+1するかしないかでWAの2WA。

最初は線形代数っぽいし、rank求めるのが本質かなと思ったけど全然違った。

const int N = 4010;
ll pow2[4020];

vi bxor(const vi& a, const vi& b) {
	vi res(N, 0);
	rep(i, 0, N) res[i] = (a[i] ^ b[i]);
	return res;
}

int fbit(const vi& a) { //fbit(0101) = 3
	rer(i, N, 0) {
		if(a[i] == 1) return i + 1;
	}
	return 0;
}

vi shift(const vi& a, int k) {
	vi res(N, 0);
	int fa = fbit(a);
	assert(fa + k <= N);
	rep(i, 0, fa) {
		res[i + k] = a[i];
	}
	return res;
}

bool is_zero(const vi& a) {
	rep(i, 0, N) {
		if(a[i]) return false;
	}
	return true;
}

vi gcd(const vi& a, const vi& b) {
	if(is_zero(b)) return a;
	vi c = a;
	while(true) {
		int fc = fbit(c), fb = fbit(b);
		if(fc < fb) break;
		int diff = fc - fb;
		c = bxor(c, shift(b, diff));
	}
	return gcd(b, c);
}

vi stobit(const string& str) {
	vector<int> res(N, 0);
	int n = sz(str);
	rep(i, 0, n) {
		res[n - i - 1] = str[i] - '0';
	}
	return res;
}

int M;
vi X;
vi B[10];

void solve() {
	string str;
	cin >> M >> str;
	pow2[0] = 1;
	rep(i, 1, 4010) pow2[i] = pow2[i - 1] * 2 % mod;
	X = stobit(str);
	rep(i, 0, M) {
		cin >> str;
		B[i] = stobit(str);
	}
	vi g = B[0];
	rep(i, 0, M - 1) g = gcd(g, B[i + 1]);
	int a = fbit(X), b = fbit(g);
	vi c(N, 0);
	ll res = 0;
	rep(i, 0, (a - b + 1)) {
		if(X[a - i - 1] == 1) {
			ADD(res, pow2[a - b - i]);
			if(c[a - i - 1] == 0) c = bxor(c, shift(g, (a - b - i)));
		}
		if(X[a - i - 1] == 0 && c[a - i - 1] == 1) {
			c = bxor(c, shift(g, (a - b - i)));
		}
	}
	rer(i, N, 0) {
		if(X[i] == 0 && c[i] == 1) {
			cout << res << "\n";
			return;
		}
		else if(X[i] == 1 && c[i] == 0) {
			cout << (res + 1) % mod << "\n";
			return;
		}
	}
	cout << (res + 1) % mod << "\n";
}

bitの問題にもっと強くなりたい。