LoginSignup
461
430

More than 3 years have passed since last update.

@drken(けんちょん (Otsuki))in株式会社NTTデータ数理システム

AtCoder 版！蟻本 (中級編)

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 上の類題】

【コメント】
高難易度問題において部分的に登場するイメージが強いテクです。
求めるものが「最小の区間」か「最大の区間」かはあまり影響がないです。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 上の類題】

【コメント】
dp を立てて行列累乗に持ち込むタイプの問題です。

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

【キーワード】

  • 行列累乗

【AtCoder 上の類題】

【コメント】
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 上の類題】

【コメント】
最大流問題の最もよくある応用として、二部グラフの最大マッチングがあります。二部グラフの最大マッチングに関連する話題として Hall の定理があります。これは二部グラフに対する最大流最小カット定理や、Dilworth の定理 (下に出て来ます) との等価性も知られており、ネットワークフロー理論の強力な定理群の 1 つの側面と考えることができます。

例題 3-5-3　二人組

【キーワード】

  • 一般グラフの最大マッチング (not フロー)

【AtCoder 上の類題】

【コメント】
一般グラフの最大マッチングです。大きく以下の 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 上の類題】

【コメント】
いわゆる 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 上の類題】

【コメント】
「燃やす埋める」の愛称で親しまれている 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 上の類題】

【コメント】
非常に中身の濃い問題です。蟻本にて、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 上の類題】

【コメント】
無限の選択肢のある最適化問題に対して、ギリギリの場合だけ考えればよいという考察をするタイプの問題です。

例題 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 の問題に結び付け、さらに類題を加える試みをしてみました。改良案をドンドン募集しています！

461
430
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
461
430