ペペロの受け渡し

どれかの種類の本数が一致しなければ不可能である。一致すれば必ず可能となる。各スタックは単色で、両方が空でなければ互いに異なる種類を保持する、という不変条件を維持する。次に必要な種類を $c$ とする。

第 $2$ スタックに $c$ があれば 2、第 $1$ スタックにあれば 12 を実行する。どちらにもなければ、未読の入力に $c$ が必ず残っている。入力を順に読み、$c$ を見つけたら 012 で直ちに渡す。

途中の別の種類 $d$ は次のように保存する。第 $2$ スタックが $d$ なら 01。そうでなく、第 $1$ スタックが空か $d$ なら 0。残る場合、第 $2$ スタックは必ず空なので 01 を実行する。両スタックが $d$ 以外の異なる種類で埋まっているなら、種類は三つだけなので一方が となり、現在の前提に矛盾する。先に第 スタックとの一致を確認し、同じ種類が両方に分かれないようにする。いずれの操作も不変条件を保つ。

各ペペロは入力、第 $1$ スタック、第 $2$ スタック、出力を一度ずつ通るので命令数は厳密に $3N$。時間と領域は $O(N)$。サブタスク $1$ は状態を記憶する全探索で解ける。状態数は高々 $O(N^3 3^N)$、文字列処理を含む時間は で、 なら十分である。サブタスク は第 スタックだけをバッファとして使い、必要な種類が一番上に来るまで入力を積めばよい。二種類なら受け渡し直後のバッファは常に単色となり、 時間で解ける。

Solution written by GPT6.1