C++で解く「4キーキーボード」問題 ― 4種類のキー操作でAの入力数を最大化する方法

キーボードで文字「A」を入力する状況を想像してみてください。ここでの目標は、わずか4種類のキー操作だけを使って、テキストフィールドにできるだけ多くの「A」を表示することです。使用できるキーは「A」「Ctrl」「C」「V」の4つです。

「A」の数を最大化するには、次のショートカット操作を組み合わせます。

• Ctrl + A … すべてを選択
• Ctrl + C … コピー
• Ctrl + V … 貼り付け

問題の例

たとえば、キーストローク数が7回だとすると、出力は9になります。具体的な操作手順は次のとおりです。

1. 「A」を3回入力(この時点で3文字)
2. Ctrl + A(3文字をすべて選択)
3. Ctrl + C(コピー)
4. Ctrl + V(貼り付けで6文字に)
5. Ctrl + V(さらに貼り付けで9文字に)

このように、コピーした3文字を2回貼り付けることで、合計9文字の「A」が得られます。

解法のアプローチ:動的計画法

この問題は、動的計画法(DP)を使うと効率よく解けます。ポイントは次の2つです。

• キーストロークが6回以下の場合:選択・コピー・貼り付けには合計3回の操作が必要なため、それらを挟むより単純に「A」を押し続ける方が有利です。したがって答えはキーストローク数そのものになります。
• 7回以上の場合:どこかの時点で「Aの入力」から「選択→コピー→貼り付けの繰り返し」へ戦略を切り替えるのが最適です。この切り替え地点(ブレークポイント)をすべて試して最大値を求めます。

アルゴリズムの手順

1. keyStrokes ≤ 6 ならば、keyStrokes をそのまま返します。
2. n = 1 から 6 まで、result[n-1] = n を設定します。
3. n = 7 から keyStrokes まで、次を繰り返します。
   • result[n-1] を 0 で初期化します。
   • breakpoint を n-3 から 1 まで減らしながら、curr = (n − breakpoint − 1) × result[breakpoint − 1] を計算します。
   • curr が result[n-1] より大きければ、result[n-1] を curr で更新します。
4. 最終的に result[keyStrokes − 1] を返します。

漸化式の意味を補足すると、ブレークポイント b 回目までに result[b−1] 個の「A」ができている状態で、残りのキーストロークを Ctrl+A(1回)・Ctrl+C(1回)・Ctrl+V(残りすべて)に充てると、最終的な文字数は (n − b − 1) × result[b−1] になります。すべての b についてこの値を調べ、最大のものを採用するのがこのDPの骨子です。

実装例(C++)

それでは、実際のC++コードを見てみましょう。

#include<iostream>
using namespace std;

// 4種類のキー操作で入力できる「A」の最大数を求める
int keyNumbers(int keystrokes){
    if (keystrokes <= 6) // 7回未満ならそのまま返す
        return keystrokes;
    int result[keystrokes]; // 中間結果を格納する配列
    for (int n = 1; n <= 6; n++) // 6回までは「A」を押した回数がそのまま最大値
        result[n-1] = n;
    for (int n = 7; n <= keystrokes; n++){ // 7回目以降をDPで計算
        result[n-1] = 0; // 初期値は0
        for (int breakPoint = n-3; breakPoint >= 1; breakPoint--){ // 選択・コピー・貼り付けへ切り替える地点を探す
            int curr = (n - breakPoint - 1) * result[breakPoint-1];
            if (curr > result[n-1])
                result[n-1] = curr;
        }
    }
    return result[keystrokes-1];
}

int main(){
    int keystrokes;
    cout << "Enter Number of keystrokes: ";
    cin >> keystrokes;
    cout << "Maximum Number of A's with " << keystrokes << " keystrokes is: " << keyNumbers(keystrokes) << endl;
}

入力

7

出力

Maximum Number of A's with 7 keystrokes is: 9

まとめ

この問題の鍵は、6回を境に最適な戦略が変わる点に気づくことです。7回目以降は「どこでコピー操作に切り替えるか」というブレークポイントを全探索する動的計画法で解けます。計算量は O(N²) であり、キーストローク数が数百程度であれば十分高速に動作します。