CSA Round 84

https://csacademy.com/contest/round-84/task/manhattan-center/
つら…
A Nが小さいので何しても通ります
B O(N)でやろうとしたんですがバグらせたので普通ににぶたん書いた…
C まず奇数長の棒が奇数本だとできません。そうでなければ奇数長を2本ずつ組み合わせればいいです。偶数長は真ん中で切ればいいです。
D 三分探索…?と思ったけど、冷静にsetを書いてAC。本番バグらせそう。

ll N, K;
vector<pl> P;
vector<vector<ll>> Q;
vector<ll> vx;
set<pl> pos, neg;
vector<pl> L;

int fd(ll v) {
	return lower_bound(all(vx), v) - vx.begin();
}

void solve() {
	cin >> N >> K;
	P.resize(N);
	rep(i, 0, N) {
		cin >> P[i].fst >> P[i].sec;
		vx.pb(P[i].fst);
	}
	sort(all(vx));
	vx.erase(unique(all(vx)), vx.end());
	Q.resize(sz(vx));
	rep(i, 0, N) {
		int at = fd(P[i].fst);
		Q[at].pb(i);
	}
	L.resize(N);
	ll sneg = 0, spos = 0;
	rep(i, 0, N) {
		L[i] = pl(P[i].fst + P[i].sec, i);
	}
	sort(all(L));
	rep(i, 0, K) {
		neg.insert(L[i]);
		sneg += L[i].fst;
	}
	int at = K;
	ll res = linf;
	rep(i, 0, sz(vx)) {
		ll x = vx[i];
		while(at < N && !pos.empty()) {
			if(P[L[at].sec].fst < x) at++;
			else if((*(--pos.end())).fst + x > L[at].fst - x) {
				spos -= (*(--pos.end())).fst;
				sneg += L[at].fst;
				pos.erase(--pos.end());
				neg.insert(L[at]);
				at++;
			}
			else break;
		}
		// debug(vector<pl>(all(pos)), vector<pl>(all(neg)));
		// debug(spos, sneg);
		MIN(res, (-x * sz(neg) + sneg) + (x * sz(pos) + spos));
		rep(j, 0, sz(Q[i])) {
			int v = Q[i][j]; //index;
			if(neg.count(pl(P[v].fst + P[v].sec, v))) {
				sneg -= P[v].fst + P[v].sec;
				spos += P[v].sec - P[v].fst;
				neg.erase(pl(P[v].fst + P[v].sec, v));
				pos.insert(pl(P[v].sec - P[v].fst, v));
			}
		}
	}
	cout << res << "\n";
}

E 複数の直線の最小値になって、傾き0になってから更に値が小さくなることはないのでこっちは三分探索できます。あとは全方位木DPして...と思ったんですが、再帰するの忘れて永遠にバグらせました。悲しい。バグが直ってもTLE。黄金比探索にしてもダメです。でもよくよく考えると、実は頂点0から普通にdfsするだけで答えが求まります。これは面白い(手のひら返し)。下のコードは黄金比探索です。

int N; ll D;
int S[250010], T[250010];
ll C[250010], A[250010];
vector<pi> G[250010];
ll ans = 0;


ll dfs(int v, int p, ll m) {
	ll res = 0;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i].fst;
		if(n == p) continue;
		ll u = dfs(n, v, m); //don't forget this
		u += C[G[v][i].sec] + A[G[v][i].sec] * m;
		MAX(ans, res + u);
		MAX(res, u);
	}
	return res;
}



ll val(ll m) {
	ans = 0;
	dfs(0, -1, m);
	return ans;
}

