手記の縦読み — 解説

問題の概要

縦 \(H\) 行、横 \(W\) 列のマス目に書かれた英小文字が \(H\) 個の文字列 \(S_1, \ldots, S_H\) として与えられます。左から \(K\) 列目の文字を上から順に読んだ文字列、すなわち各 \(i\) について \(S_i\) の \(K\) 文字目（1-indexed）を順に連結した長さ \(H\) の文字列を出力する問題です。

アルゴリズム

文字列の添字はプログラミング言語では通常 0-indexed なので、\(S_i\) の \(K\) 文字目は S_i[K-1] に対応します。

1. \(H, W, K\) を読み込む。
2. \(i = 1, \ldots, H\) について \(S_i\) を読み込み、S_i[K-1] を答えの文字列の末尾に追加する。
3. 連結した文字列を出力する。

各行を読み込んで即座に \(K\) 文字目を取り出すため、グリッド全体を保持する必要はありません。

正当性

出力するべき秘密のメッセージは、定義により「左から \(K\) 列目の文字を上から下へ順に読んだもの」です。\(S_i\) の \(j\) 文字目は上から \(i\) 行目・左から \(j\) 列目のマスの文字なので、\(i\) 行目で読むべき文字は \(S_i\) の \(K\) 文字目、すなわち S_i[K-1] です。アルゴリズムは \(i = 1\) から \(H\) まで順にこの文字を連結するため、出力はちょうど要求される長さ \(H\) の文字列になります。制約 \(1 \le K \le W\) と「\(S_i\) は長さ \(W\)」より S_i[K-1] は常に存在し、範囲外アクセスは起こりません。同点や曖昧さは問題に存在しないため、タイブレークは不要です。

計算量

• 時間計算量: \(O(HW)\)（入力の読み込みを含む）。
• 空間計算量: C++ は \(O(H + W)\)、Python は \(O(HW)\)。入力・出力として保持する配列や文字列も含む。