概要

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

考察

元のデザインは \(H \times W\) のグリッドで与えられます。これを縦横それぞれ \(K\) 倍に拡大するので、最終的なサイズは \(HK \times WK\) になります。

素朴な方法として、「各マスを \(K \times K\) のブロックに置き換える」ことをシミュレートすると、計算量が大きくなりすぎることが考えられます。例えば、各マスごとに \(K \times K\) のループを回すと、全体で \(H \times W \times K \times K\) 回の処理が必要になり、最悪ケースでは \(100 \times 100 \times 50 \times 50 = 25000000\) 回となり、時間がかかる可能性があります。

しかし、実は各行ごとに処理すれば効率的です。つまり、元の1行を拡大して1行分を作ってしまい、それを \(K\) 回繰り返すだけでOKです。これなら、各行に対して \(W \times K\) の文字列を作る操作を1回行い、それを \(K\) 回出力するだけなので、処理が高速かつシンプルになります。

例えば、入力が以下のような場合：

2 3 2
A B
#.#
.#.

元の1行目「#.」は「AABB」に拡大され、これを2回出力します。
同様に2行目「.#.」は「BAAB」に拡大され、これも2回出力されます。

このように行単位で処理することで、無駄なループを減らし、コードもシンプルになります。

アルゴリズム

1. 各行について、元の文字列を1文字ずつ見て、# なら \(c_1\) を \(K\) 個、. なら \(c_2\) を \(K\) 個連結して新しい行を作る。
2. その行を \(K\) 回出力する。
3. これをすべての行について繰り返す。

計算量

• 時間計算量: \(O(HK \cdot WK) = O(HWK^2)\)
• 空間計算量: \(O(WK)\) （1行分の文字列を保持）

※時間計算量は最終的に出力する文字数に比例します。これは避けられないため、最適です。

実装のポイント

• 各行を1度だけ変換し、それを \(K\) 回出力するのがポイント。

• 文字列の連結はPythonでは + や * を使うと簡単。

• 入力の受け取り方（リスト内包表記など）にも注意しましょう。

  ソースコード

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

for i in range(H):
    # 拡大前の1行をK倍してK行分作る
    row = ""
    for j in range(W):
        if S[i][j] == '#':
            row += c1 * K
        else:
            row += c2 * K
    # K回繰り返して出力
    for _ in range(K):
        print(row)

この解説は qwen3-coder-480b によって生成されました。