void solve() {
	cin >> N >> D;
	rep(i, 0, N - 1) {
		cin >> S[i] >> T[i] >> C[i] >> A[i];
		S[i]--;
		T[i]--;
		G[S[i]].pb(pi(T[i], i));
		G[T[i]].pb(pi(S[i], i));
	}

	ll lv = 0, rv = D + 1;
	double phi = (1.0 + sqrt(5)) / 2.0;
	while(rv - lv > 2) {
		ll m1 = (lv * phi + rv) / (1 + phi);
		ll m2 = (lv + rv * phi) / (1 + phi);
		if(val(m1) <= val(m2)) {
			rv = m2;
		}
		else lv = m1;
	}
	pl ans = pl(linf, -1);
	rep(i, 0, 2) {
		if(lv + i <= D) MIN(ans, pl(val(lv + i), lv + i));
	}
	cout << ans.sec << "\n";
	cout << ans.fst << "\n";
}

F MSTさえできれば解けそうですが、構築が難しそう…JOI水筒っぽくて懐かしいですね。

CSAたくさんやれば実装強くなりそうですね。

精進7/15

https://beta.atcoder.jp/contests/agc026/tasks/agc026_b BとDの最大公約数が肝になることがわかればほとんど解けたようなもんですが、他の自明な条件も忘れないように。
https://beta.atcoder.jp/contests/agc026/tasks/agc026_c 文字列の前N字について割り当てを決めてしまえば後はDP。
https://codeforces.com/contest/1007/problem/B 雑にやると辛いやつですね。包除しましょう。
https://codeforces.com/contest/1009/problem/F 普通にマージテクするだけと思ったけど制約が厳しすぎる…
https://codeforces.com/contest/1004/problem/B え?ってなるけど…上界をよく考えましょう。
https://codeforces.com/contest/1004/problem/D 端の値で大体決まります。
https://codeforces.com/contest/1004/problem/E 木の葉の方からいらないやつを削除していきます。K=1がコーナーケース。
https://codeforces.com/contest/1004/problem/F えーセグ木すごいですね。一見できなさそうなんですが…結合性さえあればセグ木にできるんだなぁ。実装はテンプレートがあるのでそれを使いましょう。

int N, M, X;

struct T {
	ll v; vector<pi> dpl, dpr;
	T(ll x = 0) {
		v = (x >= X);
		dpl.clear(); dpr.clear();
		dpl.pb(pi(0, x));
		dpr.pb(pi(0, x));
	}
	friend ostream& operator<<(ostream& out, const T& t) {
		out << t.v << t.dpl << t.dpr; return out;
	}
};

T operator+(const T& tl, const T& tr) {
	if(sz(tl.dpl) == 1) return tr;
	if(sz(tr.dpr) == 1) return tl;
	T res;
	res.v = tl.v + tr.v;
	int at = sz(tl.dpr) - 2;
	rep(i, 0, sz(tr.dpl) - 1) {
		while(at > 0 && (tl.dpr[at - 1].sec | tr.dpl[i].sec) >= X) {
			at--;
		}
		if((tl.dpr[at].sec | tr.dpl[i].sec) >= X) {
			res.v += (tl.dpr.back().fst - tl.dpr[at].fst) *
				(tr.dpl[i + 1].fst - tr.dpl[i].fst);
		}
	}

	res.dpl = tl.dpl;
	res.dpl.erase(--res.dpl.end());
	int tb = tl.dpl.back().sec;
	int len = tl.dpl.back().fst;
	rep(i, 0, sz(tr.dpl) - 1) {
		if(tb != (tb | tr.dpl[i].sec)) {
			tb |= tr.dpl[i].sec;
			res.dpl.pb(pi(tr.dpl[i].fst + len, tb));
		}
	}
	res.dpl.pb(pi(tr.dpl.back().fst + len, tb));

	res.dpr = tr.dpr;
	res.dpr.erase(--res.dpr.end());
	tb = tr.dpr.back().sec;
	len = tr.dpr.back().fst;

	rep(i, 0, sz(tl.dpr) - 1) {
		if(tb != (tb | tl.dpr[i].sec)) {
			tb |= tl.dpr[i].sec;
			res.dpr.pb(pi(tl.dpr[i].fst + len, tb));
		}
	}
	res.dpr.pb(pi(tl.dpr.back().fst + len, tb));
	return res;
}

