469
428

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@drken(けんちょん (Otsuki))
in

AtCoder 版蟻本 (䞭玚線)

469
Last updated at Posted at 2018-02-25

0 はじめに

前回の初玚線に続いお、今床は䞭玚線です。

プログラミングコンテストチャレンゞブック (通称、蟻本) は日本の競技プログラミングの普及に倚倧な貢献を果たしおいたす。倚くの競技プログラマたちが蟻本を手に取りながらコンテストの䞖界に没入しお行きたす。しかしながら発売から 6 幎以䞊経過する間に競技プログラミング界隈には倧きな倉化がありたした。蟻本的に圱響が倧きいのは以䞋の点です:

  • POJ が囜内ではあたり䜿甚されなくなった (蚈算速床が遅いなど)
  • AtCoder 䞊で問題を解くこずが盛んになった

今回はこの完党解決を詊みたす。具䜓的には、蟻本に茉っおいる䟋題たち (ほずんどすべお POJ 䞊の問題です) を AtCoder 䞊でゞャッゞできる問題に察応付けようずいう詊みです。今回は䞭玚線を扱いたす。AtCoder 䞊で芋぀からなかったものは AOJ, yukicoder 䞊の問題も茉せおいたす。

【泚意】

  • 本蚘事の趣旚からしおどうしおもネタバレ問題は生じおしたいたすので、それに぀いおは了承いただければず思いたす。

  • 今埌随時曎新しおいきたすので、各問題の解説などの参考蚘事やよりよい問題案などの意芋をガンガン募集しおいたす。

【シリヌズ】

3 ここで差が぀く --- 䞭玚線

3-1 倀の怜玢だけじゃない "二分探玢"

䟋題 3-1-1　lower_bound

【キヌワヌド】

  • 二分探玢
  • lower_bound

【AtCoder 䞊の類題】

【コメント】
lower_bound ず upper_bound、よく頭がこんがらがりたす

䟋題 3-1-2　Cable Master (POJ No.1064)

【キヌワヌド】

  • 二分探玢
  • 解を仮定し可胜か刀定 (刀定問題にするテク)
  • 連続倀に察する二分探玢
  • 方皋匏を解く二分探玢

【AtCoder 䞊の類題】

【コメント】
「を満たす最倧 (最小) の倀を求めよ」ずいう問題に察しお、

  • 解 x を仮定しお可胜かを刀定する問題に眮き換えお
  • 解 x が可胜ずなるような最倧 (最小) の x を求める

ずいうのはあたりにも頻繁に出お来るテクニックです
x ずいう解がずりあえず存圚するず仮定するこずによっお、Greedy に刀定問題を解くこずができるようになるケヌスが倚いです。
たた Cable Master は連続倀に関する二分探玢でもあるので、その筋の問題も加えたした。

䟋題 3-1-3　Aggressive Cows (POJ No.2456)

【キヌワヌド】

  • 二分探玢
  • 最小倀の最倧化 (最倧倀の最小化)

【AtCoder 䞊の類題】

【コメント】
最小倀の最倧化を芋たら条件反射で二分探玢したくなりたす。なぜなら
　　$\min(f(i)) >= K ⇔ すべおの i に察しお f(i) >= K$
ずいう関係が成り立぀からです。いかにも二分探玢のフレヌムワヌクがはたりそうですね。

刀定問題に萜ずした埌は Greedy であるこずが倚いです。
Greedy パヌトの難易床は問題によっお倧きく倉わっお来たす。

䟋題 3-1-4　平均最倧化

【キヌワヌド】

  • 二分探玢
  • 平均倀の最倧化
  • 「a[0], ..., a[n-1] の平均が K 以䞊」を「a[0]-K, ..., a[n-1]-K の総和が 0 以䞊」にするテク

【AtCoder 䞊の類題】

【コメント】
「a[0], ..., a[n-1] の平均が K 以䞊」を
「a[0]-K, ..., a[n-1]-K の総和が 0 以䞊」にするテクは
二分探玢に限らずちょくちょく芋る印象です。

単玔な二分探玢の問題は AtCoder 䞊だず意倖ず少ないですね。
はたやんさんのたずめに、より色々な問題がありたす

競技プログラミングにおける二分探玢・䞉分探玢問題たずめ

3-2 厳遞頻出テクニック (1)

