https://codeforces.com/contest/949
ABしか解けないよぉ助けてくれ
A
最大のzebraを取っていけばいいことはわかりますが、実装にてこずりました。こういうのはsetって一番言われてる。
B
再帰的に求めていけばいいです。
C
最近有向グラフの問題といてなくていろいろこんがらがった…SCCするだけなんですが、N=2のコーナーケースに引っかかってしまった…
D
区間に値を割り振っていく問題になって、greedyでできます。O(Nlog^2 N)とかですが大丈夫です。multisetとすべきところをsetとしてしまいWA...
解説の方は人同士が交わらないことを利用してO(N)でやってるんですがこれも思いつくべきでした。
べつにABCDまではそんな難しくないですけど、やっぱりコンテスト中に解くとなるとあせりとかもあるし難しいですね。脊髄を鍛えたい。
問題文を読解するのに時間がかかってしまったのも問題ですね。
https://codeforces.com/contest/986
AB397位
A
bfsします。
B
3nと7n+1で偶奇違うのに気づくのにすごい時間かかってしまった…。
C
こういうグラフの問題は初手をミスるとなんにもできなくなりますね…。
補助グラフを使ってうまくまとめる感じです。
https://codeforces.com/problemset/problem/1012/B
これは今回の問題とは全く関係ないですが、グラフにそもそもきづけなくて解けなかったやつなのであげときます。
D
2*2*3*3*3...みたいな形をしていることがわかればあとは大小比較をすればいいです。FFTでやれば厳密にできるらしいです。
http://codeforces.com/contest/1016
このコンテストで全完できるようになったらめちゃくちゃ気持ちよさそうですね…
A
読んでないです。
B
O(NQ)でゆるーくやりましょう。
C
めんどくさい…横移動するとあとはコにしか動けません。
D
条件を連立方程式にして、行列を変形していくと、YES<=>aとbのxorが0になります。構成は1行目と1列目を適当に決めればいいです。
E
頑張って条件式を立てると、結局r-lに依存しないので線形性でまとめてO(NlogN)だと思うんですけどなんで通らないんですか。
F
trivialじゃない木が直線+len1の枝が生えてるみたいな感じです。実装絶対めんどくさい。
G
LCMの条件からvとaiはLCMの約数なんですが、たかだか2000コです。なのでO(2000*2*10^5)で通ると思います。
なんかいろいろ書いてるんですけど実際本番で2完しかしてないのやばい。
https://codeforces.com/contest/1007
A
普通にループ回しましょう。
B
包除原理で美しく書きましょう。
C
やりたくない…
D
2-SATだけど、普通にやったら間に合わないのでsegtreeっぽく構築するやつですね。HL分解すれば論理式がO(Nlog^2N)個になって多分解けます。
E
やばそう。
A
作業の合計回数は一定です。
B
勉強になりました。数が埋まってる区間がありそうだからそれをずっと探そうと思っていたけど、冷静になるとこれは十分条件から攻めているのであまり良い戦略とは言えませんね。やっぱり「ありえない」ものを除去していって、同値に変形するのがシンプルな解法につながります。
C
包除原理するのは見え見えで、ΣΣiCj3^(i*j)を計算するのが本質です。これは二項定理でΣを1つにできます。
D
簡単に木上で長さKのサイクルを数える問題に帰着できます。ここからが面白い。重心分解するとなんか高速に求められます。重心分解とpathの相性は抜群ですね…。区間が出てきたら〜分解は考えたほうが良さそうです。
E
例の追加+削除のMoでできそう。
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たくさんやれば実装強くなりそうですね。
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) };
