Pythonでn回の操作（挿入・コピー・ペースト）で入力できる最大文字数を求めるプログラム

問題概要

ある整数 n が与えられたとき、以下の3種類の操作をちょうど n 回行って画面に入力できる最大の文字数を求める問題です。

• 文字「x」を1つ挿入する
• 現在表示されているすべての文字をコピーする
• コピーした内容を貼り付ける（ペーストする）

例えば、入力が n = 12 の場合、出力は 81 になります。

解法のアプローチ

この問題は、貪欲法（グリーディ法）を使うことで効率的に解けます。ポイントは、操作の組み合わせによって文字数の増加パターンが周期的に現れることです。

n が小さい場合（n ≤ 4）は、毎回「x」を挿入するだけが最適なので、答えはそのまま n になります。一方、n が大きい場合は「挿入 → コピー → ペースト」を組み合わせて文字数を効果的に増やしていきます。

具体的な手順は以下のとおりです。

1. n ≤ 4 の場合は n をそのまま返す
2. v = 6（現在の文字数）、x = 3（1回あたりの増加量）、i = 5（現在の操作回数）、j = 0（周期カウンタ）で初期化する
3. i が n に等しくなるまで、以下を繰り返す
   • v に x を加算する
   • i と j をそれぞれ 1 ずつ増やす
   • j が 3 で割り切れるとき：x を 1.5 倍にする
   • j を 3 で割った余りが 1 のとき：何もしない
   • それ以外（余りが 2）のとき：x を 2 倍にする
4. 最終的な v を結果として返す

実装例

class Solution:
    def solve(self, n):
        if n <= 4:
            return n

        v = 6
        x = 3
        i = 5
        j = 0
        while i != n:
            v += x
            i += 1
            j += 1

            if j % 3 == 0:
                x = int(x * 1.5)
            elif j % 3 == 1:
                pass
            else:
                x *= 2

        return v

ob = Solution()
n = 12
print(ob.solve(n))

入力

12

出力

81

計算量と補足

このアルゴリズムの時間計算量は O(n)、空間計算量は O(1) です。動的計画法（DP）を使って「dp[i] = max(dp[i-1] + 1, dp[i-b] × (b-1))」のように解く方法もありますが、本手法では増加率（×1.5、据え置き、×2）を3操作周期で適用するだけでよく、追加メモリなしで最大文字数を求められる点が特徴です。