struct segtree{
	int n; vector<T> seg;
	void init(int mx) {
		n = 1;
		while(n < mx) n *= 2;
		seg = vector<T>(n * 2);
	}
	segtree(int mx = 0) {
		init(mx);
	}
	void update(int i, T x) {
		i += n - 1;
		seg[i] = x;
		while(i > 0) {
			i = (i - 1) / 2;
			seg[i] = seg[i * 2 + 1] + seg[i * 2 + 2];
		}
	}
	T ga(int a, int b, int k, int l, int r) {
		if(b <= l || r <= a) return T();
		if(a <= l && r <= b) return seg[k];
		else {
			T lv = ga(a, b, k * 2 + 1, l, (l + r) / 2);
			T rv = ga(a, b, k * 2 + 2, (l + r) / 2, r);
			return lv + rv;
		}
	}
	void show() {
		vector<T> tmp;
		rep(i, 0, n) tmp.push_back(get(i, i + 1));
		debug(tmp);
	}
	//edit from here
	T get(int a, int b) { return ga(a, b, 0, 0, n); } //[a, b)
};

精進7/2

https://beta.atcoder.jp/contests/arc100/tasks/arc100_a目AC。中間値でもいいし、普通に全通り試すのもよし。
https://beta.atcoder.jp/contests/arc100/tasks/arc100_b目AC。にぶたんしなくても、しゃくとりしながらdpすれば解けます。K区間ならO(NK)ですね。
https://beta.atcoder.jp/contests/arc100/tasks/arc100_c高速ベータ変換あまり使う機会ないのでこういう問題はうれしい。基本は要素0から順番にdpしていく感じです。

精進6/23-30

https://agc022.contest.atcoder.jp/tasks/agc022_c面白い。場合分け系と思ったけど違った。前処理した後、大きいkから使う必要があるか見ていく。
https://agc006.contest.atcoder.jp/tasks/agc006_dやっぱり難しく考え過ぎだよなぁ…1が使えない→2で置き換えて良いとして考えていくと思ったがにぶたんでもっと簡単に解ける。
https://agc006.contest.atcoder.jp/tasks/agc006_e必要十分条件かなぁと思ったらそうだった。置換と反転が重要です。
https://agc023.contest.atcoder.jp/tasks/agc023_dこれは超良問。端をよく考えると再帰的に解ける。
https://arc068.contest.atcoder.jp/tasks/arc068_d端からとった数で場合分けをしてO(N^3)のdpを改善すればいい。
方針として再帰or必要十分条件を突き通せばどんな問題でも解ける気がしてきた。

精進6/21

久しぶりです

https://beta.atcoder.jp/contests/arc098/tasks/arc098_bえー思いつきませんでした。bitがかぶらないことが必要十分。
https://beta.atcoder.jp/contests/arc098/tasks/arc098_c最小値固定すれば、長さk以上の区間から数を取っていく問題になります。
https://beta.atcoder.jp/contests/agc024/tasks/agc024_b連続している数の最長部分列を見つければ良いことになります。
https://beta.atcoder.jp/contests/agc008/tasks/agc008_c丁寧にやればいいです。
https://beta.atcoder.jp/contests/agc022/tasks/agc022_b30000に対して20000というのがヒントです。2と3の倍数で構成します。
https://beta.atcoder.jp/contests/agc024/tasks/agc024_c数列をうしろから見ればわかりやすいです。
https://beta.atcoder.jp/contests/agc025/tasks/agc025_bnCa*nCbの言い換えが本質です。少しむずかしい。
https://agc025.contest.atcoder.jp/tasks/agc025_c
わかりましたがめっちゃこんがらがりました。普通に難しくないか?
まず問題を緩和するという発想がなかったです。N個の区間を使うのではなく、N個以下の区間を使うとします。
そうすればLi,Li+1,Ri,Ri+1に満たすべき不等式がありますが、基本的にはΣLi-ΣRiを最大化する問題になります。そうすれば貪欲に取っていけば良く、同時に不等式の条件も満たします。

codeFlyer (bitFlyer Programming Contest)