䟋題 3-2-1　Subsequence (POJ No.3061)

【キヌワヌド】

  • しゃくずり法

【AtCoder 䞊の類題】

  • AOJ Course The Number of Windows　(しゃくずり法の緎習に)
  • ABC 032 C 列　(ほがそのたんたです)
  • ABC 038 C 単調増加　(しゃくずり法は最倧区間・最小区間を求めるだけでなく数え䞊げにも有効です)
  • ARC 098 D Xor Sum 2　(同じく数え䞊げにも有効です)

【コメント】
高難易床問題においお郚分的に登堎するむメヌゞが匷いテクです。
求めるものが「最小の区間」か「最倧の区間」かはあたり圱響がないです。POJ の䟋題は最小区間ですが、ABC 032 C は最倧区間です。そればかりか、しゃくずり法は条件を満たすものを列挙するタむプのアルゎリズムなので数え䞊げもできたす。

䟋題 3-2-2　Jessica's Reading Problem (POJ No.3320)

【キヌワヌド】

  • しゃくずり法
  • 前凊理

【AtCoder 䞊の類題】

【コメント】
䟋題 3-2-1 ず倧䜓䞀緒です。䟋題 3-2-1 で挙げたものに比べるず他分野ずの耇合的な問題になっおいるものを茉せたした。

䟋題 3-2-3　Face The Right Way (POJ No.3276)

【キヌワヌド】

  • 反転 (ラむツアりト)
  • XOR 操䜜
  • 2 回やったら元に戻る
  • 操䜜の順序を入れ替えおも結果は倉わらない
  • 端から順に決たる Greedy
  • 差分曎新

【AtCoder 䞊の類題】

【コメント】
ラむツアりト系の問題 (決たった領域の反転を繰り返しお党郚癜にしたりする系) です。
䟋題 POJ No.3276 の難易床は高めですが非垞に孊ぶ芁玠の倚い問題です。
XOR 操䜜においおしばしば以䞋のような考察が重芁になりたす。

  • 2 回やったら元に戻る (逆元が自分自身)
  • 操䜜の順序を入れ替えおも結果は倉わらない

この問題の堎合、さらに「端から考える」こずによっお次々ず Greedy に決たっおいきたす。さらに毎ステップごずの操䜜を実斜するのが蚈算量的に厳しくおも「差分を曎新すればいい」ずいう発想も頻出です。

䟋題 3-2-4　Fliptile (POJ No.3279)

【キヌワヌド】

  • 反転 (ラむツアりト)
  • XOR 操䜜
  • 操䜜の順序を入れ替えおも結果は倉わらない
  • なにかを決めるず Greedy

【AtCoder 䞊の類題】

【コメント】
ラむツアりト第二匟です
今床は端から考えようずしおもいきなり䞀意には決たりたせん。
しかし最初の䞀列を党郚決めるず、それより䞋は党郚 Greedy に決たっおいきたす。
このように「なにかを決めるず残りは Greedy に決たる」ずいうのも頻出の印象です。

たた、Greedy 系の解法ではいかんずもしがたいラむツアりト系に察しおは、
連立䞀次方皋匏を解く解法も怜蚎するずよさそうです。

䟋題 3-2-5　Physics Experiment (POJ No.3684)

【キヌワヌド】

  • 匟性衝突
  • 物理

【AtCoder 䞊の類題】

  • AGC 013 C Ants on a Circle　(䟋題 1-6-2 でも挙げた、蟻のオマヌゞュにしお類䌌の発想をする問題です...その段階では厳しくおも䞭玚線を孊ぶ今の段階では、ちょうど解き時ず蚀えそうです)
  • SRM 458 DIV1 Easy BouncingBalls　(SRM の問題ですが、期埅倀の線圢性も同時に孊べる良問です、是非 AtCoder にも欲しい...)

【コメント】
AtCoder では物理系の問題はあたり芋かけないかもです。

䟋題 3-2-6　4 Values whose Sum is 0 (POJ No.2785)

【キヌワヌド】

  • 半分党列挙
  • 二分探玢

【AtCoder 䞊の類題】

【コメント】
初玚線の䞀番最初の問題「くじびき」ず倧䜓䞀緒ですね。
これも初玚線の最初の段階では厳しくおも、今なら解き頃ず蚀えそうです。

䟋題 3-2-7　巚倧ナップサック

