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