こういうセット辛すぎないか?

AB
はい
C
ちょっと詰まるよね。とりあえずjを固定して雑に数えて引くんだけど、引く時はしゃくとりが使えます。
D
累積和やるだけ。全然綺麗な方法思いつかなかった…。imos法もバグらせまくった…

ll H, W;
int N, M;
int B[2010][2010];
int D[2010][2010];
int XA[2010];
int YA[2010];

void solve() {
	cin >> H >> W;
	cin >> N >> M;
	rep(i, 0, N) {
		string str; cin >> str;
		rep(j, 0, M) {
			if(str[j] == '#') B[i][j] = 1;
		}
	}
	bool found = false;
	rep(x, 0, N) {
		rep(y, 0, M) {
			if(B[x][y]) {
				found = true;
				ll x2 = x + min(H - N, (ll)N), y2 = y + min(W - M, (ll)M);
				if(H - N + 1 > N + 1) { //xhamidasu
					XA[y + 1]++; XA[y2 + 2]--;
				}
				if(W - M + 1 > M + 1) { //yhamidasu
					YA[x + 1]++; YA[x2 + 2]--;
				}
				D[x + 1][y + 1]++; D[x2 + 2][y2 + 2]++;
				D[x + 1][y2 + 2]--; D[x2 + 2][y + 1]--;
			}
		}
	}

	if(!found) {
		cout << 0 << "\n"; return;
	}
	else {
		ll res = 0;
		rep(x, 0, 2 * N) {
			rep(y, 0, 2 * M) {
				D[x + 1][y + 1] += D[x + 1][y] + D[x][y + 1] - D[x][y];
				res += (D[x + 1][y + 1] > 0);
			}
		}
		rep(y, 0, 2 * M) {
			XA[y + 1] += XA[y];
			res += (XA[y + 1] > 0) * max(H - 2 * N, 0ll);
		}
		rep(x, 0, 2 * N) {
			YA[x + 1] += YA[x];
			res += (YA[x + 1] > 0) * max(W - 2 * M, 0ll);
		}
		res += 1ll * max(W - 2 * M, 0ll) * max(H - 2 * N, 0ll);
		cout << res << "\n";
	}
}

E
multisetやるだけ。これもめんどくさい…

ll Y, W, D;
int N, M;
ll A[110];
map<ll, int> S;
vl vec[MAX_N];
ll res;

ll bet(ll nd, ll d) {
	if(1 <= d - nd - 1 && d - nd - 1 <= D) {
		return d - nd - 1;
	}
	else return 0;
}

void del(ll d, ll e) { // S is bigger than 1
	S[d]--;
	if(S[d] == 0) {
		auto at = S.lower_bound(d);
		if(at == (--S.end())) {
			auto p = at; p--;
			res -= bet(p->fst, at->fst);
		}
		else if(at == S.begin()) {
			auto p = at; p++;
			res -= bet(at->fst, p->fst);
		}
		else {
			auto pp = at, np = at; pp--; np++;
			if(bet(pp->fst, np->fst) == 0) {
				res -= bet(pp->fst, at->fst);
				res -= bet(at->fst, np->fst);
			}
			else res++;
		}
		S.erase(d); res--;
	}
	d += e;
	S[d]++;
	if(S[d] == 1) {
		auto at = S.lower_bound(d);
		if(at == (--S.end())) {
			auto p = at; p--;
			res += bet(p->fst, at->fst);
		}
		else if(at == S.begin()) {
			auto p = at; p++;
			res += bet(at->fst, p->fst);
		}
		else {
			auto pp = at, np = at; pp--; np++;
			if(bet(pp->fst, np->fst) == 0) {
				res += bet(pp->fst, at->fst);
				res += bet(at->fst, np->fst);
			}
			else res--;
		}
		res++;
	}
}