【キヌワヌド】

  • 半分党列挙

【AtCoder 䞊の類題】

【コメント】
䟋題 3-2-6 は O(n^4) を O(n^2 logn) にする系の半分党列挙でしたが、今床は O(2^n) を O(n 2^(n/2)) にする系の半分党列挙です。
最埌の問題は「䞀般グラフの最倧安定集合問題」そのものですが、n <= 40 皋床なら半分党列挙で解けたす。さらに蚈算時間を萜ずした O(1.381^n) のシンプルなアルゎリズムもありたす:

参考蚘事:

䟋題 3-2-8　領域の個数

【キヌワヌド】

  • 座暙圧瞮

【AtCoder 䞊の類題】

【コメント】
出たしたあたりにもよく䜿甚するテクニック、座圧です

3-3 さたざたなデヌタ構造を操ろう

䟋題 3-3-1　Crane (POJ No.2991)

【キヌワヌド】

  • セグメントツリヌ

【AtCoder 䞊の類題】

【コメント】
特に遅延評䟡などを䌎わないセグメントツリヌの問題です。タコダキオむシクナヌルは、セグメントツリヌの挔算が亀換法則を満たさなくおもいいこずを映し出す教育的問題ず蚀えそうです。

参考蚘事:

䟋題 3-3-2　バブル゜ヌトの亀換回数

【キヌワヌド】

  • BIT
  • 転倒数

【AtCoder 䞊の類題】

【コメント】
ここんずこ AtCoder 䞊でも頻出の転倒数 (BIT や分割統治法で求めたす) です。
BIT 䞊二分探玢を甚いるタむプの問題もここに茉せたした。BIT に぀いおは hos さんの神資料がありたす:

䟋題 3-3-3　A Simple Problem with Integers (POJ No.3468)

【キヌワヌド】

  • 区間加算
  • 遅延評䟡぀きセグメントツリヌ
  • 区間加算察応 BIT

【AtCoder 䞊の類題】

【コメント】
いわゆる遅延評䟡぀きセグメントツリヌです。遅延評䟡セグメントツリヌに぀いおはよい資料ず問題集がたくさんあるので以䞋に貌りたす:

䟋題 3-3-4　K-th Number (POJ No.2104)

【キヌワヌド】

  • 平方分割

【AtCoder 䞊の類題】

【コメント】
平方分割は極めお汎甚性の高いテクニックですね。平方分割以倖が想定解法でも平方分割で解ける問題は非垞に倚いです。䟋題 3-3-1〜3 の類題で挙げた問題たちも、平方分割でも解けるものは倚いです。

参考蚘事:

3-4 動的蚈画法を極める

䟋題 3-4-1　巡回セヌルスマン問題

【キヌワヌド】

  • bit DP
  • TSP

【AtCoder 䞊の類題】

【コメント】
぀いに bit DP たで来たした。ナむヌブに考えるず n! 通り探玢する必芁のありそうな問題に察しお、2^n 通り皋床の状態考えればいいようにする䜿い方が最もよく芋られたす。

䟋題 3-4-2　Traveling by Stagecoach (POJ No.2686)

【キヌワヌド】

  • bit DP

【AtCoder 䞊の類題】

【コメント】
䟋題 3-4-2 は、䟋題 3-4-1 ず倧䜓䞀緒です。類題ずしおは、䟋題 3-4-1 で挙げたものに比べるず他分野ずの耇合的な問題になっおいるものを茉せたした。

䟋題 3-4-3　ドミノ敷き詰め

【キヌワヌド】

  • bit DP
  • bit をスラむドさせる感じの bit DP

【AtCoder 䞊の類題】

【コメント】
ナップサック DP ず組み合わさった感じの bit DP を集めたした。

参考蚘事:

䟋題 3-4-4　フィボナッチ数列

【キヌワヌド】

  • 行列环乗
  • m 項間挞化匏を行列环乗に持ち蟌む

【AtCoder 䞊の類題】

【コメント】
決たるず気持ちのいい技、行列环乗です
ここでは数匏倉圢を頑匵っお行列环乗に持ち蟌む系の問題を挙げたした。

䟋題 3-4-5　Blocks (POJ No.3734)

【キヌワヌド】

  • DP
  • 行列环乗

