概要

各マスの文字が「その行でもその列でも1回しか出現しない」ものだけを左上から順に拾い集めて、連結した文字列を出力する問題です。

考察

ある座席 \((i,j)\) がユニークである条件は、次の2つを同時に満たすことです。

• 行 \(i\) において文字 \(G_{i,j}\) の出現回数が \(1\)
• 列 \(j\) において文字 \(G_{i,j}\) の出現回数が \(1\)

つまり「行と列それぞれで、その文字の出現回数が1かどうか」が分かれば判定できます。

素朴に、各マスごとに - 行を全部見て同じ文字が何個あるか数える（\(O(W)\)） - 列を全部見て同じ文字が何個あるか数える（\(O(H)\)）

をやると、1マスあたり \(O(H+W)\) なので全体で \(O(HW(H+W))\) となり、最大 \(1000 \times 1000\) では間に合いません。

そこで先に - 各行ごとの各文字（a〜z）の出現回数 - 各列ごとの各文字（a〜z）の出現回数

をまとめて数えておき、各マスはその結果を見て \(O(1)\) で判定します。アルファベット小文字は26種類しかないので、集計も高速です。

アルゴリズム

1. 入力のグリッド（\(H\) 行の文字列）を読み込む。
2. row_cnt[i][c] を「行 \(i\) における文字 \(c\) の出現回数」、col_cnt[j][c] を「列 \(j\) における文字 \(c\) の出現回数」として、サイズ \(H \times 26\) と \(W \times 26\) の配列を用意する。
3. 全マス \((i,j)\) を1回走査し、文字 ch について
   • row_cnt[i][ch] += 1
   • col_cnt[j][ch] += 1 として出現回数を集計する。
4. もう一度全マスを左上から行優先で走査し、各マス \((i,j)\) の文字 ch が
   • row_cnt[i][ch] == 1 かつ col_cnt[j][ch] == 1 を満たすなら答えに追加する。
5. 追加した文字を連結して出力する（1つもなければ空行）。

（例）行の中に同じ文字が2回出ていたら、その行のその文字はどの列にあっても「行条件」で弾かれるので、最初に回数を持っておくのが有効です。

計算量

• 時間計算量: \(O(HW)\)
  （集計で1回、判定で1回の合計2回グリッドをなぞるだけ）
• 空間計算量: \(O((H+W)\cdot 26)\)
  （行・列ごとの26文字カウント。加えて入力グリッド \(O(HW)\) を保持）

実装のポイント

• 文字 ch を 0〜25 に変換して配列で管理すると高速です（k = ord(ch) - ord('a')）。

• 出力は文字をリストに append して最後に "".join(...) すると効率が良いです（文字列の逐次連結は遅くなりがち）。

• ユニークな座席が0個の場合でも、問題は「空行を出力」なので最後に "\n" を必ず付けて出力します。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    H, W = map(int, input().split())
    grid = [input().decode().strip() for _ in range(H)]

    row_cnt = [[0] * 26 for _ in range(H)]
    col_cnt = [[0] * 26 for _ in range(W)]

    for i in range(H):
        row = grid[i]
        rc = row_cnt[i]
        for j, ch in enumerate(row):
            k = ord(ch) - 97
            rc[k] += 1
            col_cnt[j][k] += 1

    out = []
    for i in range(H):
        row = grid[i]
        rc = row_cnt[i]
        for j, ch in enumerate(row):
            k = ord(ch) - 97
            if rc[k] == 1 and col_cnt[j][k] == 1:
                out.append(ch)

    sys.stdout.write("".join(out) + "\n")

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。