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