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

分割統治法

• 「列の分割統治法」、「木の分割統治法」、「平面の分割統治法」
• 色んな分割統治法があるが、大体空間サイズが半分になって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/

FourLamps [TopCoderOpen 2017 Round2A Div1 Hard]

https://community.topcoder.com/stat?c=problem_statement&pm=14597&rd=16929

問題概要

N個のランプがあり、on/offのどちらかの状態をとる。
最初はinitの状態になっている。
ここから、K回以下の操作を繰り返す時に最終的にランプが取りうる状態数は何通りか。

1. 連続する4つのランプを選ぶが、少なくとも1つがonか少なくとも1つがoffで無ければならない
2. この4つのランプの中心を分割点として、N個のランプ全体を前半・後半の2つに分ける
3. 前半・後半のどちらかを選ぶ
4. 選んだ方を反転させる

DistanceZeroAndOne [TopCoderOpen 2017 Round2A Div1 Med]

https://community.topcoder.com/stat?c=problem_statement&pm=14596

問題概要

N頂点の連結な無向グラフがある。
これについて、頂点0から各頂点への距離dist0と頂点1から各頂点への距離dist1が分かっている。
2つの距離が満たされる無向グラフがあれば復元せよ。

FoxAndCake2 [TopCoderOpen 2017 Round2A Div1 Easy]

https://community.topcoder.com/stat?c=problem_statement&pm=14609&rd=16929

問題概要

チェリーがC個、いちごがS個ある。
これを以下のルールでグルーピングする。

• 全てのチェリーといちごが何処かのグループに入る
• 何グループに分けてもいい
• 各グループ1つはチェリーといちごがそれぞれある
• 各グループのチェリーといちごの数は互いに素になってはいけない

全て満たすように分割可能か

競技プログラミングにおける中国剰余定理問題まとめ

中国剰余定理

• 中国風剰余問題、中国人剰余問題、CRT : Chinese Remainder Theorem
• 表記ゆらぎがむっちゃあるのでCRTで統一した方がいいんじゃないかと思ってる
• 解説
• 解ける問題

ある数m1,m2,...,mnとある数a1,a2,...,anがあり、
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
…
x ≡ an (mod mn)
であることが分かっている時、これを満たすx(mod m1*m2*...*mn)を導出する

• 素数でないmod計算をこれを使って解くテクがある これの発展的話題はこのテクを使っている

問題

• yukicoder No.186 中華風(Easy)
• yukicoder No.187 中華風(Hard) (LCM mod pも要求される その実装はこの提出を見るとなんとなく分かるかと思います)
• AC チップ・ストーリー　～黄金編～
• yukicoder No.261 ぐるぐるぐるぐる！あみだくじ！
• CF460 Congruence Equation 解説

競技プログラミングにおける永続データ構造問題まとめ

永続データ構造

• persistent data structures
• 解説
• 色々ある「永続配列」「永続セグメントツリー」「永続Union-Find」「永続木」「永続平衡二分木」「永続WaveletMatrix」参考
• 部分永続。最新版のみ変更可能、Undoができる機構がある。履歴は一直線。
• 完全永続。昔のどのバージョンからでも変更でき、履歴が全て残っている。履歴は木。
• 永続配列があれば永続Union-Findが作れるらしい
• 永続配列は永続木があれば作れるらしい
• 部分永続Union-Findの資料
• 部分永続はスタックで履歴を残しておいて逆操作をしていって戻すやり方がある（要出典）多分そのやり方でやってる
• 平衡二分木を永続化するときは赤黒木が最良らしい

問題

• 完全永続セグメントツリー
  • SPOJ D-query
  • CF429 Destiny (要素add,特殊クエリ)
• 部分永続セグメントツリー
  • CSAcademy Tree Nodes Sets (要素update,全体の総和)
• 部分永続UnionFind
  • CF446 Envy
  • AGC002 D. Stamp Rally 解説1 解説2
  • AC Union Sets（ご指摘いただきました！）
• 完全永続Trie
  • CodeChef Gotham PD
  • CF457 Jamie and To-do List （+完全永続配列, 完全永続平衡二分木でも解けるらしい）
• その他(分からんやつとか)
  • CF368 Persistent Bookcase 完全永続配列(反転操作がある 実装例)
  • CF276 Sign on Fence (部分？完全？)永続セグメントツリー 解説
  • CF265 The Classic Problem 完全永続遅延評価セグメントツリー

未確定

• HR Travel in HackerLand 解説
• HR Sequential Prefix Function
• http://pekempey.hatenablog.com/archive/category/Persistent%20Segment%20Tree
• https://i.cs.hku.hk/~provinci/training2016/notes4.pdf
• https://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/
• http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2012%2FPractice%2F春コンテスト%2F講評&openfile=I.pdf
• http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2563

AtCoder Beginner Contest 062 / AtCoder Regular Contest 074 解説

ABC062 http://abc062.contest.atcoder.jp
ARC074 http://arc074.contest.atcoder.jp

【ARC074/ABC062】
コンテストは終了しました。ご参加ありがとうございました。
解説PDF：https://t.co/Wpk2kKKcJz
解説動画：https://t.co/6I4t8RR6Ru

— AtCoder (@atcoder) 2017年5月20日

以下、解説