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

hamayanhamayan's blog

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

構築問題

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