概要

各行に宝物を表す T が含まれているかを調べます。含まれていれば o、含まれていなければ x とし、上の行から順につなげて出力します。

考察

ある行に宝物があるかどうかは、その行の文字列だけを調べれば判断できます。また、宝物の個数や位置は必要なく、T が少なくとも \(1\) つあるかどうかだけが重要です。

Python では、'T' in s によって、文字列 s に T が含まれているかを判定できます。

例えば、各行が次のようになっているとします。

..T.
....
T..T

• \(1\) 行目には T があるので o
• \(2\) 行目には T がないので x
• \(3\) 行目には T があるので o

したがって、出力は oxo です。

この問題では、すべてのマスを素朴に調べても最大 \(10 \times 10 = 100\) マスなので、TLE にはなりません。特別な高速化は不要です。ただし、宝物ごとに o を出力するのではなく、各行につき必ず \(1\) 文字だけ出力することに注意しましょう。

アルゴリズム

1. 入力を空白や改行で分割し、行数 \(H\) と各行の文字列を取得します。
2. 上の行から順に、それぞれの文字列 s について判定します。
   • 'T' in s が真なら o を選びます。
   • 偽なら x を選びます。
3. 選んだ \(H\) 個の文字を join でつなげ、出力します。

各行で T の有無に対応する文字を選び、入力と同じ順序で並べているため、求める文字列が得られます。

計算量

• 時間計算量: \(O(HW)\)
  各行の T の有無を調べるのに最大 \(O(W)\) かかり、これを \(H\) 行について行います。
• 空間計算量: \(O(HW)\)
  提示コードでは入力全体を読み込んで保持します。出力文字列には別途 \(O(H)\) の領域を使います。

実装のポイント

• sys.stdin.read().split() は入力を空白や改行で分割します。data[0] が \(H\)、data[1] が \(W\)、data[2] 以降が各行の文字列です。

• data[2:2 + H] で、地図の \(H\) 行を入力順に取り出します。

• \(W\) は各文字列の長さとして与えられているため、今回の判定では変数に保存する必要がありません。

• ''.join(...) を使うことで、o と x の間に空白を入れず、長さ \(H\) の文字列を作れます。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    H = int(data[0])
    # W is given but not needed beyond parsing
    rows = data[2:2 + H]
    print(''.join('o' if 'T' in s else 'x' for s in rows))

main()

この解説は gpt-6-astra-medium によって生成されました。