AtCoder 版！蟻本 (上級編)

# 0 はじめに
[初級編](https://qiita.com/drken/items/e77685614f3c6bf86f44)と[中級編](https://qiita.com/drken/items/2f56925972c1d34e05d8)に続いて、今度は上級編です。

[プログラミングコンテストチャレンジブック](https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E3%83%81%E3%83%A3%E3%83%AC%E3%83%B3%E3%82%B8%E3%83%96%E3%83%83%E3%82%AF-%E7%AC%AC2%E7%89%88-%EF%BD%9E%E5%95%8F%E9%A1%8C%E8%A7%A3%E6%B1%BA%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E6%B4%BB%E7%94%A8%E5%8A%9B%E3%81%A8%E3%82%B3%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0%E3%83%86%E3%82%AF%E3%83%8B%E3%83%83%E3%82%AF%E3%82%92%E9%8D%9B%E3%81%88%E3%82%8B%EF%BD%9E-%E7%A7%8B%E8%91%89%E6%8B%93%E5%93%89/dp/4839941068) (通称、蟻本) は日本の競技プログラミングの普及に多大な貢献を果たしています。多くの競技プログラマたちが蟻本を手に取りながらコンテストの世界に没入して行きます。しかしながら発売から 6 年以上経過する間に競技プログラミング界隈には大きな変化がありました。蟻本的に影響が大きいのは以下の点です:

+ [POJ](http://poj.org/) が国内ではあまり使用されなくなった (計算速度が遅いなど)
+ [AtCoder](http://beta.kenkoooo.com/atcoder/?user=drken&rivals=&kind=category) 上で問題を解くことが盛んになった

今回はこの完全解決を試みます。具体的には、蟻本に載っている例題たち (ほとんどすべて POJ 上の問題です) を AtCoder 上でジャッジできる問題に対応付けようという試みです。今回は上級編を扱います。AtCoder 上で見つからなかったものは [AOJ](http://judge.u-aizu.ac.jp/onlinejudge/index.jsp), [yukicoder](https://yukicoder.me/) 上の問題も載せています。


**【注意】**

+ 本記事の趣旨からしてどうしてもネタバレ問題は生じてしまいますので、それについては了承いただければと思います。

+ 今後随時更新していきますので、各問題の解説などの参考記事やよりよい問題案などの意見をガンガン募集しています。


**【シリーズ】**

+ [AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067)
+ [AtCoder 版！蟻本 (初級編)](https://qiita.com/drken/items/e77685614f3c6bf86f44)
+ [AtCoder 版！蟻本 (中級編)](https://qiita.com/drken/items/2f56925972c1d34e05d8)
+ [AtCoder 版！蟻本 (発展的トピック編)](https://qiita.com/drken/items/0de3d205690d92307b7c)


# 4 さらに極める！ --- 上級編

## 4-1 より複雑な数学的問題

-----
####**例題 4-1-1　ランダムウォーク**
**【キーワード】**

+ 期待値
+ 連立一次方程式

**【AtCoder 上の類題】**

+ [AOJ 2171 Strange Couple](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2171)　(AOJ の問題ですが例題のランダムウォークに極めて近いです)
+ [Indeedなう 2015 E Page Rank](https://atcoder.jp/contests/indeednow-finala-open/tasks/indeednow_2015_finala_e)　(特殊な連立一次方程式を解きます)
+ [codeflyer 2018 本選 D 数列 XOR](https://atcoder.jp/contests/bitflyer2018-final-open/tasks/bitflyer2018_final_d)　(掃き出し法に関する理解を問います)
+ [AOJ 2530 Reverse Game](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2530)　(例題 3-2-4 の類題でも簡単に触れた F2 体上の連立一次方程式です、しかしサイズが大きいので **bitset 高速化**を用います)

**【コメント】**
連立一次方程式を解いたりする問題です。双六のような確率的挙動が出て来ると連立一次方程式を解くことになるケースが多いイメージがあります。

参考記事:

+ [競技プログラミングのための線形代数](http://topcoder.g.hatena.ne.jp/pepsin-amylase/20131203) (amylase さん)
+ [競技プログラミングにおける確率・期待値問題まとめ](http://hamayanhamayan.hatenablog.jp/entry/2016/11/14/223727) (はまやんさん)
+ [競技プログラミングにおける連立方程式問題まとめ](http://hamayanhamayan.hatenablog.jp/entry/2017/03/15/221719) (はまやんさん)

-----

-----
####**例題 4-1-2　mod 演算あれこれ, Fermat の小定理, 中国剰余定理**
**【キーワード】**

+ nCr
+ mod_inverse
+ Fermat の小定理、Euler の定理
+ 中国剰余定理、連立線形合同方程式

**【AtCoder 上の類題】**

+ [ABC 024 D 動的計画法](https://atcoder.jp/contests/abc024/tasks/abc024_d)　(nCr に関する式変形をします)
+ [AGC 001 E BBQ Hard](https://atcoder.jp/contests/agc001/tasks/agc001_e)　(難しめの二項係数計算をします)
+ [yukicoder 0186 中華風 (Easy)](http://yukicoder.me/problems/447)　(**中国剰余定理**ライブラリの verify に)
+ [AOJ 2659 箸](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2659)　(中国剰余定理を繰り返します)
+ [SRM 449 DIV1 Hard StairsColoring](apps.topcoder.com/stat?c=problem_statement&pm=10551&rd=13903)　(**カタラン数**のよい例ではありますが、最後が少し面倒です)
+ [Japan Alumni Group Summer Camp 2013 Day 3 D Fast Division](https://atcoder.jp/contests/jag2013summer-day3/tasks/icpc2013summer_day3_d)　(Fermat の小定理です)
+ [Japan Alumni Group Summer Camp 2015 Day 4 D Identity Function](https://atcoder.jp/contests/jag2015summer-day4/tasks/icpc2015summer_day4_d)　(Fermat の小定理も、Euler の定理も使います、Euler の定理の部分は離散対数を用いてもよいです)
+ [2017 Tenka1 F ModularPowerEquation!!](https://atcoder.jp/contests/tenka1-2017/tasks/tenka1_2017_f)　(Euler の定理を用いた考察をします、問題の再帰的な構造を見出します)

**【コメント】**
nCr に関わる問題や、中国剰余定理・連立線形合同方程式を用いる問題などです。この辺りの話題についてもよい記事が豊富にあるので紹介します:

+ [数え上げテクニック集](https://drive.google.com/file/d/1WC7Y2Ni-8elttUgorfbix9tO1fvYN3g3/view)の「14. 二項係数のテクニック」 (DEGwer さん)
+ [nCr mod mの求め方](https://www37.atwiki.jp/uwicoder/pages/2118.html) (uwi さん)
+ [整数テクニック集](https://github.com/kirika-comp/articles/blob/pre-releases/pre-seisuuron.pdf) (kirika さん)
+ [競技プログラミングにおける数学的問題まとめ](http://hamayanhamayan.hatenablog.jp/entry/2017/10/14/125941) (はまやんさん)
+ [競技プログラミングにおける中国剰余定理問題まとめ](http://hamayanhamayan.hatenablog.jp/entry/2017/10/14/125941) (はまやんさん)

-----

-----
####**例題 4-1-3　包除原理**
**【キーワード】**

+ 数え上げ
+ 包除原理

**【AtCoder 上の類題】**

+ [ABC 066 D 11](https://atcoder.jp/contests/arc077/tasks/arc077_b)　(包除原理の最も簡単な場合、すなわち**ダブルカウントを除く**問題です)
+ [ABC 003 D AtCoder社の冬](https://atcoder.jp/contests/abc003/tasks/abc003_4)　(包除原理の練習によさそうです)
+ [yukicoder No.0391 CODING WAR](https://yukicoder.me/problems/no/391)　(**スターリング数**です)
+ [ARC 096 E Everything on It](https://beta.atcoder.jp/contests/arc096/tasks/arc096_c)　(スターリング数も登場します、包除原理の芸術です)
+ [Codeforces 198 DIV1 C Iahub and Permutations](http://codeforces.com/problemset/problem/340/E)　(**撹乱順列**の面白い問題です)
+ [天下一 2013 決勝 D 天下一ボディービルコンテスト](https://atcoder.jp/contests/tenka1-2013-final/tasks/tenka1_2013_final_d)　(**包除原理 + DP** です)
+ [AOJ 2136 Webby Subway](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2136)　(**彩色数**です)

**【コメント】**
包除原理を用いる問題です。典型的なものとしては「第二種スターリング数の導出」や「撹乱順列数え上げ」などがあります。少し難しくなると DP が絡むイメージがあります。他に高度な話題としては、彩色数や高速ゼータ変換などがあります。

参考記事:

+ [数え上げテクニック集](https://drive.google.com/file/d/1WC7Y2Ni-8elttUgorfbix9tO1fvYN3g3/view)の「15. 包除原理」 (DEGwer さん)
+ [包除原理 - 解ける数え上げの範囲を広げよう -](https://t.co/YOSVg3vv8U)　(tsutaj さん)
+ [競技プログラミングにおける包除原理問題まとめ](http://hamayanhamayan.hatenablog.jp/entry/2017/04/17/161345) (はまやんさん)

-----

-----
####**例題 4-1-4　周期的でない文字列の数え上げ**
**【キーワード】**

+ 数え上げ
+ 包除原理
+ 約数系包除 (DEGwer さんの[数え上げテクニック集](https://drive.google.com/file/d/1WC7Y2Ni-8elttUgorfbix9tO1fvYN3g3/view)より)

**【AtCoder 上の類題】**

+ [ABC 020 D LCM Rush](https://atcoder.jp/contests/abc020/tasks/abc020_d)　(比較的易しめの**約数系包除**です)
+ [ARC 064 F Rotated Palindromes](https://atcoder.jp/contests/arc064/tasks/arc064_d)
+ [SRM 305 DIV1 Hard PowerCollector](SRM 305 DIV1 Hard PowerCollector)
+ [SRM 626 DIV1 Hard ReflectiveRectangle](https://community.topcoder.com/stat?c=problem_statement&pm=13217&rd=15859)

**【コメント】**
包除原理のうち、特に約数に関係するものです。メビウス関数が登場するイメージがあります。蟻本や DEGwer さんの数え上げテクニック集に詳しい記載があります。

-----


-----
####**例題 4-1-5　石の塗り方の数え上げ**
**【キーワード】**

+ ポリアの数え上げ定理
+ 部分群のテクニック (DEGwer さんの[数え上げテクニック集](https://drive.google.com/file/d/1WC7Y2Ni-8elttUgorfbix9tO1fvYN3g3/view)より)

**【AtCoder 上の類題】**

+ [CODE FESTIVAL 2016 Final I Reverse Grid](https://atcoder.jp/contests/cf16-final-open/tasks/codefestival_2016_final_i)
+ [AGC 006 E Rotate 3x3](https://atcoder.jp/contests/agc006/tasks/agc006_e)
+ [KUPC 2016 J 色塗り](https://atcoder.jp/contests/kupc2016/tasks/kupc2016_j)

**【コメント】**
「ちょうど k 個分ずつ出て来る」みたいなことを利用する問題です。DEGwer さんの pdf のように「部分群のテクニック」と広くとらえるのはすごく面白いと思いました。

-----




## 4-2 ゲームの必勝法を編み出せ！

-----
####**例題 4-2-1　コインのゲーム１**
**【キーワード】**

+ DP
+ ゲーム
+ ゲーム DP

**【AtCoder 上の類題】**

+ [TDPC B ゲーム](https://atcoder.jp/contests/tdpc/tasks/tdpc_game)　(初級編でも挙げました)
+ [ABC 025 C 双子と○×ゲーム](https://atcoder.jp/contests/abc025/tasks/abc025_c)　(ゲーム DP)
+ [ARC 038 B マス目と駒](https://atcoder.jp/contests/arc038/tasks/arc038_b)　(ゲーム DP)
+ [ARC 085 D ABS](https://atcoder.jp/contests/arc085/tasks/arc085_b)　(実は O(1) で解けますが、条件反射でゲーム DP を書けるとすぐに解けます)
+ [AOJ 2376 DisconnectedGame](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2376&lang=jp)　(面白いです)
+ [ARC 038 D 有向グラフと数](https://atcoder.jp/contests/arc038/tasks/arc038_d)　(状態がループするので**後退解析**します)
+ [AOJ 1377 Black and White Boxes](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1377)　(去年の ICPC Asia で出題されて話題になった **Hackenbush** です)
+ [AGC 010 F Tree Game](https://atcoder.jp/contests/agc010/tasks/agc010_f)　(E 問題に比べれば多少考えやすい気がします)

**【コメント】**
ゲームに関する DP です。難しい問題でなければ**ゲーム木探索**を理解していれば簡単です。

参考資料

+ [ゲームを解く！Educational DP Contest K, L 問題の解説](https://qiita.com/drken/items/4e1bcf8413af16cb62da)
+ [ACM-ICPC 2016 Asia Tsukuba Regional, K 解法](http://natsugiri.hatenablog.com/entry/2016/10/23/234716) (natsugiri さん)

-----

-----
####**例題 4-2-2　[A Funny Game (POJ No.2484)](http://poj.org/problem?id=2484)**
**【キーワード】**

+ ゲーム
+ 簡単な表式で解けるゲーム
+ 対称戦略 (相手のマネをする)

**【AtCoder 上の類題】**

+ [AGC 020 A Move and Win](https://atcoder.jp/contests/agc020/tasks/agc020_a)　(AtCoder では頻出の**パリティ**に関するよい例題です)
+ [ABC 059 D Alice&Brown](https://atcoder.jp/contests/arc072/tasks/arc072_b)　(実験をすると見えて来ます)
+ [AGC 014 D Black and White Tree](https://atcoder.jp/contests/agc014/tasks/agc014_d)　(面白いです)
+ [AGC 002 E Candy Piles](https://atcoder.jp/contests/agc002/tasks/agc002_e)　(どこに挙げるか迷いました、最終的にはシンプルな判定法になります)

**【コメント】**
explicit に解けるタイプのゲームです。A Funny Game はひたすら相手のマネをする戦略をとるのがよいゲームでした。必勝法が簡単な表式で表せるタイプのゲームでは、このような対称戦略を考えることは頻出のイメージです。ここでは数学的考察によって必勝法がシンプルに言い表せるタイプの問題を集めました。

-----

-----
####**例題 4-2-3　[Euclid's Game (POJ No.2348)](http://poj.org/problem?id=2348)**
**【キーワード】**

+ ゲーム
+ 自由度の観点から選べる手が実質的に高々 2 通りしかない

**【AtCoder 上の類題】**

+ [ARC 085 D ABS](https://atcoder.jp/contests/arc085/tasks/arc085_b)　(ゲーム DP でも挙げた問題ですが、O(1) で解けます、問題の構造は Euclid's Game によく似ています)
+ [AGC 010 D Decrementing](https://atcoder.jp/contests/agc010/tasks/agc010_d)　(難しめですが、結局選べる手が高々 2 通りしかないゲームです)

**【コメント】**
一見探索領域が広くてメモ化もできなくて難しそうですが、実質的に選べる手が高々 2 通りしかないタイプのゲームです。

-----

-----
####**例題 4-2-4　Nim**
**【キーワード】**

+ ゲーム
+ Nim

**【AtCoder 上の類題】**

+ [ARC 013 C 笑いをとれるかな？](https://atcoder.jp/contests/arc013/tasks/arc013_3)　(Nim の例題です)
+ [yukicoder No.002 素因数ゲーム](https://yukicoder.me/problems/no/2)　(Nim)
+ [yukicoder No.524 コインゲーム](https://yukicoder.me/problems/no/524)　(Nim)
+ [HackerRank Misère Nim](https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/misere-nim)　(**Misere Nim** です)
+ [Japan Alumni Group Spring Contest 2014 J Unfair Game](https://atcoder.jp/contests/JAG2014Spring/tasks/icpc2014spring_j)　(Nim の場合分けゲーです)

**【コメント】**
すごく有名な問題 Nim です。なお最後に石を取ると負けとしたバージョンを Misere Nim と呼ぶようです。

+ [Nim](http://sigma425.hatenablog.com/entry/2014/12/07/132702) (sigma さん)
 
-----

-----
####**例題 4-2-5　[Georgia and Bob (POJ No.1704)](http://poj.org/problem?id=1704)**
**【キーワード】**

+ Nim
+ 時々見るタイプの Nim

**【AtCoder 上の類題】**

+ [SRM 309 DIV1 Hard StoneGameStrategist](https://community.topcoder.com/stat?c=problem_statement&pm=6239&rd=9989)　(見た目違いますが Georgia and Bob と同じ問題です)
+ [Codeforces 417 DIV2 E Sagheer and Apple Tree](http://codeforces.com/contest/812/problem/E)　(これの列バージョンをずっと前に出題しようと考えていたのですがお蔵入りです)

**【コメント】**
時々このタイプの Nim を見る気がします。類題として挙げた 2 題はどちらも見た目は大分違いますが本質的には **Georgia and Bob と同型**な問題です。

-----

-----
####**例題 4-2-6　コインのゲーム２**
**【キーワード】**

+ ゲーム
+ Nim
+ Grundy 数

**【AtCoder 上の類題】**

+ [yukicoder No.103 素因数ゲーム リターンズ](https://yukicoder.me/problems/no/103)　(Grundy 数を求める例題です)
+ [yukicoder No.102 トランプを奪え](https://yukicoder.me/problems/no/102)　(Grundy 数を求めます)
+ [ARC 038 C 茶碗と豆](https://atcoder.jp/contests/arc038/tasks/arc038_c)　(104 点解法は高速化します)
+ [AGC 017 D Game on Tree](https://atcoder.jp/contests/agc017/tasks/agc017_d)　(頑張って求めます)
+ [AGC 016 F Games on DAG](https://atcoder.jp/contests/agc016/tasks/agc016_f)　(難しいです)

**【コメント】**
複数盤面を同時に処理するゲームに使える一般的なテク Grundy です！

-----

-----
####**例題 4-2-7　[Cutting Game (POJ No.2311)](http://poj.org/problem?id=2311)**
**【キーワード】**

+ ゲーム
+ Nim
+ Grundy 数
+ 分裂のある Grundy 数

**【AtCoder 上の類題】**

+ [yukicoder No.361 門松ゲーム2](https://yukicoder.me/problems/no/361)　(比較的 Cutting Game に近いです)
+ [yukicoder 0153 石の山](https://yukicoder.me/problems/13)　(分裂のある Grundy 数のいい感じの例題です)
+ [ARC 087 E Prefix-free Game](https://atcoder.jp/contests/arc087/tasks/arc087_c)　(超良問だと思います)

**【コメント】**
Grundy 数は盤面の**分裂**がある場合に真価を発揮するイメージです！

-----

ゲーム全般の問題集です。またゲーム系問題への入門として、HackerRank によい教材があるようです:

+ [HackerRank Game Theory の勧め](http://hamayanhamayan.hatenablog.jp/entry/2017/03/10/150817) (はまやんさん)
+ [競技プログラミングにおけるゲーム問題まとめ (Nim,Grundy数,後退解析)](http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/025050) (はまやんさん)



## 4-3 グラフマスターへの道

-----
####**例題 4-3-1　[Popular Cows (POJ No.2186)](http://poj.org/problem?id=2186)**
**【キーワード】**

+ 強連結成分分解

**【AtCoder 上の類題】**

+ [JOI 2006 本選 D 最悪の記者](https://atcoder.jp/contests/joi2007ho/tasks/joi2007ho_d)　(DAG の**トポロジカルソート**です、[AOJ 0519](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0519) に同じ)
+ [AOJ Course Strongly Connected Components](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C&lang=jp)　(強連結成分分解の verify に)
+ [TDPC R グラフ](https://atcoder.jp/contests/tdpc/tasks/tdpc_graph)　(強連結成分分解して DP します。フローでも解けるので例題 3-5-9 でも挙げました)
+ [SRM 608 DIV1 Medium BigO](SRM 608 DIV1 Medium BigO)　(SRM の問題ですがとても面白いです)

**【コメント】**
有向グラフに強連結成分分解を行い、強連結成分を 1 点につぶすと DAG になります。DAG 上で DP したりなど、色んな問題が出題されます。

-----

-----
####**例題 4-3-2　[Priest John's Busiest Day (POJ No.3683)](http://poj.org/problem?id=3683)**
**【キーワード】**

+ 強連結成分分解
+ 2-SAT

**【AtCoder 上の類題】**

+ [yukicoder No.274 The Wall](https://yukicoder.me/problems/no/274)　(2-SAT を試すよい例題です)
+ [yukicoder No.470 Inverse S+T Problem](https://yukicoder.me/problems/no/470)　(2-SAT です)
+ [ARC 069 F Flags](https://atcoder.jp/contests/arc069/tasks/arc069_d)　(2-SAT です)

**【コメント】**
強連結成分分解を用いる典型例として 2-SAT があります。2-SAT 制約は **Project Selection Problem (燃やす埋める)** とも相性がよいです。

参考記事:

+ [競技プログラミングにおける有向グラフに関する問題まとめ (強連結成分分解, 最小パス被覆, Dilworthの定理, トポロジカルソート)](http://hamayanhamayan.hatenablog.jp/entry/2017/06/11/124732) (はまやんさん)
+ [競技プログラミングにおける2-SAT問題まとめ](http://hamayanhamayan.hatenablog.jp/entry/2017/02/19/024517) (はまやんさん)

-----

-----
####**例題 4-3-3　[Housewife Wind (POJ No.2763)](http://poj.org/problem?id=2763)**
**【キーワード】**

+ ツリー上のクエリ
+ LCA
+ Euler Tour
+ ダブリング

**【AtCoder 上の類題】**

+ [ABC 014 D 閉路](https://atcoder.jp/contests/abc014/tasks/abc014_4)　(LCA を試すよい例題です)
+ [KUPC 2015 J MODクエリ](https://atcoder.jp/contests/kupc2015/tasks/kupc2015_j)　(LCA 関連のダブリングをするか、HL 分解をします)
+ [JOI 2011 本選 E JOI 国のお祭り事情](https://atcoder.jp/contests/joi2012ho/tasks/joi2012ho5)　(色んな解法が考えられます, [AOJ 0575](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0575) に同じ)
+ [天下一プログラマーコンテスト2015 本戦 F 根付き木のみさわさん](https://atcoder.jp/contests/tenka1-2015-final/tasks/tenka1_2015_final_f)　(Euler Tour)
+ [NJPC 2017 H 白黒ツリー](https://atcoder.jp/contests/njpc2017/tasks/njpc2017_h)　(Euler Tour)
+ [UTPC 2013 I 支配と友好](https://atcoder.jp/contests/utpc2013/tasks/utpc2013_09)　(Euler Tour)
+ [square869120Contest #5 H Percepts of Atcoder](https://atcoder.jp/contests/s8pc-5/tasks/s8pc_5_h)　(ダブリングをします、HL分解的な発想に基づいているようです)
+ [JOI 2015 春合宿 day2-3 道路整備](https://atcoder.jp/contests/joisc2015/tasks/joisc2015_g)　(色んなアルゴリズムを総動員します、二重辺連結成分分解も、問題は[ここ](https://www.ioi-jp.org/camp/2015/2015-sp-tasks/2015-sp-d2.pdf))
+ [JOI 2017 春合宿 day2-3 鉄道旅行](https://atcoder.jp/contests/joisc2017/tasks/joisc2017_f)　(最後に LCA のようなものを求めるダブリングに近いことをします、問題は[ここ](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d2-railway_trip-review.pdf))

**【コメント】**
ツリー上のクエリに関する問題です。典型的にはダブリング、オイラーツアーから、少しよく見るものに **HL 分解**などがあります。

参考記事:

+ [完全制覇・ツリー上でのクエリ処理技法](https://topcoder.g.hatena.ne.jp/iwiwi/20111205/1323099376) (iwi さん)
+ [Heavy-Light Decomposition](http://beet-aizu.hatenablog.com/entry/2017/12/12/235950) (beet さん)
+ [競技プログラミングにおけるLCA問題まとめ](http://hamayanhamayan.hatenablog.jp/entry/2017/05/03/131624) (はまやんさん)
+ [競技プログラミングにおけるオイラーツアー問題まとめ](http://hamayanhamayan.hatenablog.jp/entry/2017/04/10/163548) (はまやんさん)
+ [競技プログラミングにおけるHL分解まとめ](http://hamayanhamayan.hatenablog.jp/entry/2017/04/10/172636) (はまやんさん)

-----





## 4-4 厳選！頻出テクニック (2)

-----
####**例題 4-4-1　[Largest Rectangle in a Histogram (POJ No.2559)](http://poj.org/problem?id=2559)**
**【キーワード】**

+ ヒストグラム長方形面積最大化
+ stack

**【AtCoder 上の類題】**

+ [KUPC 2013 D カーペット](https://atcoder.jp/contests/kupc2013/tasks/kupc2013_d)　(ほぼそのものな問題です)
+ [ARC 081 F Flip and Rectangles](https://atcoder.jp/contests/arc081/tasks/arc081_d)　(ヒストグラム長方形面積最大化に帰着されます)
+ [ABC 064 D Insertion](https://atcoder.jp/contests/abc064/tasks/abc064_d)　(**括弧列**に関する例題です)
+ [ARC 076 E Connected?](https://atcoder.jp/contests/arc076/tasks/arc076_c)　(見た目違いますが結局、括弧列の問題になります)

**【コメント】**
ナイーブにやると O(n^2) かかる処理を stack を用いて O(n) で済ませるテクニックです。類似の話題として[最大正方形の面積 - 正方形探索](http://algorithms.blog55.fc2.com/blog-entry-131.html)もあります。他に stack を用いて実施できる典型的な問題として**括弧列**に関する問題があります。

-----

-----
####**例題 4-4-2　スライド最小値**
**【キーワード】**

+ スライド最小値
+ deque

**【AtCoder 上の類題】**

+ [ARC 077 C pushpush](https://atcoder.jp/contests/arc077/tasks/arc077_a)　(deque が使える問題です)
+ [ARC 005 C 器物損壊！高橋君](https://atcoder.jp/contests/arc005/tasks/arc005_3)　(0-1 BFS に deque が使えます、2 つの queue を用いてもよいです)

**【コメント】**
DP の高速化テクニックとしてよく見るスライド最小値技法です。スライド最小値そのものの問題は見つからなかったですが、ここでは deque が使えそうな問題を挙げます。

-----

-----
####**例題 4-4-3　個数制約付きナップサック**
**【キーワード】**

+ DP
+ deque
+ スライド最小値を用いた DP 高速化

**【AtCoder 上の類題】**

+ [CODE FESTIVAL 2016 Tournament Round 3 A ストラックアウト](https://atcoder.jp/contests/cf16-tournament-round3-open/tasks/asaporo_d)
+ [JOI 2014 予選 F 財宝](https://atcoder.jp/contests/joi2015yo/tasks/joi2015yo_f)　([AOJ 0613](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0613) に同じ)
+ [COLOCON Colopl programming contest 2018 D すぬけそだて――トレーニング――](https://atcoder.jp/contests/colopl2018-qual/tasks/colopl2018_qual_d)　(より単純な解法も)
+ [JOI 2009 本選 E ダンジョン](https://atcoder.jp/contests/joi2010ho/tasks/joi2010ho_e)　(deque を使う O(n) 解法があるようです、[AOJ 0553](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0553) に同じ)
+ [treeone カット問題](https://twitter.com/ei1333/status/952921366570844161): おまけに

**【コメント】**
DP 高速化技法としてよく見られる手法の 1 つ、スライド最小値 (他に累積和, インライン DP, Convex Hull Trick など) です。多くの場合、segtree を用いた高速化もできますが、スライド最小値が決まると segtree 高速化よりも計算量オーダーを落とせます。

-----

-----
####**例題 4-4-4　[K-Anonymous Sequence (POJ No.3709)](http://poj.org/problem?id=3709)**
**【キーワード】**

+ DP
+ Convex Hull Trick を用いた DP 高速化

**【AtCoder 上の類題】**

+ [COLOCON -Colopl programming contest 2018 Final C スペースエクスプローラー高橋君](https://atcoder.jp/contests/colopl2018-final/tasks/colopl2018_final_c)　(DP 高速化ではないですが CHT のシンプルな例題です)
+ [yukicoder No.409 ダイエット](https://yukicoder.me/problems/no/409)
+ [Japan Alumni Group Summer Camp 2015 Day 4 I  Live Programming](https://atcoder.jp/contests/jag2015summer-day4/tasks/icpc2015summer_day4_i)　(実はダイエットとほぼ同じです)
+ [JOI 2017 春合宿 day3-1 長距離バス](https://atcoder.jp/contests/joisc2017/tasks/joisc2017_g)　(問題は[ここ](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d3-coach-review.pdf))
+ [ARC 066 F Contest with Drinks Hard](https://atcoder.jp/contests/arc066/tasks/arc066_d)　(分割統治法も絡みます)

**【コメント】**
DP 高速化技法としてよく見られる手法の 1 つ、Convex Hull Trick です。
DP 高速化関連記事:

+ [DP高速化](http://ferin-tech.hatenablog.com/entry/2018/02/23/071343) (フェリンさん)
+ [Convex-Hull Trick](http://satanic0258.hatenablog.com/entry/2016/08/16/181331) (satanic さん)
+ [難しい典型テクとか](https://www.slideshare.net/ikumihide/ss-50881829) (とざんさん)
+ [数え上げテクニック集](https://drive.google.com/file/d/1WC7Y2Ni-8elttUgorfbix9tO1fvYN3g3/view)の「11. 高速化のテクニック」 (DEGwer さん)
+ [動的計画法高速化テクニック（オフライン・オンライン変換）](https://qiita.com/tmaehara/items/0687af2cfb807cde7860) (前原さん)
+ [競技プログラミングにおける動的計画法更新最適化まとめ（CHT, MongeDP, AlianDP, インラインDP, きたまさ法）](http://hamayanhamayan.hatenablog.jp/entry/2017/03/20/234711) (はまやんさん)

-----

-----
####**例題 4-4-5　巡回スケジューリング**
**【キーワード】**

+ ダブリング

**【AtCoder 上の類題】**

+ [ABC 013 D 阿弥陀](https://atcoder.jp/contests/abc013/tasks/abc013_4)　(感覚を掴むのにいい感じの問題です)
+ [ARC 060 E 高橋君とホテル](https://atcoder.jp/contests/arc060/tasks/arc060_c)　(いい感じです)
+ [UTPC 2012 H 区間スケジューリングクエリ](https://atcoder.jp/contests/utpc2012/tasks/utpc2012_08)　(面白いです)
+ [JAG Practice Contest for ACM-ICPC Asia Regional 2015 E Shifting a Matrix](https://atcoder.jp/contests/jag2015autumn/tasks/icpc2015autumn_e)　(英語ですがいい感じです)

**【コメント】**
べき乗法、行列累乗、LCA などでもおなじみのダブリングを用いた DP です。
参考記事:

+ [ダブリング](http://satanic0258.hatenablog.com/entry/2017/02/23/222647) (satanic さん)

-----





## 4-5 工夫を凝らして賢く探索

-----
####**例題 4-5-1　数独 (POJ 2676, 2918, 3074, 3076)**
**【キーワード】**

* 探索
+ 探索順序を工夫する
+ バックトラック

**【AtCoder 上の類題】**

+ [UTPC 2013 E 2-SAT](https://atcoder.jp/contests/utpc2013/tasks/utpc2013_05)　(実は素直な探索で解けて、計算量の見積りが本質です)
+ [JOI 2008 予選 D 薄氷渡り](https://atcoder.jp/contests/joi2009yo/tasks/joi2009yo_d)　(見積もり大事です、[AOJ 0535](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0535) に同じ)
+ [JOI 2009 予選 F 方向音痴のトナカイ](https://atcoder.jp/contests/joi2010yo/tasks/joi2010yo_f)　(後ろから解くと速いです、[AOJ 0548](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0548) に同じ)
+ [AOJ 2026 Divisor is the Conqueror](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2026)　(同じく後ろから解くと速いバックトラックです)
+ [AOJ 2443 ReverseSort](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2443)　(前と後ろの両方から攻める**両側探索**と呼ばれているものです)
+ [AOJ 0091 Blur](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0091)　(AOJ Volume 0 で最難と有名です、integrality がよくわからないですが**単体法**でも通りました、ということはもしかしたらフロー解があるのかもです)

**【コメント】**
基本的には DFS などによる全探索ですが、全探索方法があまり自明でないタイプの問題です。DFS ではしばしば「前の状態に戻す」といことをするので、そこをいかに高速に実現するかが大事になることもあります (そこを強く意識した DFS を**バックトラック**と言います)。

-----

-----
####**例題 4-5-2　[Sequence Destroyer (POJ No.1084)](http://poj.org/problem?id=1084)**
**【キーワード】**

+ 探索
+ 枝刈り探索
+ 解が悪くなったら打ち切る
+ 分枝限定法やα-β法的な枝刈り探索

**【AtCoder 上の類題】**

+ [KUPC 2016 F 早解き](https://atcoder.jp/contests/kupc2016/tasks/kupc2016_f)　(α-β 的なことをします)
+ [Japan Alumni Group Summer Camp 2013 Day 4 E Optimal alpha beta pruning ](https://atcoder.jp/contests/jag2013summer-day4/tasks/icpc2013summer_day4_e)　(α-β します)
+ [ABC 032 D ナップサック問題](https://atcoder.jp/contests/abc032/tasks/abc032_d)　(DP や半分全列挙で解きますが[分枝限定法でまとめて解く](https://qiita.com/hamko/items/cceb1a92da14e2755527)こともできます)
+ [AOJ 1131 Unit Fraction Partition](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1131&lang=jp)　(枝刈りをすると通る系です)
+ [JAG Practice Contest for ACM-ICPC Asia Regional 2013 J Magical Switches](https://atcoder.jp/contests/jag2013autumn/tasks/icpc2013autumn_j)　(枝刈り探索しますが計算時間の指数の底を評価できたりして面白いです)

**【コメント】**
分枝限定法やα-β法に代表されるような、「解が悪くなったら打ち切る」系の枝刈り探索をする問題です。計算量オーダーが不明になることが多く出題側も苦心しそうなタイプの問題です。ここではもっと広く枝刈り探索に関する問題を載せました。
参考記事:

+ [競技プログラミングにおける枝刈り問題まとめ](http://hamayanhamayan.hatenablog.jp/entry/2017/12/23/155922) (はまやんさん)

-----

-----
####**例題 3-5-3　AとIDA**
**【キーワード】**

+ A*とIDA*

**【AtCoder 上の類題】**

+ [UTPC 2013 J K番目の閉路](https://atcoder.jp/contests/utpc2013/tasks/utpc2013_10)　(A*が本質的に計算量を改善する問題で面白いです)

**【コメント】**
A* や IDA* によって DFS や BFS を高速化します。

-----






## 4-6 分けて解いてまとめる！ "分割統治法"

-----
####**例題 4-6-1　バブルソートの交換回数**
**【キーワード】**

+ 分割統治法

**【AtCoder 上の類題】**

+ [AOJ Course The Number of Inversions](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D&lang=jp)　(バブルソートの交換回数そのものです)
+ [UTPC 2012 I 最短路クエリ](https://atcoder.jp/contests/utpc2012/tasks/utpc2012_09)　(面白いです)
+ [ARC 066 F Contest with Drinks Hard](https://atcoder.jp/contests/arc066/tasks/arc066_d)　(Convex Hull Trick も絡みます、難しめです)
+ [JOI 2017 春合宿 day1-2 港湾設備](https://atcoder.jp/contests/joisc2017/tasks/joisc2017_b)　(二部グラフ判定を頑張って高速化します)

**【コメント】**
なんとなく Segtree を使ってもできることが多そうなイメージもある分割統治法です。

+ [競技プログラミングにおける分割統治法問題まとめ](http://hamayanhamayan.hatenablog.jp/entry/2017/05/21/234616) (はまやんさん)

-----

-----
####**例題 4-6-2　[Tree (POJ No.1741)](http://poj.org/problem?id=1741)**
**【キーワード】**

+ 分割統治法
+ ツリーの重心
+ ツリーの重心分解

**【AtCoder 上の類題】**

+ [ARC 087 F Squirrel Migration](https://atcoder.jp/contests/arc087/tasks/arc087_d)　(ツリーの重心に関する数学的問題、包除原理も使います)
+ [2018 第4回ドワンゴからの挑戦状 予選 E ニワンゴくんの家探し](https://atcoder.jp/contests/dwacon2018-prelims/tasks/dwacon2018_prelims_e)　(ツリーの重心分解)
+ [DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 D 道路網](https://atcoder.jp/contests/ddcc2016-qual/tasks/ddcc_2016_qual_d)　(重心分解)
+ [AOJ 2559 Minimum Spanning Tree](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2559)　(マージテクや重心分解の典型的良問です)
+ [AOJ 1330 Never Wait for Weights](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1330)　(データ構造をマージする一般的なテク)
+ [AGC E Blue and Red Tree](https://atcoder.jp/contests/agc014/tasks/agc014_e)　(マージテク)
+ [UTPC 2014 I 盆栽](https://atcoder.jp/contests/utpc2014/tasks/utpc2014_i)　(マージテク)
+ [JOI 2012 春合宿 day1-1 ビルの飾り付け 2](https://atcoder.jp/contests/joisc2012/tasks/joisc2012_building2)　(マージテク発祥の問題です、問題は[ここ](https://www.ioi-jp.org/camp/2012/2012-sp-tasks/2012-sp-day1-building2-slides.pdf))

**【コメント】**
ツリーの重心分解を用いたツリー上の分割統治法です。**データ構造をマージする一般的なテク**で解けるケースも多いイメージがあります。また、ツリーの重心の数学的性質を活用するタイプの問題も挙げました。
参考記事:

+ [ツリーの重心分解 (木の重心分解) の図解](https://qiita.com/drken/items/4b4c3f1824339b090202)
+ ["データ構造をマージする一般的なテク" とは？](https://topcoder.g.hatena.ne.jp/iwiwi/20131226/1388062106) (iwi さん)
+ [やぶについて書きます](https://camypaper.bitbucket.io/2016/12/18/adc2016/) (紙ペーパーさん)
+ [競技プログラミングにおける重心分解問題まとめ](http://hamayanhamayan.hatenablog.jp/entry/2017/12/19/152143) (はまやんさん)
+ [競技プログラミングにおけるマージテク問題まとめ](http://hamayanhamayan.hatenablog.jp/entry/2017/02/10/132728) (はまやんさん)

-----

-----
####**例題 4-6-3　[最近点対問題 (Uva 10245)](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1186)**
**【キーワード】**

+ 分割統治法
+ 平面の分割統治法
+ 最近点対問題

**【AtCoder 上の類題】**

+ [AOJ 0585 Nearest Two Points](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0585)　(最近点対問題そのものです)
+ [AOJ 2057 The Closest Circle](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2057)　(最近円対問題です)
+ [AOJ 1340 Directional Resemblance](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1340)　(三次元になって難しいです)

**【コメント】**
最近点対問題です。

+ [競技プログラミングにおける最近点対問題まとめ](http://hamayanhamayan.hatenablog.jp/entry/2018/01/10/163818) (はまやんさん)

-----







## 4-7 文字列を華麗に扱う

-----
####**例題 4-7-1　禁止文字列　＜募集中！！！＞**
**【キーワード】**

+ 文字列 DP

**【AtCoder 上の類題】**

+ [Codeforces 201 DIV1 B Lucky Common Subsequence](http://codeforces.com/contest/346/problem/B)　(例題よりやや難しいですが比較的近いです)
+ [SRM 412 DIV1 Easy ForbiddenStrings](https://chaingng.github.io/post/srm-412-div1-easy---forbiddenstrings-/)　(割と例題に近いです)
+ [SRM 557 DIV2 Hard FoxAndMountain](https://community.topcoder.com/stat?c=problem_statement&pm=11810&rd=15179)　(見た目違いますが結構例題に近いです)

**【コメント】**
Trie DP の前振りです。ごく自然な DP で解くことができます。競プロの問題としては、通常は複数文字列を禁止パターンとして Trie DP の形で出すものと思われるため、類題はあまり見つからなかったです。AtCoder 上の問題を募集中です。

-----

-----
####**例題 4-7-2　[DNA Repair (POJ No.3691)](http://poj.org/problem?id=3691)**
**【キーワード】**

+ 文字列 DP
+ Trie 木

**【AtCoder 上の類題】**

+ [天下一プログラマーコンテスト2016本戦 C たんごたくさん](https://atcoder.jp/contests/tenka1-2016-final/tasks/tenka1_2016_final_c)　(比較的近いです)
+ [UTPC 2014 E 宝くじ](https://atcoder.jp/contests/utpc2014/tasks/utpc2014_e)　(Trie 木上のツリー DP です)
+ [ARC 087 E Prefix-free Game](https://atcoder.jp/contests/arc087/tasks/arc087_c)　(Grundy 数との組み合わせ)
+ [CODE FESTIVAL 2016 Qual B E Lexicographical disorder](https://atcoder.jp/contests/code-festival-2016-qualb/tasks/codefestival_2016_qualB_e)　(少し難しめです)

**【コメント】**
例題 4-7-1 から少し発展して Trie 木を構築するタイプの問題です。

-----

-----
####**例題 4-7-3　[星座 (POJ No.3690)](http://poj.org/problem?id=3690)**
**【キーワード】**

+ 文字列検索
+ ローリングハッシュ
+ KMP 法
+ Aho-Corasick 法

**【AtCoder 上の類題】**

+ [yukicoder No.430 文字列検索](https://yukicoder.me/problems/no/430)　(**ロリハ**でも、**Trie** でも、**Aho-Corasick** でもできます、ライブラリ整備に)
+ [yukicoder No.599 回文かい](https://yukicoder.me/problems/no/599)　(ロリハ)
+ [AOJ 2808 パスワード](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2808)　(ロリハ)
+ [JOI 2010 春合宿 day2-2 DNA synthesizer](https://atcoder.jp/contests/joisc2010/tasks/joisc2010_dna)　(Trie や Aho-Corasick で解きます, 問題は[ここ](https://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day2_21.pdf))
+ [Japan Alumni Group Summer Camp 2015 Day 2 F ほぼ周期文字列](https://atcoder.jp/contests/jag2015summer-day2/tasks/icpc2015summer_day2_f)　(ロリハが楽なようです)
+ [AOJ 2257 桜詩 願はくは花の下にて春死なむ](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2257)　(Aho-Corasick)
+ [JAG Practice Contest for ACM-ICPC Asia Regional 2017 H Separate String](https://atcoder.jp/contests/jag2017autumn/tasks/jag2017autumn_h)　(Aho-Corasick)

**【コメント】**
文字列検索関連です。

+ [競技プログラミングにおけるハッシュ問題まとめ](http://hamayanhamayan.hatenablog.jp/entry/2017/05/24/154618) (はまやんさん)
+ [ハッシュを衝突させる話](http://hos.ac/blog/#blog0003) (hos さん)

-----

-----
####**例題 4-7-4　[Sequence (POJ No.3581)](http://poj.org/problem?id=3581)**
**【キーワード】**

+ Suffix Array

**【AtCoder 上の類題】**

+ [SPOJ SARRAY Suffix Array](http://www.spoj.com/problems/SARRAY/)　(高速な SA ライブラリの verify に。昔は SA-IS でないと通らなかったようですが現在はもう少し遅い解法でも通るようです。)
+ [DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 C アメージングな文字列は、きみが作る！](https://atcoder.jp/contests/discovery2016-qual/tasks/discovery_2016_qual_c)　(SA 以外のところがむしろメインかもですが、辞書順最小な接尾辞を選ぶ考え方は似通っています)
+ [Japan Alumni Group Summer Camp 2014 Day 4 F Longest Match](https://atcoder.jp/contests/jag2014summer-day4/tasks/icpc2014summer_day4_f)　(SA + segtree です)
+ [CODE FESTIVAL 2016 Elimination Tournament Round 1 B 数字列をカンマで分ける問題](https://atcoder.jp/contests/cf16-tournament-round1-open/tasks/asaporo_f)　(SA + 二分探索です)
+ [RUPC 2018 day H Hth Number](https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp18Day2/problems/H)　(非常に教育的かつ典型的な SA + 二分探索です)

**【コメント】**
Suffix Array です。Suffix Array を求めるアルゴリズムは様々なものが提案されており、特に $O(n)$ で求められる **SA-IS** は理論上も実際上も高速です。

-----

-----
####**例題 4-7-5　[共通部分文字列(POJ No.2217)](http://poj.org/problem?id=2217)**
**【キーワード】**

+ Suffix Array
+ LCP (高さ配列)

**【AtCoder 上の類題】**

+ [square869120Contest #2 E 部分文字列](https://atcoder.jp/contests/s8pc-2/tasks/s8pc_2_e)　(比較的素直な考察で解ける LCP です)
+ [yukicoder No.515 典型LCP](https://yukicoder.me/problems/no/515)　(LCP + segtree)
+ [KUPC 2014 K 弱点](https://atcoder.jp/contests/kupc2014/tasks/kupc2014_k)　(難しめです)

**【コメント】**
Suffix Array とセットになって使われることの多い LCP です。

-----

-----
####**例題 4-7-6　最長回文**
**【キーワード】**

+ Suffix Array
+ LCP
+ 回文

**【AtCoder 上の類題】**

+ [ARC 060 F 最良表現](https://atcoder.jp/contests/arc060/tasks/arc060_d)　(様々な解法があります)
+ [Japan Alumni Group Summer Camp 2013 Day 3 H Almost Same Substring](https://atcoder.jp/contests/jag2013summer-day3/tasks/icpc2013summer_day3_h)　(様々な解法があります)
+ [Japan Alumni Group Summer Camp 2015 Day 2 F ほぼ周期文字列](https://atcoder.jp/contests/jag2015summer-day2/tasks/icpc2015summer_day2_f)　(ロリハでも、SA+LCP でもできます)
+ [ARC 050 D Suffix Concat](https://atcoder.jp/contests/arc050/tasks/arc050_d)　(SA+LCP)

**【コメント】**
LCP にさらに RMQ を用いると文字列の場所 i, j の接尾辞の先頭何文字が共通しているかを求めることができます。最長回文はそのような LCP 処理を用いる典型的な例です。

-----

文字列全般の問題集です:

+ [競技プログラミングにおける文字列アルゴリズム問題まとめ (ローリングハッシュ,Suffix Array,LCP,KMP,Aho-Corasick,Z-algorithm)](http://hamayanhamayan.hatenablog.jp/entry/2017/03/25/005452) (はまやんさん)







## 4-8 GCJ の問題に挑戦してみよう (3)

各 GCJ の問題たちのキーワードを挙げていきます。この中でも 4-8-5 は一時期流行したテクニックを用いるので類題を挙げます。

-----
####**例題 4-8-1　[Mine Layer (2008 World Final C)]()**
**【キーワード】**

+ 端から決まる Greedy

**【AtCoder 上の類題】**


**【コメント】**
最適化問題の顔をしていますが、実は一意に決まってしまう問題です。

-----

-----
####**例題 4-8-2　[Year of More Code Jam (2009 World Final A)]()**
**【キーワード】**

+ 期待値
+ 期待値の線形性

**【AtCoder 上の類題】**

+ [AGC 007 C Pushing Balls](https://atcoder.jp/contests/agc007/tasks/agc007_c)　(期待値計算を頑張ります、kirika さん提供)

**【コメント】**
期待値の式変形をひたすら頑張る問題です。

-----

-----
####**例題 4-8-3　[Football Team (2009 Round 3 C)]()**
**【キーワード】**

+ グラフ
+ 彩色数
+ 二部グラフ判定
+ 平面グラフ
+ 四色定理
+ 三彩色問題

**【AtCoder 上の類題】**


**【コメント】**
グラフの彩色に関する問題です。

-----

-----
####**例題 4-8-4　[Endless Knight (2008 Round3 D)]()**
**【キーワード】**

+ 数え上げ
+ 包除原理
+ 包除原理 + DP

**【AtCoder 上の類題】**

**【コメント】**
包除原理を用いる例題です。今の時代となっては比較的典型の部類に入りそうです。

-----

-----
####**例題 4-8-5　[The Year of Code Jam (2008 World Final E)]()**
**【キーワード】**

+ フロー
+ 最小カット
+ Project Selection Problem (燃やす埋める)
+ 半分だけ変数変換して「燃やす埋める」が使える形にするテク

**【AtCoder 上の類題】**

+ [SRM 558 DIV1 Hard SurroundingGame](https://community.topcoder.com/stat?c=problem_statement&pm=12158)
+ [AOJ 2496 1](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2496)
+ [RUPC 2019 day1-G イルミネーション](https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day1/problems/G)

**【コメント】**
蟻本のラストを飾る問題です！！！
GCJ 2008 World Final で最も正答者数の少なかった難問ですが、この問題が世に知れ渡って以降、典型テクニックとして理解されるようになりました。

+ [最小カットを使って「燃やす埋める問題」を解く](https://www.slideshare.net/shindannin/project-selection-problem) (診断人さん)
+ [LPとグラフと定式化](http://tokoharu.github.io/tokoharupage/docs/formularization.pdf) (とこはるさん)

-----




# 謝辞
蟻本の例題たちを AtCoder の問題に結び付け、さらに類題を加える試みをしてみました。
本記事を執筆するにあたり、たくさんの方に支えていただきました。本記事の企画に賛同していただいた秋葉さん、これほどまでに素敵な蟻本を執筆してくださった iwi さん、wata さん、kita_masa さん、問題案などを提供していただいた yumechi さん、はむこさん、ヘクトさん、きゅうりさん、とこはるさん、くぬーさん、くちもちとくらさん、kirika さん、n_vip さん、E869120 さん、square10011 さん、nadare さん、リンク切れなどのミスを指摘してくれた Moko さん、くちもちとくらさん、好意的なコメントを寄せていただいた TL の皆さん、いつも楽しいコンテストを開催してくださっている AtCoder 社の方々、読んでいただいている読者の皆さん、そして競技プログラミングに関わるすべての方々への感謝の想いでいっぱいです。今後ますますの競技プログラミング界の発展を願って、むすびの言葉とさせていただきます (まだまだ随時更新します)。