概要

\(H \times W\) の座席表が与えられ、各座席の文字がその行でもその列でも1回しか現れない場合に「ユニークな座席」とみなし、該当する文字を左上から行順に連結して出力する問題です。

考察

重要な気づき

ある座席 \((i, j)\) がユニークであるためには、次の2つを同時に満たす必要があります。

1. 第 \(i\) 行の中で、文字 \(G_{i,j}\) が1回しか出現しない
2. 第 \(j\) 列の中で、文字 \(G_{i,j}\) が1回しか出現しない

例えば、以下の \(3 \times 3\) の座席表を考えます。

abc
bca
cab

座席 \((1, 1)\) の文字は a です。第1行 abc の中で a は1回だけ、第1列（上から a, b, c）の中で a も1回だけなので、ユニークです。

素朴なアプローチの問題点

各座席 \((i, j)\) について、毎回その行全体・列全体を走査して出現回数を数えると、1座席あたり \(O(H + W)\) かかり、全体で \(O(H \times W \times (H + W))\) となります。\(H, W\) が最大 \(1000\) の場合、これは最大 \(2 \times 10^9\) 程度の計算となりTLEの恐れがあります。

解決策

前処理として、各行・各列ごとに文字の出現回数を事前に数えておくことで、各座席の判定を \(O(1)\) で行えます。

アルゴリズム

1. 行ごとの文字出現回数を計算: 各行 \(i\) について、Counter を使い各文字が何回出現するかを記録します。これを row_count[i] とします。

2. 列ごとの文字出現回数を計算: 各列 \(j\) について、全行を走査して各文字が何回出現するかを記録します。これを col_count[j] とします。

3. ユニーク判定: 座席 \((i, j)\) について、文字 \(c = G_{i,j}\) が row_count[i][c] == 1 かつ col_count[j][c] == 1 であれば、ユニークな座席です。

4. 結果の出力: 第1行の左から右、第2行の左から右、……の順でユニークな座席の文字を連結して出力します。

計算量

• 時間計算量: \(O(H \times W)\)
  • 行ごとのカウント: 各行の文字列を走査するので合計 \(O(H \times W)\)
  • 列ごとのカウント: 全座席を走査するので \(O(H \times W)\)
  • ユニーク判定: 全座席を走査し、各座席 \(O(1)\) で判定するので \(O(H \times W)\)
• 空間計算量: \(O(H \times W + (H + W) \times |\Sigma|)\)
  • \(|\Sigma| = 26\)（アルファベット小文字の種類数）
  • 座席表の格納に \(O(H \times W)\)、カウンタの格納に \(O((H + W) \times 26)\)

実装のポイント

• Pythonの collections.Counter を使うと、文字列をそのまま渡すだけで各文字の出現回数を簡単に取得できます。

• 列方向のカウントは、行を走査しながら各列のカウンタに加算していく形で計算します（列ごとに文字列を構築する必要はありません）。

• sys.stdin.buffer.read() を使って入力を一括読み込みすることで、大きな入力でも高速に処理できます。

  ソースコード

import sys
from collections import Counter

def main():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    H = int(tokens[idx]); idx += 1
    W = int(tokens[idx]); idx += 1
    
    grid = []
    for i in range(H):
        grid.append(tokens[idx]); idx += 1
    
    # Count occurrences of each character in each row
    row_count = []
    for i in range(H):
        row_count.append(Counter(grid[i]))
    
    # Count occurrences of each character in each column
    col_count = [Counter() for _ in range(W)]
    for i in range(H):
        for j in range(W):
            col_count[j][grid[i][j]] += 1
    
    result = []
    for i in range(H):
        for j in range(W):
            c = grid[i][j]
            if row_count[i][c] == 1 and col_count[j][c] == 1:
                result.append(c)
    
    print(''.join(result))

main()

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