競技プログラミングにおける構築問題まとめ

構築問題

条件を満たす何かを作る
逆引きとかテク
- 【テク2】「条件を満たす辞書順最小」頭から貪欲に整合性が保たれるように決めていく
- 「今の状態に何かを加えて答えを +1 か ×2 にする操作」2進数的に作れる問題
- 小さい状態ではおかしなことが起こる場合は、小さい場合だけ乱択アルゴリズムで解決するテクがあるこの問題
- dpをして、それを元に復元して構築というのもある(文字列系構築でよくある（らしい）)
- 「複数のオイラーパスで特定の辺をカバーしたいとき、先にいくつかの奇数次数の辺を結んでしまうというテク」
  - 1. 奇数次数の辺を結んでしまってオイラーパスを構築
  - 2. 構築後にオイラーパスに含まれる1.で作ったパスを削除して、求めたいオイラーパス群を得る
- 状態数が限られている式の構築は反復法でdpを収束するまで更新することで得るテクがあるこれ
- 制約式が沢山出てきて、そこから解を絞ることによって得られるこれ
- とても長い文字列の一部分を取ってくるには再帰的な性質が無いなら、何かしら法則性が元々無いと厳しいこれ
- 中には天才的なセンスを求めるものもある
  - まずは構成できる条件をしっかり考えたほうがいい
- 「①最上位の数と桁数を決定する②上位桁から順番に数を決定していく」というテク
- 【テク1】n進数として考えて、各桁毎に決定できるように作る
- 【テク3】市松模様を意識して作る
- KokiYmgchさんの平面上のロシアゲー（構築ゲー）を解くためのそこそこ一般的なテクについてがとても有用
- 【テク4】答えが無いかも知れない問題では構築したあとに条件を満たしているか確認しておいた方が良い
- 【テク5】4つの象限に分けて処理していく（Nが偶数）
- 【テク6】最も小さい形からインクリメンタルに大きいものを作っていく
- 【テク7】上限ギリギリの条件での構築方法が全部に使える