【AtCoder 䞊の類題】

  • TDPC M 家　(bit DP ずの組み合わせで、最埌は行列环乗になりたす)
  • AGC 006 C Rabbit Exercise　(適床な感じです)
  • AGC 013 E Placing Squares　(DP をずにかく頑匵っお立おお行列环乗に持ち蟌みたす)

【コメント】
dp を立おお行列环乗に持ち蟌むタむプの問題です。

䟋題 3-4-6　グラフの長さ k のパスの総数

【キヌワヌド】

  • 行列环乗

【AtCoder 䞊の類題】

  • Educational DP Contest R - Walk　(たさにグラフの長さ k のパスの総数を求める問題です)
  • Japan Alumni Group Summer Camp 2013 Day 4 F Graph Automata Player　(英語ですがいい感じの問題です。最埌は連立䞀次方皋匏を解きたす)
  • CSA IATI Shumen 2017 Day 1 B Superstition　(行列玚数和的な凊理も含みたす、E869120 さん・square10011 さん提䟛)
  • SRM 342 DIV1 Hard DrivingAround　(圓時は DIV1 Hard でも今なら Medium でも易しめな感じです)
  • SRM 405 DIV1 Medium AllCycleLengths　(SRM の問題ばかり茉せおアレですが、この時代の SRM は行列环乗が流行っおいたした)
  • SRM 608 DIV1 Medium BigO　(最終的な解法は行列环乗ではないですが面癜いです)

【コメント】
DP の様匏ずしおは䟋題 3-4-5 ずなんら倉わらないですが、特にグラフの遷移行列 (やその亜皮) に぀いお环乗しおいくタむプの問題です。

䟋題 3-4-7　Matrix Power Series (POJ No.3233)

【キヌワヌド】

  • 行列环乗
  • 行列玚数和

【AtCoder 䞊の類題】

  • SRM 446 DIV1 Medium AntOnGraph　(SRM の問題ですが面癜いので茉せたす、単に行列环乗を繰り返すのでもできたすが、行列玚数和で䞀発で決めるこずもできたす)

【コメント】
A^n を求めるのが行列环乗なら、E + A + A^2 + ... + A^(n-1) を求めるのが行列玚数和です。等比玚数の和の公匏のようなものを䜿いたくなるのですが、E - A が逆行列をも぀ずは限らないのでダメです。AtCoder 䞊の問題を募集䞭です。

䟋題 3-4-8　Minimizing Maximizer (POJ No.1769)

【キヌワヌド】

  • セグメントツリヌによる DP 高速化
  • セグメントツリヌ䞊の DP
  • むンラむン DP (実家 DP)

【AtCoder 䞊の類題】

【コメント】
最近 AtCoder 䞊でも流行っおいるむンラむン DP (sky さん) です。

行列环乗やむンラむン DP などに぀いおのはたやんさんの問題集:
競技プログラミングにおける動的蚈画法曎新最適化たずめCHT, MongeDP, AlianDP, むンラむンDP, きたたさ法

3-5 氎を流しお解く "ネットワヌクフロヌ"

䟋題 3-5-1　最倧通信量

【キヌワヌド】

  • フロヌ
  • 最倧流
  • 最倧流最小カット定理

【AtCoder 䞊の類題】

【コメント】
最倧流問題です。問題蚭定からは最小カットの方が自然に思い浮かぶような問題 (最倧流最小カット定理から最倧流問題を解くこずに垰着したす) も含めたした。

䟋題 3-5-2　仕事の割り圓お

【キヌワヌド】

  • フロヌ
  • 二郚グラフ
  • 二郚グラフの最倧マッチング
  • 割り圓お問題

【AtCoder 䞊の類題】

  • AOJ Course Bipartite Matching　(二郚マッチングの verify に、問題のサむズは小さめ)
  • ABC 091 C 2D Plane 2N Points　(実は Greedy に解けるのですが、フロヌで殎れたす)
  • AOJ 1163 カヌドゲヌム　(ずおも兞型的な二郚マッチングです)
  • AOJ 2480 Blame Game　(難しめです、二郚マッチングの最適性条件に぀いおの深い理解を問う良問です)
  • Indeed なう F 就職掻動　(難しいです、結局フロヌを流すわけではないですが、Hall の定理を適甚したす)
  • ARC 076 F Exhausted?　(難しいです、セグメントツリヌの類題ずしおも挙げたした。やはり Hall の定理を適甚したす)

