AGC001D: Arrays and Palindrome

https://agc001.contest.atcoder.jp/tasks/agc001_d

これ知識的には誰でも解けるけど結構思考しないといけなくて面白い。

同じにならないといけない文字同士を結ぶグラフを考えると、直線+ループになる。これは各点の次数が2以下であることから示せる。
なので奇数が2つ以上あると、グラフが連結にならず、Impossibleになる。
今奇数が2以下だとする。
全部の点を1本の直線で結びたいのだが、奇数を端に置いて、最初の文字数を1増やして最後の文字数を1減らすとうまくいく。

あとはM=1の時や、最後の文字数が1の時を注意して実装すればいいです。

N=1コーナーケースだと思いましたが、そんなことはなかった…

int N, M;
vi odd, even;

void solve() {
	cin >> N >> M;
	rep(i, 0, M) {
		int a; cin >> a;
		if(a % 2) odd.pb(a);
		else even.pb(a);
	}
	if(sz(odd) <= 2) {
		vector<int> ans;
		vector<int> ord;
		if(sz(odd) == 0) {
			ans.pb(1);
			rep(i, 0, sz(even)) {
				ord.pb(even[i]);
				ans.pb(even[i]);
			}
			ans[M]--;
		}
		else if(sz(odd) == 1) {
			ans.pb(1);
			rep(i, 0, sz(even)) {
				ord.pb(even[i]);
				ans.pb(even[i]);
			}
			ord.pb(odd[0]);
			if(odd[0] != 1) ans.pb(odd[0] - 1);
		}
		else {
			ans.pb(odd[0] + 1);
			ord.pb(odd[0]);
			rep(i, 0, sz(even)) {
				ord.pb(even[i]);
				ans.pb(even[i]);
			}
			ord.pb(odd[1]);
			if(odd[1] != 1) ans.pb(odd[1] - 1);
		}
		rep(i, 0, sz(ord)) {
			cout << ord[i] << " ";
		}
		cout << "\n";
		cout << sz(ans) << "\n";
		rep(i, 0, sz(ans)) {
			cout << ans[i] << " ";
		}
		cout << "\n";
	}
	else {
		cout << "Impossible\n";
	}
}

ARC064F: Rotated Palindromes

https://arc064.contest.atcoder.jp/tasks/arc064_d

f(l)=周期がちょうどlの条件を満たす数列の数とすると、

f(l)=K^[(l+1)/2]-Σf(l/p)となって、求める値はΣ(lは奇数)f(l)*l+Σ(lは偶数)f(l)*(l/2)です。

f(l)の式は高速メビウス変換の式に良く似ています。

http://omochan.hatenablog.com/entry/2017/09/26/235331

ただ集合が0と1以外の値も取るので注意しましょう。
dp[k+1][a0a1....ak....am]=dp[k][a0a1....ak....am]-dp[k][a0a1....(ak-1)....am]のように遷移すれば良いです。

かなり高速でN<10^18でも通りそうです。多倍長必要ですが。

でもN=10^9程度だったら(lとしてありうるものの個数)<=2000らしいので、わざわざdpにして高速化しなくても2000*2000で通ります。

ll N, K, M;
ll ans;
map<int, int> P;
vector<pi> vp;

map<vi, ll> dp[11];

ll diviser(const vi& vec) {
	ll n = 1;
	rep(i, 0, M) {
		n *= mod_pow(vp[i].fst, vec[i]);
	}
	return n;
}

ll loop(vi vec, int at) {
	if(dp[at].find(vec) != dp[at].end()) return dp[at][vec];
	if(at == 0) {
		ll l = diviser(vec);
		return dp[at][vec] = mod_pow(K, (l + 1) / 2);
	}
	else {
		int p = vec[at - 1];
		ll res = 0;
		if(p - 1 >= 0) {
			vec[at - 1] = p - 1;
			ADD(res, mod - loop(vec, at - 1));
		}

		vec[at - 1] = p;
		ADD(res, loop(vec, at - 1));
		return dp[at][vec] = res;
	}
}

