Codeforces Round #497 (Div. 1)

https://codeforces.com/contest/1007

A
普通にループ回しましょう。
B
包除原理で美しく書きましょう。
C
やりたくない…
D
2-SATだけど、普通にやったら間に合わないのでsegtreeっぽく構築するやつですね。HL分解すれば論理式がO(Nlog^2N)個になって多分解けます。
E
やばそう。

Codeforces Round #493 (Div. 1)

A
作業の合計回数は一定です。
B
勉強になりました。数が埋まってる区間がありそうだからそれをずっと探そうと思っていたけど、冷静になるとこれは十分条件から攻めているのであまり良い戦略とは言えませんね。やっぱり「ありえない」ものを除去していって、同値に変形するのがシンプルな解法につながります。
C
包除原理するのは見え見えで、ΣΣiCj3^(i*j)を計算するのが本質です。これは二項定理でΣを1つにできます。
D
簡単に木上で長さKのサイクルを数える問題に帰着できます。ここからが面白い。重心分解するとなんか高速に求められます。重心分解とpathの相性は抜群ですね…。区間が出てきたら〜分解は考えたほうが良さそうです。
E
例の追加+削除のMoでできそう。

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 グラフさえできればあとはkruskalをやれば答えが求まります。45度回転して、ある点vを中心に平面を8分割(y=0,x=0,y=x,y=-x)すると、分割された各領域について、一番vに近い点以外は、vと結ぶ必要がないことが証明できるので、斜めに平面走査してそのような点を求めればいいです。TLEがきつくていろいろ不毛な高速化をしてAC。

int N, E = 0;
struct edge { int u, v, cost; };

bool comp(const edge& e1, const edge& e2) {
	return e1.cost < e2.cost;
}

//int N, E; add this////////////////////////////
edge es[2000010];

ll kruskal() {
	sort(es, es + E, comp);
	UF uf(N);//init union_find
	ll res = 0;
	for(int i = 0; i < E; i++) {
		edge e = es[i];
		if(!uf.same(e.u, e.v)) {
			res += 1LL * e.cost * uf.sd(e.u) * uf.sd(e.v);
			uf.unite(e.u, e.v);
		}
	}
	return res;
}

int X[MAX_N], Y[MAX_N];

int fd(const vi& vec, int v) {
	return lower_bound(all(vec), v) - vec.begin();
}

vector<int> Q[MAX_N];

void pre() {
	vector<int> qx;
	vector<int> vx;
	vector<int> vy;
	segtree sx, sy;
	rep(i, 0, N) {
		qx.pb(X[i] + Y[i]);
		vx.pb(X[i]); vy.pb(Y[i]);
		Q[i].clear();
	}
	sort(all(qx));
	qx.erase(unique(all(qx)), qx.end());
	sort(all(vx));
	vx.erase(unique(all(vx)), vx.end());
	sort(all(vy));
	vy.erase(unique(all(vy)), vy.end());
	sx.init(sz(vy));
	sy.init(sz(vx));
	rep(i, 0, N) {
		int at = fd(qx, X[i] + Y[i]);
		Q[at].pb(i);
	}
	rep(i, 0, sz(qx)) {
		rep(j, 0, sz(Q[i])) {
			int x = X[Q[i][j]], y = Y[Q[i][j]], id = Q[i][j];
			int xat = fd(vx, x), yat = fd(vy, y);
			sx.update(0, yat, T(pi(xat, id)));
			sy.update(0, xat, T(pi(yat, id)));
		}
		rep(j, 0, sz(Q[i])) {
			int x = X[Q[i][j]], y = Y[Q[i][j]], id = Q[i][j];
			int xat = fd(vx, x), yat = fd(vy, y);
			pi px = sx.get(yat, sz(vy)).v;
			pi py = sy.get(xat, sz(vx)).v;
			if(px.sec != -1) add_edge(id, px.sec, (X[id] - X[px.sec]) / 2);
			if(py.sec != -1) add_edge(id, py.sec, (Y[id] - Y[py.sec]) / 2);
			sx.update(0, yat + 1, T(pi(xat, id)));
			sy.update(0, xat + 1, T(pi(yat, id)));
		}
	}
}

void solve() {
	cin >> N;
	rep(i, 0, N) {
		int x, y;
		cin >> x >> y;
		X[i] = x - y;
		Y[i] = x + y;
	}
	rep(q, 0, 4) {
		pre();
		rep(i, 0, N) {
			int x = X[i], y = Y[i];
			X[i] = -y;
			Y[i] = x;
		}
	}
	cout << kruskal() << "\n";
}

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を最大化する問題になります。そうすれば貪欲に取っていけば良く、同時に不等式の条件も満たします。