Pythonで色付きタイルがカバーできるブロック数を求めるプログラム

ある道に n 個のブロックが並んでおり、作業員がそのブロックに色付きタイルを貼っていく場面を考えてみましょう。作業員は「番号が 4 または 2 で割り切れるブロック（ただし 42 を除く）」にだけ色付きタイルを貼るというルールに従います。このとき、最初に k 枚の色付きタイルを持っている場合、何番目までのブロックをカバーできるかを求めるのがこの問題です。

例えば、入力が k = 16 の場合、出力は 32 になります。これは、偶数番号のブロック 2, 4, 6, …, 32 の計 16 個にタイルを貼ると、ちょうど 16 枚を使い切るためです。

解き方のアプローチ

この問題は、42 というスキップ対象のブロックが一定間隔で現れることに着目すると、O(1) で効率的に解けます。具体的には以下の手順で計算します。

• MOD = 10^9 + 7 を定義します（結果が巨大になった場合の剰余演算用）。
• quotient := k を 20 で割った商（小数点以下切り捨て）
• remainder := k を 20 で割った余り
• remainder が 0 の場合は、(42 × quotient − 2) mod MOD を返します。
• それ以外の場合は、(42 × quotient + 2 × remainder) mod MOD を返します。

なぜ 20 で割るのかというと、42 番目のブロックに達するまでは偶数番号ごとにタイルを貼れるため、k ≤ 20 の範囲では答えは単純に 2 × k になるからです。しかし 21 枚目以降は 42 番のブロックをスキップしなければならず、その分を補正するためにこの式になっています。

実装例

理解を深めるために、以下の Python 実装を見てみましょう。

def solve(k):
   MOD = 10**9 + 7
   quotient = k // 20
   remainder = k % 20
   if remainder == 0:
      return ((42 * quotient - 2) % MOD)
   else:
      return ((42 * quotient + 2 * remainder) % MOD)

print(solve(16))

入力

16

出力

32