概要

座席表から、同じ行と列に同じクラス名が他に存在しない「ユニークな座席」を探し、そのクラス名を左上から順に連結した文字列を出力する問題です。

考察

各座席について、その行と列に同じクラス名の座席が他にないかをチェックする必要があります。素朴なアプローチでは、各座席 \((i, j)\) について、行 \(i\) と列 \(j\) を全探索して同じクラス名の存在を確認することになりますが、これでは \(O(HW \times (H + W))\) の計算量となり、最大 \(1000 \times 1000 = 10^6\) 座席に対して各行・列（最大1000要素）をチェックすると \(10^6 \times 2000 = 2 \times 10^9\) 回の操作が必要になり、時間制限に間に合いません。

そこで、各行と各列ごとに、各クラス名の出現回数を事前にカウントしておくことで、各座席のチェックを定数時間で行えるようにします。

アルゴリズム

1. 前処理: 各行と各列について、各クラス名の出現回数をカウントする
   • row_counts[i]: 行 \(i\) における各クラス名の出現回数を格納する辞書
   • col_counts[j]: 列 \(j\) における各クラス名の出現回数を格納する辞書
2. メイン処理: 各座席 \((i, j)\) について、以下の条件をチェック
   • 行 \(i\) において、クラス名 \(G_{i,j}\) の出現回数が1である
   • 列 \(j\) において、クラス名 \(G_{i,j}\) の出現回数が1である
3. 出力: 条件を満たす座席のクラス名を左上から順に連結して出力

計算量

• 時間計算量: \(O(HW)\)
  • 前処理で各行・各列のカウントに \(O(HW)\)
  • メイン処理で各座席のチェックに \(O(HW)\)
• 空間計算量: \(O(HW)\)
  • グリッドの保存に \(O(HW)\)
  • 行と列のカウント用のデータ構造に \(O(HW)\)（各行・各列の辞書の合計サイズ）

実装のポイント

• 行と列のカウント用に、辞書のリストを使用する

  • row_counts は長さ \(H\) のリストで、各要素が行 \(i\) の辞書
  • col_counts は長さ \(W\) のリストで、各要素が列 \(j\) の辞書

• カウントは二重ループで一度に行い、効率的に処理する

• 条件を満たす座席のクラス名はリストに追加し、最後に連結して出力する

  ソースコード

import sys

def main():
    data = sys.stdin.read().splitlines()
    if not data:
        return
    
    H, W = map(int, data[0].split())
    grid = []
    for i in range(1, 1 + H):
        grid.append(data[i].strip())
    
    row_counts = [{} for _ in range(H)]
    col_counts = [{} for _ in range(W)]
    
    for i in range(H):
        for j in range(W):
            c = grid[i][j]
            if c in row_counts[i]:
                row_counts[i][c] += 1
            else:
                row_counts[i][c] = 1
                
            if c in col_counts[j]:
                col_counts[j][c] += 1
            else:
                col_counts[j][c] = 1
                
    result = []
    for i in range(H):
        for j in range(W):
            c = grid[i][j]
            if row_counts[i][c] == 1 and col_counts[j][c] == 1:
                result.append(c)
                
    print(''.join(result))

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。