構築問題

概要

条件を満たす具体的な例を $1$ つ作って出力する問題。
通常の問題であれば、各入力に対して正しい答えは $1$ つしかないが、構築問題は一般に解が多数ある。
どれか $1$ つでも条件を満たすものを出力できれば、問題ページの出力例と異なっていてもよい。

例えば、以下は簡単な構築問題である。

A, B, C, X の4種類の文字からなる文字列が与えられる。
それぞれの X を A, B, C のいずれかに書き換えた文字列を作成し、出力せよ。
ただし、その文字列の中に、同じ文字が連続する部分が含まれていてはならない。

入力が "AXXC" だった場合、出力は "ABAC" でも "ACAC" でも "ACBC" でもよい。

作れない場合はそう答える問題もある。
作れるかどうかや最大値を答える問題でも、実際に例を作ってみて答えるという実質的構築問題もある。

構築方法の例

条件を足して考える

例えば、冒頭の問題。
条件として「その中で辞書順最小のものを作れ」を追加してみる。
すると、先頭から順に「前後に同じ文字がない最も若いアルファベット」を決めていくだけでよくなる。

うまい条件を足せれば感動的にスッキリ解けるが、失敗するとただ複雑になるだけである。
それどころか、変なものを足したせいで、解が存在しなくなる場合すらある。
この方法で解くには、柔軟な思考と経験が必要となる。

小さい場合を手で作る

例えば、以下の問題。

正の整数 N をいくつかの異なる正の整数の和で表すとき、その個数の最大値 M を答えよ。
また、実際に M 個の和として表せ。

一見難しそうだが、小さい例についていいので作ってみるとよい。
手段は、手計算でも全探索プログラムでもいい。

これを見れば、規則性は単純である。
$1+2+3+\dots +K$ が初めて $N$ 以上になるまで和を作り、オーバーした分の $1$ つを取り除けばよい。

このように、小さい例について作ってみると、規則性が見えることがある。
しかし、その規則が小さい場合にだけたまたま成り立っているだけという可能性もあり、注意が必要。

必要条件から考える

条件を満たすものが存在するなら、必ず成り立つ性質を探す。

例えば、合計、個数、偶奇、最大値、最小値、次数、連結性など。
これらを見ると、作れない場合を先に除外できることがある。
また、作れるとしたら何を守らなければならないかもわかる。

例えば、一筆書きの問題。
スタート地点とゴール地点以外は、入ってくる道と出ていく道がセットになっている必要がある。
つまり、その場所からは必ず偶数本の線が出ている必要がある。
ということは、奇数本の線が $2$ ヶ所まででなければその時点で不可能を判断できる。
また、$2$ ヶ所である場合は、その片方がスタートでもう片方がゴールというパターンのみ考えればよい。

ただし、必要条件を見つけただけでは十分ではない。
その条件を満たしても不可能な場合もあるし、構築もさらに考察を深めなければならない場合も多い。

逆向きに考える

最終的に必要な形から逆に考えると、作り方が見える場合がある。

例えば、操作列を出力する問題では、目的の状態から逆向きに戻す方が簡単なことがある。
逆向きに作った操作列は、最後に反転すれば元の向きの操作列になる。
詳しくは「バックトレース」の記事参照。

より小さい問題に帰着する

例えば、$1$ から $N$ までの整数を、和が等しくなるような $2$ つのグループにわけるという問題。

片方に $N$ と $N-3$ を、もう片方に $N-1$ と $N-2$ を入れるとする。
すると、あとは $N$ が $4$ 小さくなった問題を解けばよい。
再帰的に繰り返して $N=3$ または $N=4$ の場合に帰着できる場合には、これで解ける。

ただし、この方法で不可能な場合に、他の方法でも不可能かどうかはわからない点に注意。

問題を言い換える

例えば、与えられた文字列で最長のしりとりを作る場合。

"apple" という文字列をこのまま考えるのではなく、a という頂点から e という頂点への辺とみなす。
すると、最長のしりとりを作る問題は、グラフ上で最長のパスを探す問題となる。
グラフ理論のいろいろなアルゴリズムが使えるようになるので問題が解きやすくなる。

注意点

出力例と同じでなくてもよい

構築問題では、条件を満たす解が複数あることも多い。
その場合、出力例と違うものを出しても正解になる。

サンプルテストで出力例と一致しない場合でも、自分の出力が条件を満たしているなら問題ない。
逆に、見た目がそれっぽくても条件を満たしていなければ不正解である。
出力が条件を満たすか、慎重に確認すること。

あるいは、ARCなどでは、少し時間を使ってチェッカーを実装した方が結果的に速い場合もある。

小さいケースに注意する

一般的な作り方が、$N=1$ や $N=2$ などの小さい場合だけ壊れることがある。
小さい入力や端の入力は、自作テストで確認すること。

不可能判定に注意する

No や -1 を出す場合、本当に作れないことを確認する必要がある。

「自分の方法では作れない」ことは、「どんな方法でも作れない」という意味ではない。
構築できないと判断する場合は、合計、偶奇、個数、制約などから、不可能である理由を確認する。

関連知識

考察問題

構築問題では、条件整理や性質発見が必要になることが多い。
つまり、考察問題とは共通する部分が多い。

コーナーケース

小さい入力、端の値、余りが出る場合などで、構築方法が壊れることがある。
特殊な入力でも条件を満たすものが作れるか確認する。

テスト

構築問題では、出力例と同じでなくても正解になることがある。
自分の出力が問題文の条件を満たしているかを確認する必要がある。

全探索

小さい入力を全探索すると、構築の規則性や不可能条件を見つけられることがある。
また、構築した答えが正しいかを小さいケースで照合できる場合もある。

貪欲法

前から順に値を決めるなど、貪欲法に近い考え方で構築することがある。

パリティ

作れる必要条件にパリティが関わることも多い。

バックトレース

最終状態から逆向きにたどることで、操作列や具体例を構築できる場合がある。