https://beta.atcoder.jp/contests/arc060/tasks/arc060_d 最小項数は1or2orNで、1とNの時は簡単。2はKMP法でできる。
[https://beta.atcoder.jp/contests/agc013/tasks/agc013_d DPにするのが難しいタイプの問題はホント苦手。でもこれはとりあえずdp[i][at]:=iまで進めた時赤がat個だけある場合の数をとりあえず求めてから背反にする方法を考えると解ける。
https://beta.atcoder.jp/contests/agc005/tasks/agc005_d こっちはDPにするまでが難しいタイプなので解けます…。マッチングの数え上げに帰着できるんですが、よく見ると直線グラフになっているので前処理コンビネーションして解けます。
https://yahoo-procon2017-final-open.contest.atcoder.jp/tasks/yahoo_procon2017_final_a おまけ。各文字ごとにyahooを挿入することを考えてDP
ARC085E: MUL
https://arc085.contest.atcoder.jp/tasks/arc085_c
maximum closure problemという問題なんですが、集合を2つに分ける+DPでできない場合は疑ったほうがいいです。
さて今回最大化したいのは、
S-min(Σbi+Σci)です。ここでbiは破壊する宝石のうち値が正のものであり、ciは破壊しない宝石のうち値が負のものについて絶対値をとったものです。
Sをsupersource,Tをsupersinkとして、S側にグラフcutが含まれるとき宝石を破壊し、T側に含まれていたら宝石を破壊しないことにします。
そうすると、宝石n*iはiの倍数なので、n*iが破壊されないのにiが破壊されるということはありません。なのでi->n*iにコスト無限の辺を張ります。
あと、i->Tにコストbiの辺を張ることで、もしbiが破壊されるグループに入ってる場合、その分損をしていることを表現します。
同じようにS->iにコストciの辺を張れば完成です。あとはSからTにフローを求めればmin(Σbi+Σci)が求められます。
int N; int A[MAX_N]; void solve() { cin >> N; ll S = 0; rep(i, 1, N + 1) { cin >> A[i]; if(A[i] >= 0) S += A[i]; } int s = N + 1, t = N + 2; MF::init(N + 3); rep(i, 1, N + 1) { for(int j = i * 2; j <= N; j += i) { MF::add_edge(i, j, linf); } } rep(i, 1, N + 1) { if(A[i] >= 0) { MF::add_edge(i, t, A[i]); } else MF::add_edge(s, i, -A[i]); } cout << S - MF::get(s, t) << "\n"; }
3/28精進
https://beta.atcoder.jp/contests/agc004/tasks/agc004_c 赤と青を交互に並べる。
https://beta.atcoder.jp/contests/agc012/tasks/agc012_b うーんこういうのダメだよなぁ。dp的に考えるのが苦手。bellman-fordっぽくやる。
https://beta.atcoder.jp/contests/agc013/tasks/agc013_c 場所はわかるので、ある点について反転する回数を求めれば全部わかる。
https://beta.atcoder.jp/contests/agc018/tasks/agc018_b ずっとどうやったらこんなの思いつくんだと思っていましたが、必要条件から攻めれば思いつけます。Constructive的発想。
https://beta.atcoder.jp/contests/cf16-tournament-round1-open/tasks/asaporo_c 最小全域木上のpathで最大の辺を選べば良いことがわかる。sとtを同じ点とみなすをsとtの間にコスト0の辺を張るという言い換えはお見事。
https://beta.atcoder.jp/contests/cf16-tournament-round2-open/tasks/asaporo_e 漸化式やるだけ。受験数学かな?
https://beta.atcoder.jp/contests/cf16-final-open/tasks/codefestival_2016_final_d 余りがjのやつとM-jのやつで最大マッチング。グラフの形がだいぶ特殊なので簡単な貪欲法でできる。
https://beta.atcoder.jp/contests/cf16-tournament-round3-open/tasks/asaporo_d スライド最小値やるだけ。
https://beta.atcoder.jp/contests/code-festival-2016-qualb/tasks/codefestival_2016_qualB_d ちょっと考えると111111222222223333333...みたいな形にすれば良いことがわかる。
https://code-festival-2017-qualc.contest.atcoder.jp/tasks/code_festival_2017_qualc_d だからdpになるととたんにわからなくなるよなぁ。DPだと思ったらとりあえず性質に関する考察やめて状態について考えるべき。
3/27精進
https://arc081.contest.atcoder.jp/tasks/arc081_d まず2*2の正方形に注目して塗られているマスが奇数個だとその正方形を一色にすることはできないことに気づきます。そうしたらそのような正方形を全部含まないような長方形のうち最大のものを求めればいいです。これはヒストグラム最大長方形と同じ要領でできますが、めちゃくちゃバグらせたので結局蟻本写経しました。LとRを素直に求めるのがやっぱりよさそう。あとstackとかいうゴミを許すな。queueを使いましょう。
https://arc085.contest.atcoder.jp/tasks/arc085_c maximum closure problem、また別に記事書きます。小さい約数全部決め打って大きいの適当にやるかと思ったけど違いました。
COLOCON -Colopl programming contest 2018- Final,E: キャプテン・タカハシ
https://colopl2018-final.contest.atcoder.jp/tasks/colopl2018_final_e
rep(i, H + 1) rep(W, M) AS[i] += min(i, A[j]);
通した人の多くがこのようなコードを書いているわけですが、これだけ解説します。
Bがsource側、Aがsink側だとします。
Bのうちi辺がcutされたとして、この時のmincutを求めましょう。
すると容量Aiの辺をsupersourceのグループに含めるとcostはAi,逆に含めないとcostはiになります。supersourceのグループ→supersinkのグループに向きが付いている辺のコストを求めるとこうなります。なので
mincut = Σ(k< i)Bk+Σ(0<=l< W)min(Ai, i)となります。このΣ(0<=l< W)min(Ai,i)を求めているのが上のコードです。
editorialを素直にコードにしたような人が少なかったので結構理解に苦戦しました。
なんか変な貪欲でみんな通しているのかなぁと思いましたが、結局フローをベースに考えているようですね。
あとHallの結婚定理は辺に重みが付いている時は使えないので注意しましょう。
AGC006C: Rabbit Exercise
https://beta.atcoder.jp/contests/agc006/tasks/agc006_c
おもしろかったので別に記事書きました。
まず簡単な計算をすると、ai,ai+1,ai+2と場所の期待値が求まっており、ai+1が行動するとき、ai+1の期待値はai+1→ai+ai+2-ai+1となることがわかります。
次の場所の期待値は前の場所の線型結合の和で表せるので行列累乗すればO(N^3logK)で求められます。
しかしN=10^5なので到底間に合いません。
ここでai+1-aiとai+2-ai+1に注目すると、ai+1-ai→ai+2-ai+1,ai+2-ai+1→ai+1-aiになっていることがわかります。つまりswapされたことになっています。なのでM回swapされた後の位置は置換行列で求められ、置換行列同士の掛け算は一回あたりO(N)で済むのでO(NlogK)でK回おこなかった後の場所もわかります。あとは累積和するだけです。
4項の関係を差のswapに言い換えるのは難しいですね…。
こんなの計算できるのはシンプルに驚きでした。
int N, M; ll K; ll A[MAX_N]; vi ordfun(const vi& vec1, const vi& vec2) { vi res(N - 1); rep(i, 0, N - 1) { res[i] = vec2[vec1[i]]; } return res; } vi ordpow(vi vec, ll K) { if(K == 1) return vec; else { vi tmp = ordpow(vec, K / 2); tmp = ordfun(tmp, tmp); if(K % 2 == 0) return tmp; else return ordfun(tmp, vec); } } void solve() { cin >> N; rep(i, 0, N) cin >> A[i]; cin >> M >> K; vector<int> vec(N - 1); rep(i, 0, N - 1) vec[i] = i; rep(i, 0, M) { int a; cin >> a; a--; swap(vec[a], vec[a - 1]); } vec = ordpow(vec, K); ll cur = A[0]; rep(i, 0, N) { cout << cur << "\n"; if(i != N - 1) { cur += A[vec[i] + 1] - A[vec[i]]; } } }
3/26精進
https://beta.atcoder.jp/contests/cf16-final-open/tasks/codefestival_2016_final_c 二部グラフでdfs
https://beta.atcoder.jp/contests/agc004/tasks/agc004_d 下からk-1番ごとに1に繋げれば良い。上から見るのではなく下から見るのが重要
https://beta.atcoder.jp/contests/agc006/tasks/agc006_c めっちゃ面白い。置換行列の累乗になる。
https://beta.atcoder.jp/contests/agc008/tasks/agc008_d 端から埋めれば良い。フロー知っていると若干思いつきやすいか。
https://beta.atcoder.jp/contests/agc009/tasks/agc009_b 高さをsortして+n,+n-1,+n-2...+1としたもののmaxを取る。
https://beta.atcoder.jp/contests/agc021/tasks/agc021_b convex hull持っていたので通してみた。角度が重要
https://beta.atcoder.jp/contests/cf17-final-open/tasks/cf17_final_b abcabcabc...しかありえません。
https://beta.atcoder.jp/contests/arc074/tasks/arc074_b priority_queue
https://colopl2018-final.contest.atcoder.jp/tasks/colopl2018_final_e やっと理解した…フローで考えるんですけど、ACした人のコードが理解できなくてまさか変な貪欲でできるのではと錯覚してしまった。
