概要

\(H\) 行 \(W\) 列の座席表において、同じ行内でも同じ列内でもそのクラス名（文字）が自分自身しか存在しない「ユニークな座席」をすべて探し出し、それらを走査順に連結して出力する問題です。

考察

この問題を解く上で最も重要なのは、「ある座席 \((i, j)\) がユニークであるか」を効率的に判定することです。

素朴な方法（間に合わない方法）

すべての座席 \((i, j)\) について、その都度「同じ行に同じ文字があるか」「同じ列に同じ文字があるか」を調べるとします。 - 1つの座席の判定に \(O(H + W)\) かかります。 - 座席は全部で \(H \times W\) 個あります。 - 全体の計算量は \(O(HW(H+W))\) となります。

制約が \(H, W \leq 1000\) であるため、最大で \(1000 \times 1000 \times 2000 = 2 \times 10^9\) 回程度の計算が必要になり、実行時間制限（通常 2 秒程度）に間に合いません。

効率的な方法

各行・各列における各文字の出現回数をあらかじめ数えておく（前計算する）ことで、判定を高速化できます。 - row_counts[i][文字] : \(i\) 行目におけるその文字の出現回数 - col_counts[j][文字] : \(j\) 列目におけるその文字の出現回数

これらを事前に計算しておけば、座席 \((i, j)\) の文字を \(c\) としたとき、ユニークである条件は row_counts[i][c] == 1 かつ col_counts[j][c] == 1 であると \(O(1)\) で判定できます。

アルゴリズム

以下の手順で解くことができます。

1. 出現回数のカウント: 座席表全体を 1 回走査し、各行および各列ごとに、アルファベット ‘a’〜’z’ がそれぞれ何回出現するかを記録する配列（または連想配列）を作成します。
2. ユニークな座席の抽出: 座席表を左上から（第 1 行の左から右、次に第 2 行…の順で）走査します。 各座席 \((i, j)\) の文字 \(G_{i,j}\) について、以下の条件をチェックします。
   • \(i\) 行目において \(G_{i,j}\) の出現回数が 1 である。
   • \(j\) 列目において \(G_{i,j}\) の出現回数が 1 である。
3. 出力: 条件を満たした座席の文字を順番に連結し、最終的な文字列として出力します。

計算量

• 時間計算量: \(O(HW)\)
  • 座席表の走査（カウント時と判定時の 2 回）に \(O(HW)\) かかります。アルファベットの種類数（26）は定数として扱えます。\(H, W = 1000\) のとき \(HW = 10^6\) なので、十分に高速です。
• 空間計算量: \(O(HW)\)
  • 座席表を保持するのに \(O(HW)\) 、出現回数を保持するのに \(O(26(H+W))\) のメモリを使用します。

実装のポイント

• 文字の数値化: ord(c) - ord('a') のように文字を 0〜25 の数値に変換して配列のインデックスとして使うと、カウント処理がスムーズになります。

• 高速な入出力: \(H, W\) が大きいため、Python では sys.stdin.read().split() などを使って一括で入力を読み込むと実行時間を短縮できます。

• 空文字列の扱い: ユニークな座席が 1 つもなかった場合、空文字列（または空行）を出力するように注意します。join メソッドを使うと、リストが空の場合でも適切に空文字列を扱えます。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込み、空白文字（スペース、タブ、改行）で分割します。
    # これにより、H, W と座席表の各行を柔軟に取得できます。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
        
    if len(input_data) < 2:
        return
    
    try:
        H = int(input_data[0])
        W = int(input_data[1])
    except (ValueError, IndexError):
        return
    
    # 座席表の文字データを1つの文字列に連結し、H行W列の形式に再構成します。
    # 各行の文字列内にスペースが含まれている場合でも、これで正しく処理できます。
    all_grid_chars = "".join(input_data[2:])
    G = [all_grid_chars[i*W : (i+1)*W] for i in range(H)]
    
    if not G:
        if H > 0:
            sys.stdout.write("\n")
        return

    # 各座席のクラス名をアルファベットのインデックス（0-25）に変換しておきます。
    # これにより、ループ内での ord() 呼び出しを減らし高速化を図ります。
    G_idx = [[ord(c) - 97 for c in row] for row in G]
    
    # row_counts[i][c]: 第 i 行におけるクラス名（インデックス c）の出現回数
    # col_counts[j][c]: 第 j 列におけるクラス名（インデックス c）の出現回数
    row_counts = [[0] * 26 for _ in range(H)]
    col_counts = [[0] * 26 for _ in range(W)]
    
    # 全ての座席を走査し、各行および各列における各クラス名の出現回数をカウントします。
    for i in range(len(G_idx)):
        row_i_idx = G_idx[i]
        row_counts_i = row_counts[i]
        for j in range(len(row_i_idx)):
            c_idx = row_i_idx[j]
            # 行ごとのカウント
            row_counts_i[c_idx] += 1
            # 列ごとのカウント（jがWの範囲内であることを確認）
            if j < W:
                col_counts[j][c_idx] += 1
    
    unique_chars = []
    # 座席表を左上から行ごとに走査し、「ユニークな座席」の条件を満たすか判定します。
    for i in range(len(G_idx)):
        row_i_idx = G_idx[i]
        row_counts_i = row_counts[i]
        row_i_str = G[i]
        for j in range(len(row_i_idx)):
            c_idx = row_i_idx[j]
            if j < W:
                # 条件: その行で唯一かつ、その列で唯一のクラス名であること
                if row_counts_i[c_idx] == 1 and col_counts[j][c_idx] == 1:
                    unique_chars.append(row_i_str[j])
    
    # 見つかったユニークな座席のクラス名を連結して出力します。
    # ユニークな座席がない場合は空行が出力されます。
    sys.stdout.write("".join(unique_chars) + "\n")

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。