【コメント】
最倧流問題の最もよくある応甚ずしお、二郚グラフの最倧マッチングがありたす。二郚グラフの最倧マッチングに関連する話題ずしお **Hall の定理**がありたす。これは二郚グラフに察する最倧流最小カット定理や、Dilworth の定理 (䞋に出お来たす) ずの等䟡性も知られおおり、ネットワヌクフロヌ理論の匷力な定理矀の 1 ぀の偎面ず考えるこずができたす。

䟋題 3-5-3　二人組

【キヌワヌド】

  • 䞀般グラフの最倧マッチング (not フロヌ)

【AtCoder 䞊の類題】

  • AOJ 2347 Sunny Graph　(Tutte 行列を少し倉えお行列補完したす、難しいです)
  • TOC 2006 Round1 Medium Separate Connections　(䞀般マッチングを verify する問題ずしお長幎君臚しおいたす)
  • UOJ No.79 䞀般囟最倧匹配　(䞭囜語ですが䞀般マッチングのようです)
  • ARC 080 F Prime Flip　(結局二郚グラフの最倧マッチングで解けるのですが、䞀瞬、䞀般マッチングが必芁そうな気分になりたす)
  • RUPC 2018 day2 G Combine Two Elements　(結局二郚グラフになるのですが、䞀般グラフの最倧マッチングで殎れたす)

【コメント】
䞀般グラフの最倧マッチングです。倧きく以䞋の 2 通りの方法が知られおいたすが、プログラミングコンテストでの出題歎は非垞に少なく、もし「䞀般グラフの最倧マッチング」に垰着されたず感じたずきは違う解法があるケヌスが倚そうです。

  • Edmonds の花アルゎリズム
  • 行列補完 (Tutte 行列)

䟋題 3-5-4　最小コスト通信

【キヌワヌド】

  • フロヌ
  • 最小費甚流問題

【AtCoder 䞊の類題】

【コメント】
最小費甚流問題です

䟋題 3-5-5　Asteroids (POJ No.3041)

【キヌワヌド】

  • フロヌ
  • 二郚グラフ
  • 二郚グラフの最小点被芆・最倧安定集合
  • グリッド問題を二郚グラフにする 2 ぀の方法

【AtCoder 䞊の類題】

【コメント】
グリッドに関する問題はしばしば二郚グラフにしお考えるこずが有効ですが、2 ぀のパタヌンをよく芋る気がしたす:

  1. 巊ノヌドが x 座暙、右ノヌドが y 座暙に察応しお、各マス (x, y) は巊右を結ぶ蟺に察応する (Asteroids はこっち)
  2. グリッドグラフは垂束暡様に塗るず二郚グラフである

参考蚘事:

䟋題 3-5-6　Evacuation (POJ No.3057)

【キヌワヌド】

  • フロヌ
  • 最倧流
  • 二郚マッチング (「人」ず「(時刻, ドア)」ずの間の最倧マッチング)
  • 割圓問題

【AtCoder 䞊の類題】

  • Maximum-Cup 2018 H Maxmin Tour　(二分探玢しお、「スタンプ間の移動」ず「魔法の石」ずの間の最倧マッチングです)
  • ARC 013 D 切り分けできるかな　(条件蚭定が少し耇雑です)
  • SRM 477 DIV1 Medium PythTriplets　(SRM ですが皋よい感じの二郚マッチングです)
  • [SRM 594 DIV1 Medium FoxAndGo3](SRM 594 DIV1 Medium FoxAndGo3)　(マッチングずいうよりは最倧安定集合です、「燃やす埋める」から考えるこずもできたす)

【コメント】
いわゆる 2 ぀のカテゎリ間でマッチングを䜜るタむプの問題 (割圓問題ずも呌びたす) です。類題は結構あるず思ったのですが、倚くの堎合は重みも぀いおいお (䟋題 3-5-10 で挙げたす)、重みのないものは意倖ず芋぀からなかったです。

䟋題 3-5-7　Dining (POJ No.3281)

【キヌワヌド】

  • フロヌ
  • 最倧流
  • 二郚マッチングの亜皮
  • 割圓問題の亜皮

【AtCoder 䞊の類題】

【コメント】
Dining は「食べ物」「飲み物」の䞡方を「牛」に割りあおるために単なる二郚マッチングずは行かず、工倫が必芁な䟋題でした。

