競技プログラミングにおける分割統治法問題まとめ

分割統治法

• 「列の分割統治法」、「木の分割統治法」、「平面の分割統治法」
• 色んな分割統治法があるが、大体空間サイズが半分になってlogNくらいで解けるようになる
• 再帰的な定義がなされているやつを再帰的に処理して解決する問題もある
• 列の分割統治法はセグメントツリーでの別解がよくある印象
• 木の分割統治法では「重心分解」が有名

問題

再帰的な関数で表現できる系

• AOJ コッホ曲線
• yukicoder No.493 とても長い数列と文字列(Long Long Sequence and a String） 解説
• SRM714 Div1 Med NAddOdd 解説
• ARC077 SS
• Looksery Cup 2015 F. Yura and Developers 解説
• Codeforces Round #415 (Div. 1) C. Find a car (二次元上)
• ARC066 F. Contest with Drinks Hard 解説 (難)

再帰的な関数で表現できる系(最大値での分割)

• SRM638 div1 Med NarrowPassage2 解説
• CSA Ultimate Orbs
• CF Maximum Reduction
• HR Max Transform （難）

列の分割統治

• AOJ 反転数
• POJ 1854 Evil Straw Warts Live 解説
• POJ 3067 Japan 解説1 解説2
• HR Boxes for Toys
• CSA Borland
• HR Pair Sums （+CHT）
• yukicoder No.913 木の燃やし方 解説 (+CHT)
• ARC006F Contest with Drinks Hard (+CHT)
• yukicoder No.1079 まお

メモ

• http://d.hatena.ne.jp/anta1/20121226/1356512522
• http://d.hatena.ne.jp/anta1/20121218/1355826246
• http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D
• http://poj.org/problem?id=3067
• https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=37&page=show_problem&problem=724
• http://main.edu.pl/en/archive/pa/2011/plo
• https://www.hackerrank.com/contests/101hack50/challenges/boxes-for-toys/problem
• https://csacademy.com/contest/round-35/task/min-max-sum/