蟻本をする2(中級編)
ymduu.hatenablog.com
の続き、こんどは中級編だ
例題 3-1-1 lower_bound
自力: 〇
lower_bound やるだけ
類題
自力: 〇
https://atcoder.jp/contests/abc077/submissions/10357158
Bを決めた時に使えるCの場合の数を累積和しておけばA固定でも解ける、Bを固定するとそういう小細工をしなくても解ける
3つの変数がうごく -> 真ん中(のこり2つの両方に直接影響する) を固定すると嬉しいことが多い
例題 3-1-2 Cable Master (POJ No.1064)
自力: 〇
解を仮定して二分探索シリーズ
類題:
自力: 〇
https://atcoder.jp/contests/abc023/submissions/10373489
受けるペナルティを固定すると、各風船を何秒以内に破壊すべきかがわかるのでソートすれば可能かどうかをNlogNで判定可能
例題 3-1-3 Aggressive Cows (POJ No.2456)
自力: 〇
上と同様に最小値を決め打ちすればOK
類題:
自力: 〇
https://atcoder.jp/contests/code-festival-2015-quala/submissions/10421073
例題 3-1-4 平均最大化
自力: ×
解xを固定すると、その解が可能かどうかは式変形により貪欲に判定できるようになるパターン
類題:
自力: 〇
https://atcoder.jp/contests/abc034/submissions/10422151
例題 3-2-1 Subsequence (POJ No.3061)
自力: 〇
oldskool しゃくとり
類題:
自力: 〇
https://atcoder.jp/contests/abc032/submissions/10506572
例題 3-2-2 Jessica's Reading Problem (POJ No.3320)
自力: 〇
ある要素aの個数が0になった時は次のaが現れるまでrを進める、とすると実装が楽になる
類題:
自力:〇
https://atcoder.jp/contests/arc022/submissions/10524534
上に同じ
例題 3-2-3 Face The Right Way (POJ No.3276)
自力: ×
ライツアウトの結果は操作を行う場所の集合にのみ依存し、順番には依存しないことに気を付ける。
これさえ分かっていれば、左から順番に決めていくことで問題のサイズを1ずつ小さくすることができる。
ただし、この問題はそれだけではだめで、数列 f において、区間 [l, r] の和は、[l-1, r-1] + f[r] - f[l-1] で表せることを利用して差分だけ更新していく必要がある。
-> 長さNの数列において、固定長の区間を全走査したい場合は差分更新することでO(N)にできる
類題:
自力: 〇
https://atcoder.jp/contests/arc064/submissions/10538540
端から順番に決めていく系
例題 3-2-4 Fliptile (POJ No.3279)
自力: ×
今度は上1行を固定すると全体のひっくり返し方が決まるパターン
類題:
自力: 〇
https://atcoder.jp/contests/joi2008yo/submissions/10544690
例題 3-2-5 Physics Experiment (POJ No.3684)
自力: 〇
蟻と同じ考察をすればオッケー
類題:
自力: ×
https://atcoder.jp/contests/agc013/submissions/10667472
蟻の考察をすると蟻の順番は変わらないことがわかるけれど、その先で0番の蟻がどこにいくのか分からずgg
けんちょんさんのブログを見て、原点を左右に通過する蟻の数を数えると最初の位置からいくつズレたかが分かるのでOK
例題 3-2-6 4 Values whose Sum is 0 (POJ No.2785)
自力: 〇
くじびきと同じ
類題:
自力: 〇
https://atcoder.jp/contests/joi2008ho/submissions/10756669
例題 3-2-7 巨大ナップサック
自力: ×
類題: 〇
実装が重くてしんどい、DPの方のナップザック問題はソラで書けるようになっていたので成長をかんじる
https://atcoder.jp/contests/abc032/submissions/10771038
例題 3-2-8 領域の個数
自力: ×
線がある座標の±1の場所も含めて座圧するのがポイント
類題:
自力: 〇
AOJ で解いたんだけどURLがどっかいってしまった
例題 3-3-1 Crane (POJ No.2991)
自力: ×
つらい
類題:
自力: 〇
https://atcoder.jp/contests/arc008/submissions/10939720
手で試すとちゃんと結合則が成り立ってエモいです、ついでに座圧の復習もできてアド
例題 3-3-2 バブルソートの交換回数
自力: ×
類題:
自力: 〇
https://atcoder.jp/contests/chokudai_S001/submissions/10963786
転倒数、こわそう、と思っていたけど前から順番にセグ木で出てきた数を覚えておいて今見ている数より大きい数の個数を数えるだけだった、こわくない
例題 3-3-3 A Simple Problem with Integers (POJ No.3468)
自力: 〇
類題:
RSQRAQ
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4270233#1
例題 3-3-4 K-th Number (POJ No.2104)
自力: 〇
類題:
自力: 〇
https://atcoder.jp/contests/arc033/submissions/10982608
平方分割はセグ木の深さを1にして各ノードの区間長をsqrt(N) にした感じ、実装が軽いのに一点更新区間取得が超定数倍軽いsqrt(N)でできてえらい
例題 3-4-1 巡回セールスマン問題
自力: ×
類題:
自力: △(ソラで書けず)
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4281785#1
例題 3-4-2 Traveling by Stagecoach (POJ No.2686)
自力: 〇
bitDPというよりも拡張ダイクストラのような？
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4282437#1
脳内でなく例題をAOJでACしたので類題は無し
例題 3-4-3 ドミノ敷き詰め
自力: ×
dp[i][j][S] := i行j列まで埋まっていて、下端の状態がSの時の場合の数 なるbitDPをする
類題:
自力: 〇
https://atcoder.jp/contests/code-festival-2014-quala/submissions/11078114
dp[i][j][S] := i(1-indexed) 桁目まで決めたとき、状態jであり使っている数の集合がSであるときの差の最小値というDPをした
— AIRをプレイする (@ymduu) 2020年3月22日
104 1 みたいな時は 111 でなく 99 が最適であることを見逃してWAしたもののストレステストで無事発見でき、かなりの良さ
— AIRをプレイする (@ymduu) 2020年3月22日
例題 3-4-4 フィボナッチ数列
自力: ×
漸化式のn番目は漸化式を一つすすめる行列を定義してその行列をかけることで求められる。
は、という感じだけど言われればまあそうだね、という感じだし行列積の手続きからも自明
類題
自力: 〇
https://atcoder.jp/contests/abc009/submissions/11369837
演算が特殊でも演算が半環をなしていれば行列積が計算できるのでgg
例題 3-4-5 Blocks (POJ No.3734)
自力: ×
http://poj.org/showsource?solution_id=21536909
DP 高速化 としての行列累乗、結局赤の偶奇と緑の偶奇で4通りしか状態がないので O(N) のDPは自然に思いつくはずで、それを行列累乗で高速化する。
最初 2 * 2 の 行列を考えてハマったけどこういうのは1列の行列で考えると見通しがよくなりがちっぽい
類題
POJ で実装までやったのでなし
例題 3-4-7 Matrix Power Series (POJ No.3233)
自力: ×
http://poj.org/showsource?solution_id=21552608
知ってるかゲーって気はするけど
類題
POJ で実装までやったのでなし
例題 3-4-8 Minimizing Maximizer (POJ No.1769)
自力: ×
POJ だと C++ の新しい機能バリバリの抽象化セグ木が使いづらいので、1点更新区間min のセグ木を写経した、よい復習になった
http://poj.org/showsource?solution_id=21553375
類題: POJ で実装までやったのでなし
てか類題が赤 diff ばっかりなんだが
ついにフローにたどりつきました
例題 3-5-1 最大通信量
例題はなし
類題:
自力: △(蟻本のF-Fを使ってるライブラリに合わせて改変しつつ写経した)
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4329720
自力: 〇
マークしてる人から辺を張るノードを一つ用意してそこにたどり着けなくするための最小カットを求めればOK -> 最大流最小カット からフローを流せばOK
例題 3-5-2 仕事の割り当て
自力: 〇
二部グラフの最大マッチングは知っていたのでフローを持っていれば解けるね
類題:
自力: 〇
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4330160#2
自力: 〇
https://atcoder.jp/contests/abc091/submissions/11633199
例題 3-5-3 はたいへんなのでパス(は)
例題 3-5-4 最小費用流
自力: ×
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4336350#1
残余グラフにおいて、辺に流すときのコストを距離と見て最短経路問題を解き、その最短経路(つまり、最小コストで s-t に流せる経路)に流せるだけ流すことを繰り返す。
例題 3-5-5 Asteroids (POJ No.3041)
自力: ×
http://poj.org/showsource?solution_id=21562701
X 座標と Y 座標 をグラフのノードとみなし、隕石があるところに辺を張った二部グラフを構成する
そのようなグラフの最小点カバー問題を解けばよく(点 = ビームを撃つ X or Y座標)、これは二部グラフの最大マッチングに等しい
類題:
https://atcoder.jp/contests/soundhound2018/submissions/11692524
- グリッドグラフは市松模様に塗ると二部グラフ
- (x + y) もしくは (x - y) の偶奇でどちらに属するかを判定可能
- 二部グラフの最大マッチングをするときには、2つの集合をU, V として U -> V みたいに向きを付けておかないとフローを流すときに戻れてしまい終わる
- 最大安定集合(ノード同士が隣接しないようになるべく多くのノードを取る) -> 最大マッチングから計算できる、蟻本P199参照
例題 3-5-6 Evacuation (POJ No.3057)
自力: ×
この辺からくるしくなってきた
時間を固定すると(各時間,各ドア)から出られうる人間 という 二部グラフが作れるので、最大マッチングが人間の数だけあればOK
類題:
自力: ×
https://atcoder.jp/contests/arc013/submissions/11709738
作れうる各重さに関して高橋君のノード、青木君のノードを作成し、それらと鉄塊を表すノードを繋いだ二部グラフに始点終点を追加したもの に対してフローを流そうとしたが嘘なのでGG
正しい方法は、各重さについて2個以上作れればよいので、各重さを表すノードを2個ずつ作り、それらが同時に作れる場合(≒一つの鉄塊から切り出せる場合)に辺を張る。
そうして構成したグラフは二部グラフになり、「各重さが2つ以上作れる」 とは、このグラフの辺を適切に選んで、どの頂点も選んだ辺に接続している 状態にできればよい。
これは最小辺カバー問題であるので、最大マッチングから求めることができる。(蟻本P199参照)
なんだかお気持ちは Asteroids と同じ気もする
二部グラフに落としたいなあという気持ちがあって、{XY, 作れる重さ}を二部グラフの集合として、{隕石がある, 同時に作れる}を辺として、それの{最小点カバー, 最小辺カバー}を求める。
例題 3-5-7 Dining (POJ No.3281)
自力: ×
(食べ物, 牛), (飲み物, 牛) の同時割り当てを求める問題。
食べ物 -> 牛 -> 飲み物 のフローを流したくなるが、それはだめ。
なぜなら、一つの牛に対して複数のフローが流れてしまう可能性があるから(蟻本の例: s->食べ物1->牛1->飲み物1->t とs->食べ物2->牛1->飲み物3->t が同時に流れうるが、これを2頭の要求を満足すると数えてしまう。)
食べ物側と飲み物側のマッチンググラフを分け、同じ牛同士の間に容量1の辺を張ることで、一つの牛には一つの割り当てが行われるようになり(P192 頂点に容量がある場合 の考え方と同じ)、正解となる。
http://poj.org/showsource?solution_id=21566325
例題 3-5-8 Dual Core CPU (POJ No.3469)
自力: ×
燃やす埋める問題、診断人さんのスライドがマジでわかりやすい。
www.slideshare.net
小問題一つに対し、コストのかかる選択肢が2つあってそれを選ぶ、さらにその選択肢間に依存関係がある(グラフに見えてくる)場合は適切なグラフを作り最小カット(=最大流)を計算するとうまくいくことが多い。
気持ちとしては、始点sと終点tを用意して、s -> 選択肢1に対応する辺 -> 小問題に対応する頂点 -> 選択肢2に対応する辺 -> t なるグラフを作って、適切な方をカットする(≒選択肢を選ぶ)ことでs-tカットをつくるぞ、というもの。
蟻本の構築方法を後から見ても若干 ？？？ という感じだったので先に診断人さんのスライドを見てよかった
http://poj.org/showsource?solution_id=21566683
ところで、Dinic の計算量ってO(EV2)だけど、この問題はV = 2 * 104、E = 2 * 105 で、4 * 1013 で明らかに適用できないサイズに見えるんですけど……
Dinic は速い！とは聞くものの105倍速くなったりするものだろうか、それとも計算量の見積もりを間違えている？
例題 3-5-9 Farm Tour (POJ No.2135)
自力: 〇
http://poj.org/showsource?solution_id=21566867
容量2の最小費用流を流すだけ、逆向きの辺も追加する必要があることに注意(最大流と同じような議論で無向の時は逆辺を張ればいいことがわかる)
この辺全部 POJ で解いているけど、フロー系の問題は Dinic と Ford-Fulkerson と Primal-Dual さえあればあとは個別のアドホックなので、ライブラリを C++03 に対応させる手間が少なくてらくだった
例題 3-5-10 Evacuation Plan (POJ No.2175)
自力: ×
二部グラフの最小重みマッチングは最大マッチングの時みたいに最小費用流を流すことで解ける。
類題:
自力: ×
https://atcoder.jp/contests/abc004/submissions/11717678
例題 3-5-11 The Windy's (POJ No.3686)
自力: ×
http://poj.org/showsource?solution_id=21579994
非直感的な式変形をする問題、工場iでj個のおもちゃを作る時、k番目(0-indexed)に到着した依頼は終了時間の総和にj-k回効いてくることから、工場の頂点を倍加して工場iでk回目の依頼を処理する、というノードを作り、おもちゃlからコスト(j-k) * Z[l][i] とした辺を張る。
例題 3-5-12 Intervals (POJ No.3680)
自力: ×
http://poj.org/showsource?solution_id=21580272
言いたいことは分かるけど自力で思いつくのは無理だなあ、最後だし撤退するのも気持ち悪いので写経AC
蟻本P205のFが一定の時負辺を除去するテクを使っている
これは負辺を除去するために、負辺に目一杯流す≒負辺(u, v)のコストを最初から計上して、代わりにコスト0でu->t, s->v (sは新たに追加した始点、tは新たに追加した終点)に流せる辺を追加するというもの。(これを飲み込むのに2時間くらいかかったので元気が出たらまとめる)