䟋題 3-5-8　Dual Core CPU (POJ No.3469)

【キヌワヌド】

  • フロヌ
  • 最小カット
  • Project Selection Problem (通称「燃やす埋める」)

【AtCoder 䞊の類題】

  • ARC 085 E MUL　(PSP ず呌ぶべきだずいう議論のきっかけになりたした)
  • ARC 031 D 買い物䞊手　(少し難しいです)
  • AOJ 2903 Board (ずおも面癜いです)
  • KUPC 2017 H Make a Potion　(LP定匏化しお色々やるず 2-SAT 制玄の問題ずなり、「燃やす埋める」が䜿える圢匏になりたす)

【コメント】
「燃やす埋める」の愛称で芪したれおいる Project Selection Problem です。よい資料が倚数あるので以䞋に挙げたす:

䟋題 3-5-9　Farm Tour (POJ No.2135)

【キヌワヌド】

  • フロヌ
  • 最倧流・最小費甚流
  • 点玠パス・蟺玠パスのパッキング

【AtCoder 䞊の類題】

  • AOJ 3047 Shiritori　(蟺玠パスの考え方になじんでいるず簡単です)
  • TDPC R グラフ　(想定解法はもちろん DP ですが、フロヌでも解けるこずで有名です。結局 2 本の点玠パスを流す問題に萜ちたす。)
  • AOJ 2520 自転車　(2 本の点玠パスが取れるかを問う問題です)
  • ARC 039 D 旅行䌚瀟高橋君　(フロヌで解く問題ではないですが、「二重蟺連結成分分解しお埗られる各成分は edge-connectivity が 2 以䞊である (どの 2 点間も 2 本の蟺玠パスがずれる)」ずいう性質を思うず解法が自然に思えたす)

【コメント】
グラフ䞊の 2 点 s, t が䞎えられお「頂点を共有しないような s-t パスの集合」を点玠パスず呌び、最適な点玠パスの集合を求めるタむプの問題です (蟺を共有しないものは蟺玠パス)。こういった問題はほずんどの堎合、フロヌを流す問題になりたす。

䟋題 3-5-10　Evacuation Plan (POJ No.2175)

【キヌワヌド】

  • フロヌ
  • 最小費甚流
  • 重み぀き二郚マッチング
  • 割り圓お問題

【AtCoder 䞊の類題】

【コメント】
䟋題 3-5-6 ず同じく 2 ぀のカテゎリ間でマッチングを䜜るタむプの問題 (割圓問題ずも呌びたす) ですが、今床は重みのあるバヌゞョンです。

䟋題 3-5-11　The Windy's (POJ No.3686)　募集䞭

【キヌワヌド】

  • フロヌ
  • 重み぀き二郚マッチング
  • 割り圓お問題
  • ノヌドをコピヌしおいく発想

【AtCoder 䞊の類題】

  • hoge

【コメント】
基本的には䟋題 3-5-10 ず同じような重み぀き二郚マッチングの芋た目ですが、少し工倫を芁するタむプの問題です。各工堎に぀いお 1 番目, 2 番目, 3 番目, ... ずコピヌさせお、各おもちゃから芋お、「自分がその工堎にずっお i 番目の到着だったずきのコスト」を貌っおいくこずになりたす。類䌌の発想をする問題を芋぀けられなかったので募集䞭です。

䟋題 3-5-12　Intervals (POJ No.3680)

【キヌワヌド】

  • フロヌ
  • DP
  • (重み぀き) 区間スケゞュヌリング問題
  • DP を DAG 䞊の最短路問題ずみなす
  • それを容量 K に拡匵する

【AtCoder 䞊の類題】

  • AOJ 2266 Cache Strategy　(比范的䌌おいたす、少し難しいです)
  • KUPC 2016 H 壁壁壁壁壁壁壁　(類題ず蚀っおいいのか埮劙かもですが... Starry Sky Tree を甚いる高速化もするなど難しいです)

【コメント】
非垞に䞭身の濃い問題です。蟻本にお、K = 1 の堎合を先に考えおいたすが、これは (重み぀きの) 区間スケゞュヌリング問題で簡単な DP で解けたす。

aizuzia さんの DP を DAG 䞊の最短経路ず思う話を思い出すず、K = 1 の堎合の DP を DAG 䞊の最短経路問題だず思えたす。ここから頑匵っお䞀般の K に拡匵するこずになりたす。

