4つのキー（A・C・V・Ctrl）だけで最大数の「A」を出力する方法

問題の概要

キーボードを使って文字「A」を入力することを考えてみましょう。使用できるのは「A」「C」「V」「Ctrl」の4つのキーだけで、決められた回数のキー操作（キーストローク）で、テキストフィールドにできるだけ多くの「A」を表示することが目標です。

最大数の「A」を得るためには、次の操作を組み合わせて利用します。

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

入力と出力

入力:
キーストローク数（例: 7）

出力:
7回のキーストロークで作れる「A」の最大数は: 9
手順: A を3回押す → Ctrl+A → Ctrl+C → Ctrl+V → Ctrl+V

アルゴリズム

keyNumbers(keyStrokes)

入力: キーストロークの回数。

出力: その回数のキー操作で作れる最大の文字数。

Begin
    if keyStrokes <= 6, then
        return keyStrokes

    for n := 1 to 6, do
        result[n-1] := n
    done

    for n := 7 to keyStrokes, do
        result[n-1] := 0
        for breakpoint := n-3 down to 1, do
            curr := (n – breakpoint - 1) * result[breakpoint - 1]
            if curr > result[n-1], then
                result[n - 1] := curr
        done
    done
    result[keyStrokes - 1]
End

アルゴリズムのポイント

この問題は動的計画法（DP）で効率よく解けます。

• 6回以下の場合： 毎回「A」を直接入力するのが最適です。つまり答えはキーストローク数そのものになります。
• 7回以上の場合： 「すべて選択 → コピー → 貼り付け」をどこで行うか（分割点 breakpoint）を全通り試し、(n − breakpoint − 1) × result[breakpoint − 1] が最大になる組み合わせを求めます。
  ここで n − breakpoint − 1 は、選択とコピーに2回使った後、残りの操作すべてを貼り付けに充てたときの倍率を表します。

C++による実装例

#include<iostream>
using namespace std;

int keyNumbers(int keystrokes) {   // 4種類のキーで作れる「A」の最大数を求める
    if (keystrokes <= 6)           // 6回以下なら、Aを直接入力するのが最適
        return keystrokes;

    int result[keystrokes];        // 中間結果を保存する配列
    for (int n = 1; n <= 6; n++)   // 6回まではキーストローク数がそのまま最大値
        result[n-1] = n;

    for (int n = 7; n <= keystrokes; n++) {   // 7回目以降を動的計画法で計算
        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;
}

実行結果

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

このように、7回のキー操作では「Aを3回入力 → 全選択 → コピー → 貼り付け×2」という手順により、合計9個の「A」を作れることが確認できます。