void loop2(vi vec, int at) {
	if(at == M) {
		ll l = diviser(vec);
		if(l % 2 == 0) ADD(ans, (l / 2) * loop(vec, M) % mod);
		else ADD(ans, l * loop(vec, M) % mod);
		return;
	}
	vec.resize(at + 1);
	rep(i, 0, vp[at].sec + 1) {
		vec[at] = i;
		loop2(vec, at + 1);
	}
}

void solve() {
	cin >> N >> K;
	ans = 0;
	ll n = N;
	for(int i = 2; i * i <= n; i++) {
		while(n % i == 0) {
			n /= i;
			P[i]++;
		}
	}
	if(n != 1) P[n]++;

	vp = vector<pi>(all(P));
	M = sz(vp);


	loop2({}, 0);

	cout << ans << "\n";
}

まず場合の数パートが難しい。もっとサラッと考えられないかなぁ。

COLOCON -Colopl programming contest 2018- Final

https://colopl2018-final-open.contest.atcoder.jp/

A
オンサイトだとこれでも詰まるよねぇ…端が繋がる時注意。

B
スタックでO(N)。再帰やってTLEするの普段絶対やらないと思うし、怖いね。

C
一次式にしてもよくわからなかったので分割統治でやった。これ解けたの嬉しい。
一次式はConvex Hull Trickらしいです。

D
加法定理使ってたら結局pairでsortする問題になった。

int N, M;
pi P[MAX_N], Q[MAX_N];
BIT bit;

void solve() {
	cin >> N;

	rep(i, 0, N) {
		int a, b;
		cin >> a >> b;
		if(a > b) swap(a, b);
		P[i].fst = a; P[i].sec = b;
	}

	sort(P, P + N);
	
	M = N * 2;
	bit.init(N + 10);
	rep(i, 0, N) {
		Q[i * 2] = pi(P[i].fst, i);
		Q[i * 2 + 1] = pi(P[i].sec, i);
	}
	sort(Q, Q + M);
	
	ll res = 0;
	rep(i, 0, M) {
		// int v = Q[i].fst;
		int at = Q[i].sec;
		res += bit.get(at + 1, N);
		bit.update(at, at + 1, 1);
	}
	MUL(res, mod_pow(2, N - 2));
	cout << res << "\n";
}

E
グラフにします。フローっぽいです。わけわかんないので終了です。でも筋は悪くないみたい。

F
エスパーっぽい。

経験不足だなぁ。

懇親会
これ話せる人いないやつだと思ったらei1333さん、satanicさんと話せた。楽しかった。
よすぽさん面白かった。

AGC020

https://beta.atcoder.jp/contests/agc020

A
A-Bの偶奇です

B
条件を満たすものは区間で表せるので端の値を持てばいいです。

C
和をSとしてS/2以上で一番小さいものを選べばいいです。証明はSの部分列をA、B=S/Aとするとsum(A)<=S/2,sum(B)>=S/2となることからです。
bitのdpでできて、64倍高速化できます。
64倍高速化ってこうやるのか…

int N;
int A[MAX_N];
bitset<2000 * 2000 + 10> dp[2]; 

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	dp[0][0] = 1;
	int s = 0;
	int now = 0, nex = 1;
	rep(i, 0, N) {
		dp[nex] = dp[now] << A[i];
		dp[nex] |= dp[now];
		swap(now, nex);
		s += A[i];
	}
	s = (s + 1) / 2;
	for(int i = s; ; i++) {
		if(dp[now][i]) {
			cout << i << "\n";
			return;
		}
	}
}

