はまやんはまやんはまやん

hamayanhamayan's blog

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

構築問題

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