void solve() {
	cin >> Y >> W;
	cin >> N >> M >> D;
	rep(i, 0, N) {
		cin >> A[i]; A[i]--;
		S[A[i]]++;
	}
	rep(i, 0, M) {
		ll a, b;
		cin >> a >> b; a--; b--;
		S[a * W + b]++;
		vec[b].pb(a * W + b);
	}
	if(N + M <= 1) {
		rep(i, 0, W) cout << N + M << "\n";
		return;
	}
	res = sz(S);
	ll prev = -linf;
	for(pl a : S) {
		res += bet(prev, a.fst);
		prev = a.fst;
	}
	rep(i, 0, W) {
		cout << res << "\n";
		rep(j, 0, N) {
			del(A[j]++, 1);
		}
		rep(j, 0, sz(vec[i])) {
			del(vec[i][j], W);
		}
	}
}

こういうコンテストで勝てるようになったらすごい強くなれそうだけどなぁ。

Codeforces Round #483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov!]

http://codeforces.com/contest/983

A
えーABCの中で一番手間取った。QとBの最大公約数gをとってQをgで割ることを繰り返す。こういうの苦手。
B
dpしてまたdp
C
dp[i][j][k][l][m][n]:=i番目の人までみて、場所jにいる。エレベーターに乗っている人はk,l,m,nである時の最小コストとやると、2*10^8となって辛いです。しかし、i番目の人が乗った場合行き先がbiの人が必ずいるので、それを利用するとnを10試す必要がなくなって2で大丈夫になります。これで2*10^7*2で通ります。2*10^8/(4!)が通ってしまうのは少し解せない…。コードがだいぶエグい。

int N;
int A[MAX_N], B[MAX_N];
int dp[2010][9][10][10][10][2]; //i,at j,floor at; k, l, m floor to visit, B[i], visited?

void solve() {
	cin >> N;
	rep(i, 0, N) {
		cin >> A[i] >> B[i];
		A[i]--; B[i]--;
	}
	rep(i, 0, N + 1) {
		rep(j, 0, 9) {
			rep(k, 0, 10) {
				rep(l, 0, 10) {
					rep(m, 0, 10) {
						rep(n, 0, 2) {
							dp[i][j][k][l][m][n] = inf;
						}
					}
				}
			}
		}
	}
	dp[0][A[0]][9][9][9][0] = A[0];
	//i, j, k, l, m, n
	rep(i, 0, N) {
		rep(k, 0, 10) {
			rep(l, 0, 10) {
				rep(m, 0, 10) {
					rep(n, 0, 2) {
						rep(j, 0, 9) {
							if(dp[i][j][k][l][m][n] == inf) continue;
								// debug(i, j, k, l, m, n);
							if(k == 9) { //visited
								MIN(dp[i + 1][A[i + 1]][B[i]][l][m][0], dp[i][j][k][l][m][n] + abs(A[i + 1] - j));
							}
							else {
								MIN(dp[i][k][9][l][m][n], dp[i][j][k][l][m][n] + abs(k - j));
							}

							if(l == 9) {
								MIN(dp[i + 1][A[i + 1]][k][B[i]][m][0], dp[i][j][k][l][m][n] + abs(A[i + 1] - j));
							}
							else {
								MIN(dp[i][l][k][9][m][n], dp[i][j][k][l][m][n] + abs(l - j));
							}

							if(m == 9) {
								MIN(dp[i + 1][A[i + 1]][k][l][B[i]][0], dp[i][j][k][l][m][n] + abs(A[i + 1] - j));
							}
							else {
								MIN(dp[i][m][k][l][9][n], dp[i][j][k][l][m][n] + abs(m - j));
							}

							if(n == 1) { //visited
								MIN(dp[i + 1][A[i + 1]][k][l][m][0], dp[i][j][k][l][m][n] + abs(A[i + 1] - j));
							}
							else {
								MIN(dp[i][B[i]][k][l][m][1], dp[i][j][k][l][m][n] + abs(B[i] - j));
							}
						}
					}
				}
			}
		}
	}
	int res = inf;
	rep(i, 0, 9) {
		MIN(res, dp[N - 1][i][9][9][9][1]);
	}
	cout << res + 2 * N << "\n";
}