E
sの圧縮の仕方をg(s)、そのうち(s')*nで表せる方法をf(s)としてmap, bool>でdpします。
sとしてありうるものは少なそうだなぁと思ってそのままコードにしたら通ってしまいました…

でもよくよく考えてみると、f(s)の遷移先g(s')は|s|/2>=|s'|を満たすからですね。

map<vi, ll> G;
map<vi, ll> F;

ll loopf(vector<int> vec);

ll loopg(vector<int> vec) {
	int n = sz(vec);
	if(G.find(vec) != G.end()) return G[vec];

	vector<vl> f(n + 1, vl(n + 1, 0));
	rep(i, 0, n) {
		rep(j, i + 1, n + 1) {
			if(i == 0 && j == n) continue;
			f[i][j] = loopf(vi(vec.begin() + i, vec.begin() + j));
		}
	}
	vl dp(n + 1, 0);
	dp[0] = 1;
	rep(i, 1, n + 1) {
		rep(j, 0, i) ADD(dp[i], dp[j] * f[j][i] % mod);
	}
	return G[vec] = (dp[n] + loopf(vec)) % mod;
}

ll loopf(vector<int> vec) {
	int n = sz(vec);
	if(n == 1) {
		if(vec[0] == 0) return 1;
		else return 2;
	}
	if(F.find(vec) != F.end()) return F[vec];

	ll ans = 0;
	rep(i, 1, n) {
		if(n % i) continue;
		vi res(i, 1);
		rep(j, 0, n) {
			res[j % i] &= vec[j];
		}
		ADD(ans, loopg(res));
	}
	return F[vec] = ans;
}

void solve() {
	string str;
	cin >> str;
	int n = sz(str);
	vector<int> vec(n);
	rep(i, 0, n) vec[i] = str[i] - '0';
	cout << loopg(vec) << "\n";
}

行く年来る年

2017年

重要なアルゴリズムはだいたい抑えられた。(特にflow)

問題の解き方が少しわかってきた。(前まではひらめくまで途方に暮れていた)

年末はコンテスト結構出れた。AtCoderのみだけど。

2018年目標

AtCoder Rate2600

CodeForces Rate2200

AtCoder精進(AGC,ARC)

できたら作問

赤一歩手前くらいまで到達できるとなぁ。

Codeforces Round #455 (Div. 2)

http://codeforces.com/contest/909/problem/E

全体的に問題文の把握に手間がかかっていますね…

A
はい。
B
親の顔より見た問題。一番重なっているところを累積和で求めます。
C
勘違いした…
D
削除は奈良市計算量チャンスです。
E
問題を理解するのに無限に時間を費やした。
トポロジカルソートして一番1の連続した区間が多いpathを求めます。
トポロジカルソートの実装を忘れたので戒めとしてコード貼ります。dfsしてreverseですよ。

int N, M;
int A[MAX_N];
int dp[MAX_N];
bool used[MAX_N];
vi ord;
vi G[MAX_N];

void dfs(int v) {
	used[v] = true;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(!used[n]) dfs(n);
	}
	ord.pb(v);
}

void solve() {
	cin >> N >> M;
	rep(i, 0, N) {
		cin >> A[i];
		if(A[i] == 1) dp[i] = 1;
	}
	rep(i, 0, M) {
		int a, b;
		cin >> a >> b;
		G[b].pb(a);
	}
	rep(i, 0, N) {
		if(!used[i]) dfs(i);
	}
	reverse(all(ord));
	rep(i, 0, N) {
		int v = ord[i];
		if(A[v] == 0) {
			rep(j, 0, sz(G[v])) {
				int n = G[v][j];
				if(A[n] == 1) MAX(dp[n], dp[v] + 1);
				else MAX(dp[n], dp[v]);
			}
		}
		else {
			rep(j, 0, sz(G[v])) {
				int n = G[v][j];
				MAX(dp[n], dp[v]);
			}
		}
	}
	int ans = 0;
	rep(i, 0, N) MAX(ans, dp[i]);
	cout << ans << "\n";
}

F
2番目は普通にできて、1番目は偶数の場合はできて、奇数の場合はできないことを証明しようとしてたんですができませんでした…。
さらに解説で4行くらいで済まされて悲しかった。ディレクリで終了です。

1番目は(2^n,2^n-1),(2^n+1,2^n-2)...みたいに並べて再帰的にやります。
2番目は(N<=5||N=2^k)の時できなくて、N=6,N=7は埋め込みます。
N>=8は奇数偶数で場合分けして、N=6とN=7の結果を利用します。

int N;
int ans[MAX_N];

void loop_sub1(int n) {
	if(n == 0) return;
	int pow2 = 1;
	while(pow2 * 2 <= n) pow2 *= 2;
	rep(i, 0, n - pow2 + 1) {
		int a = pow2 + i, b = pow2 - i - 1;
		ans[a] = b;
		ans[b] = a;
	}
	loop_sub1(pow2 * 2 - n - 2);
}

void ans_show() {
	cout << "YES\n";
	rep(i, 1, N) {
		cout << ans[i] << " ";
	}
	cout << ans[N] << "\n";
}

void sub1() {
	if(N % 2 == 1) cout << "NO\n";
	else {
		loop_sub1(N);
		ans_show();
	}
}

void sub2_6() {
	ans[1] = 3; ans[3] = 1;
	ans[2] = 6; ans[6] = 2;
	ans[4] = 5; ans[5] = 4;
}

void sub2_7() {
	ans[1] = 3; ans[3] = 7; ans[7] = 1;
	ans[2] = 6; ans[6] = 2;
	ans[4] = 5; ans[5] = 4;
}

void sub2() {
	if(N <= 5) {
		cout << "NO\n";
	}
	else if(N == 6) {
		sub2_6();
		ans_show();
	}
	else if(N == 7) {
		sub2_7();
		ans_show();
	}
	else {
		int pow2 = 8;
		while(pow2 * 2 <= N) pow2 *= 2;
		if(N - pow2 == 0) cout << "NO\n";
		else if((N - pow2) % 2 == 1) {
			sub2_7();
			for(int i = 8; i < N; i += 2) {
				ans[i] = i + 1; ans[i + 1] = i;
			}
			ans_show();
		}
		else {
			sub2_6();
			for(int i = 8; i <= pow2; i += 2) {
				ans[i] = i + 1; ans[i + 1] = i;
			}
			ans[7] = pow2 + 1; ans[pow2 + 1] = 7;
			ans[pow2] = pow2 + 2; ans[pow2 + 2] = pow2;
			for(int i = pow2 + 3; i < N; i += 2) {
				ans[i] = i + 1; ans[i + 1] = i;
			}
			ans_show();
		}
	}
}

void solve() {
	cin >> N;
	sub1();
	sub2();
}

全部解けそうだったね。

ARC068

https://beta.atcoder.jp/contests/arc068

C
はい。

D
結局2枚捨てるという操作なので。

E
解法2つあります。

dの倍数のdを小さくすると、r - l <= dを満たす区間、つまりl<=x < r の間にdの倍数が1つ以上ある区間の数は増えていきます。
これを利用する方法が1つです。

もうひとつは区間(l,r)を二次元plotすると、長方形領域にある点の数を数える問題になるので平面走査する方法です。
下のコードは2つ目の方法ですが、範囲を±1でミスりまくって結構辛かった。

区間の長さを短くするというのも本質的な考察になるんですね。二次元plotの方は思いついてもよかったなぁ。

int N, M;
vi point[MAX_N];
vector<pi> interval[MAX_N];
int ans[MAX_N];
BIT bit;

void solve() {
	cin >> N >> M;
	bit.init(M + 2);
	rep(i, 0, N) {
		int l, r; cin >> l >> r; r++;
		point[l].pb(r);
	}
	rep(i, 1, M + 1) {
		for(int j = -i; j + i <= M; j += i) {
			int l = j, r = j + i;
			if(l >= 0) interval[l + 1].pb(pi(r + 1, -i));
			interval[r + 1].pb(pi(r + 1, i));
		}
	}
	rep(i, 0, M + 2) {
		rep(j, 0, sz(interval[i])) {
			pi p = interval[i][j];
			int v = abs(p.sec);
			if(p.sec < 0) {
				ans[v] -= bit.get(p.fst, M + 2);
			}
			else ans[v] += bit.get(p.fst, M + 2);
		}
		rep(j, 0, sz(point[i])) {
			int p = point[i][j];
			bit.update(p, p + 1, 1);
		}
	}
	rep(i, 1, M + 1) {
		cout << ans[i] << "\n";
	}
}