概要

デザイン原案の各マスを \(K \times K\) のブロックに拡大し、# と . をそれぞれ指定された文字に置き換えてモザイクアートを出力する問題です。

考察

この問題で行う操作は大きく2つです。

1. 拡大: 原案の各マスを \(K \times K\) の同じ文字のブロックにする
2. 色の割り当て: # を文字 \(c_1\) に、. を文字 \(c_2\) に置き換える

具体例で考えてみましょう。原案が以下の \(2 \times 3\) で \(K = 2\) の場合：

#.#
..#

横方向の拡大（各文字を \(K=2\) 個に複製）： - #.# → ##..## - ..# → ....##

縦方向の拡大（各行を \(K=2\) 回繰り返す）：

##..##
##..##
....##
....##

色の割り当て（例: \(c_1 = \) A, \(c_2 = \) B）：

AABBAA
AABBAA
BBBBAA
BBBBAA

重要な気づきとして、横の拡大と色の割り当ては同時に処理できます。各文字を見て、# なら \(c_1\) を \(K\) 個、. なら \(c_2\) を \(K\) 個並べれば、1行分の文字列が完成します。縦の拡大は、その行を \(K\) 回出力するだけで実現できます。

この問題は素朴に実装しても制約が小さい（最大出力サイズは \(100 \times 50 \times 100 \times 50 = 25{,}000{,}000\) 文字程度）ため、TLE の心配はありません。

アルゴリズム

1. \(H\), \(W\), \(K\), \(c_1\), \(c_2\) を読み込む。
2. 原案の各行 \(S\) について以下を行う：
   • \(S\) の各文字 ch に対し、ch が # なら \(c_1\) を \(K\) 回、. なら \(c_2\) を \(K\) 回繰り返した文字列を連結し、拡大後の1行 row を作る。
   • row を \(K\) 回出力する（縦方向の拡大）。

計算量

• 時間計算量: \(O(HK \times WK)\)
  • 各行（\(H\) 行）について、長さ \(WK\) の文字列を作り、\(K\) 回出力するため、出力全体のサイズに比例します。
• 空間計算量: \(O(WK)\)
  • 1行分の文字列を保持するだけで済みます。

実装のポイント

• 横の拡大と色の割り当てを一度に行う: 各文字を見て c1 * K または c2 * K を生成し、''.join(...) で連結すれば、横方向の拡大と文字の置換が同時に完了します。

• 縦の拡大は同じ行を \(K\) 回出力するだけ: 拡大後の行を変数 row に保存しておけば、内側のループで \(K\) 回 print(row) するだけで済みます。

• 行ごとに処理すればメモリ効率が良い: 全体のグリッドを二次元配列に保存する必要はなく、1行読むたびに出力を完了できます。

  ソースコード

H, W, K = map(int, input().split())
c1, c2 = input().split()
for _ in range(H):
    S = input()
    row = ''.join(c1 * K if ch == '#' else c2 * K for ch in S)
    for _ in range(K):
        print(row)

---

この解説は claude4.6opus-thinking によって生成されました。