概要

各座席にアルファベットが書かれた \(H \times W\) の座席表が与えられ、各行および各列においてただ一つだけ存在する文字（クラス名）を持つ座席を「ユニークな座席」と定義します。これらの座席のクラス名を左上から順に読んでできる文字列を出力する問題です。

考察

この問題では、各座席 \((i, j)\) に対して、「その行の中で同じ文字が他にない」かつ「その列の中で同じ文字が他にない」かどうかを判定する必要があります。

素朴な方法としては、各座席について、その行と列を全探索して同じ文字の個数を数える方法があります。しかし、これだと各座席に対して最大で \(H + W\) 回の比較が必要となり、全体で最大 \(H \times W \times (H + W)\) 回の計算が必要になります。制約が \(H, W \leq 1000\) なので、最悪の場合で \(2 \times 10^9\) 回を超える計算となり、時間内に処理しきれません（TLE）。

そこで、事前に各行・各列における各文字の出現回数を前もって計算しておくことで、各座席の判定を定数時間で行えるようにします。具体的には、各座席 \((i, j)\) に対して、行 \(i\) 内での grid[i][j] の出現回数と、列 \(j\) 内での出現回数がともに \(1\) であるかを確認すればよいです。

アルゴリズム

1. 各行に対して、含まれる各文字の出現回数をカウントします（row_count[i][char]）。
2. 各列に対して、含まれる各文字の出現回数をカウントします（col_count[j][char]）。
3. 各座席 \((i, j)\) について、その文字 char = grid[i][j] が：
   • 行 \(i\) 内で1回だけ出現する（row_count[i][char] == 1）
   • 列 \(j\) 内で1回だけ出現する（col_count[j][char] == 1） を確認し、両方満たしていればその座席はユニークです。
4. ユニークな座席の文字を左上から順に結果のリストに追加し、最後に連結して出力します。

例

入力が以下の場合：

3 3
abc
def
ghi

各行・各列にはすべて異なる文字しかないので、すべての座席がユニークになります。結果は abcdefghi となります。

一方で、以下のような場合：

2 2
aa
bb

どの座席も行または列で重複しているため、ユニークな座席はありません。結果は空文字列です。

計算量

• 時間計算量: \(O(H \times W)\)
  • 各行・各列の文字カウントに \(O(H \times W)\)、各座席の判定に \(O(H \times W)\)。
• 空間計算量: \(O(H \times W)\)
  • row_count と col_count に使用されるメモリが最大で \(O(H \times W)\) 必要。

実装のポイント

• 各行・各列の文字出現回数を辞書型で前計算しておくことが肝心。
• 文字列結合は最後に一度だけ join() を使うことで効率的に行える。
• 空文字列を出力するケース（ユニークな座席がない場合）も考慮すること。

## ソースコード

```python
H, W = map(int, input().split())
grid = [input().strip() for _ in range(H)]

# 各行について、各文字の出現回数をカウント
row_count = [{} for _ in range(H)]
for i in range(H):
    for char in grid[i]:
        row_count[i][char] = row_count[i].get(char, 0) + 1

# 各列について、各文字の出現回数をカウント
col_count = [{} for _ in range(W)]
for j in range(W):
    for i in range(H):
        char = grid[i][j]
        col_count[j][char] = col_count[j].get(char, 0) + 1

# 結果を格納するリスト
result = []

# 各座席についてチェック
for i in range(H):
    for j in range(W):
        char = grid[i][j]
        # 行内でその文字が1回だけ出現し、列内でもその文字が1回だけ出現すればユニーク
        if row_count[i][char] == 1 and col_count[j][char] == 1:
            result.append(char)

print(''.join(result))

---

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