概要

デザイン原案を縦横それぞれ \(K\) 倍に拡大し、指定された文字に置き換えたモザイクアートを出力する問題です。

考察

この問題では、元の \(H \times W\) のグリッドを \(K\) 倍に拡大する必要があります。素朴なアプローチとして、拡大後の \(HK \times WK\) のグリッドを直接構築しようとすると、各マスを個別に処理する必要があり、計算量が \(O(H \cdot W \cdot K^2)\) となります。しかし、制約が最大 \(H=100, W=100, K=50\) なので、\(100 \times 100 \times 50^2 = 25,000,000\) 回の処理が必要となり、Pythonなどのインタプリタ言語では実行時間が厳しくなる可能性があります。

しかし、実際には各行・各列の繰り返しパターンを利用することで、効率的に拡大後のグリッドを構築できます。具体的には、元のグリッドの各マスを \(K\) 回横に繰り返し、さらに各行を \(K\) 回縦に繰り返すことで、拡大後のグリッドを効率的に生成できます。

アルゴリズム

1. 元のグリッドの各行について、各マスを文字変換（# → \(c_1\)、. → \(c_2\)）した後、各文字を \(K\) 回繰り返して横方向に拡大した行を生成します。
2. 生成した各行を \(K\) 回繰り返して縦方向に拡大し、出力します。

このアプローチでは、各元の行に対して横方向の拡大を1回行い、それを \(K\) 回出力するだけなので、計算量を大幅に削減できます。

計算量

• 時間計算量: \(O(H \cdot W \cdot K)\)
  • 元のグリッドの各マスを処理（\(H \cdot W\) 回）し、各マスに対して \(K\) 回の文字列繰り返し操作を行うため。
• 空間計算量: \(O(H \cdot W \cdot K)\)
  • 拡大後の1行分の文字列を保持するため（最大 \(W \cdot K\) 文字）。

実装のポイント

• 文字列の乗算演算（char * K）を使って、横方向の拡大を効率的に行います。

• 各行を横方向に拡大した後、その行を \(K\) 回出力することで縦方向の拡大を実現します。

• メモリ効率を考慮し、拡大後の全体のグリッドを一度に保持するのではなく、1行ずつ生成して出力します。

  ソースコード

H, W, K = map(int, input().split())
c1, c2 = input().split()
grid = [input() for _ in range(H)]

for i in range(H):
    expanded_row = []
    for j in range(W):
        char = c1 if grid[i][j] == '#' else c2
        expanded_row.append(char * K)
    expanded_line = ''.join(expanded_row)
    for _ in range(K):
        print(expanded_line)

この解説は deepseekv3 によって生成されました。