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さんと話せた。楽しかった。
よすぽさん面白かった。