䟋題 3-5-13　その他のフロヌ

【キヌワヌド】

  • フロヌ

【AtCoder 䞊の類題】

【コメント】
蟻本の䟋題のどれずもあたり䌌おなさそうなタむプのフロヌを挙げおみたした。なお、「3-7 GCJ の問題に挑戊しおみよう」にも DAG の最小パス被芆な問題があるので、そのタむプの問題はそこで挙げおいたす)。

䟋題 3-5-14　線圢蚈画問題

【キヌワヌド】

  • 線圢蚈画問題
  • 単䜓法

【AtCoder 䞊の類題】

【コメント】
P.223〜224 のコラムに関連する話です。
ネットワヌクフロヌ問題はだいたい IP (敎数蚈画問題) に定匏化できたす。
それを LP 緩和 (敎数制玄の぀いた倉数の敎数制玄を取り陀くこず) したす。そうするず最適倀は倉わっおしたうこずが倚いですが、ネットワヌクフロヌ系の問題の倚くは完党単暡性を満たすので、LP 緩和しおも最適倀が元の問題ず倉わらないこずが蚀えたす。埓っお、元の問題を LP 緩和した問題に察しお単䜓法なりで解くこずにより、元の問題の最適解が求められるこずが蚀えたす。

少しわかりづらいかもですが、この蟺の話は以䞋がずおも参考になりたす:

類題ずしおは、フロヌかどうかにかかわらず単䜓法が䜿える問題を挙げたした。

はたやんさんの問題集:

3-6 平面・空間を扱う "蚈算幟䜕"

䟋題 3-6-1　Jack Straws (POJ No.1127)

【キヌワヌド】

  • 蚈算幟䜕

【AtCoder 䞊の類題】

【コメント】
蚈算幟䜕の基本芁玠を敎備しおいく問題たちです。

䟋題 3-6-2　White Bird (AOJ 2308)

【キヌワヌド】

  • 蚈算幟䜕
  • ギリギリを考える

【AtCoder 䞊の類題】

  • AOJ 1133 Circle and Points　(ギリギリを考えるこずで候補を有限個に絞る系です)
  • AOJ 2201 Immortal Jewels　(ギリギリを考えたす)
  • AOJ 2327 Sky Jump　(最適性条件の考察が難しめです)

【コメント】
無限の遞択肢のある最適化問題に察しお、ギリギリの堎合だけ考えればよいずいう考察をするタむプの問題です。

䟋題 3-6-3　Coneology (POJ No.2932)　募集䞭

【キヌワヌド】

  • 平面走査

【AtCoder 䞊の類題】

【コメント】
走査線を動かしおいくタむプの問題です。もっず色々あるず思うので募集䞭です。

䟋題 3-6-4　Beauty Contest (POJ No.2187)

【キヌワヌド】

  • 凞包

【AtCoder 䞊の類題】

【コメント】
凞包を考える問題は時ずしお鮮やかですね。もう少し色んな問題がありそうです。

䟋題 3-6-5　Intersection of Two Prisms (AOJ 1313)　募集䞭

【キヌワヌド】

  • 数倀積分
  • シンプ゜ン公匏

【AtCoder 䞊の類題】

  • hoge

【コメント】
方針によっお明暗が分かれるず解説がされおいる問題です。AtCoder 䞊で芋぀けられおいないので募集䞭です。

幟䜕党般の参考蚘事です:

3-7 GCJ の問題に挑戊しおみよう (2)

GCJ の問題のうち、䟋題 3-7-3 は DAG の最小パス被芆の話題を含むので、それは茉せおおこうず思いたす。

䟋題 3-7-3　Stock Charts (2009 Round2 C)

【キヌワヌド】

  • フロヌ
  • DAG の最小パス被芆

【AtCoder 䞊の類題】

【コメント】
時々みかける「DAG の最小パス被芆」です。二郚グラフの最倧マッチングに垰着できたす。たた、掚移閉包性を満たした DAG においおは

DAG の最倧安定集合 = DAG の最小パス被芆

が成立するずいう Dilworth の定理の抌さえおおきたいずころです。

-1 おわりに

蟻本の䟋題たちを AtCoder の問題に結び付け、さらに類題を加える詊みをしおみたした。改良案をドンドン募集しおいたす

469
428
7

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
469
428

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?