【競技プログラミング】AtCoder Beginner Contest 315_D問題(TLE版)

# 問題
https://atcoder.jp/contests/abc315/tasks/abc315_d

# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)

# 雑記
一見、簡単に見えたんですよ。でも3時間くらいハマってしまったので、撤退。
diffを見てみたら、1531で水色上位問題ですか。
難しい記憶があったのは、AtCoder Beginner Contest 322のポリオミノだけど、それより絶対難しいと思う。

せめてもの抵抗として、考え方は当っているだろ！とC++で提出したところ、、、

testcase29.txt		2219 ms	195092 KB
testcase30.txt		2218 ms	176496 KB
testcase31.txt		2219 ms	195200 KB
testcase32.txt		2219 ms	179444 KB
がどうしてもTLE。

現時点で、競技プログラミングをやっている目的は上ランク狙いではなく、問題に対する考え方や、解き方を学ぶためなので、2024年11月27日時点では力不足の魚拓として残しておきます。
悔しいので、この問題はAC出来なくても考え方のまとめ資料残すことにしよ。

来年末までには絶対ACできるだけの実力を付けてやる！

# アプローチ

効率的にクッキーの除去を行うために、行と列ごとのアルファベットの出現回数と種類数を管理する。
これによって、同じ色のクッキーが2枚以上ある行や列を素早く特定できる。
クッキーの除去操作を繰り返し、最終的に残ったクッキーの枚数を計算する。

# 解法手順

1. 入力データを受け取り、初期状態を設定する。
   - クッキーの配置を2次元リストSに格納する。
   - 各行、各列におけるアルファベットの出現回数をカウントする。
   - 各行、各列に存在するアルファベットの種類数を記録する。

2. クッキーの除去処理を行う関数removeを定義する。
   - 指定された位置のクッキーを除去し、関連するカウンタを更新する。

3. メインのループ処理を実行する。
   - 各行で、アルファベットの種類数が1かつ列数が2以上の場合、その行を削除対象とする。
   - 各列で、アルファベットの種類数が1かつ行数が2以上の場合、その列を削除対象とする。
   - 削除対象の行と列がない場合、ループを終了する。

4. 削除対象の行と列に対して、removeを呼び出してクッキーを除去する。
   - 残りの行数と列数を更新する。

5. 最終的に残った行数と列数の積を計算し、結果を出力する。


# TLEコード(python)
```python:ac.py

# 1. 入力データを受け取り、初期状態を設定する
N, M = map(int, input().split())  # N行M列のグリッドサイズを入力
S = [list(input()) for _ in range(N)]  # クッキーの配置を2次元リストSに格納

# 各行、各列におけるアルファベットの出現回数をカウントする辞書
row_count = [{} for _ in range(N)]
col_count = [{} for _ in range(M)]

# 各行、各列に存在するアルファベットの種類数を記録するリスト
row_types = [0] * N
col_types = [0] * M

# 初期状態のカウントを設定
for i in range(N):
    for j in range(M):
        if S[i][j] not in row_count[i]:
            row_count[i][S[i][j]] = 1
            row_types[i] += 1
        else:
            row_count[i][S[i][j]] += 1
        
        if S[i][j] not in col_count[j]:
            col_count[j][S[i][j]] = 1
            col_types[j] += 1
        else:
            col_count[j][S[i][j]] += 1

# 2. クッキーの除去処理を行う関数removeを定義する
def remove(i, j):
    char = S[i][j]  # 除去するクッキーの文字
    S[i][j] = '.'  # クッキーを除去（'.'で置換）
    
    # 行のカウントを更新
    row_count[i][char] -= 1
    if row_count[i][char] == 0:
        del row_count[i][char]
        row_types[i] -= 1
    
    # 列のカウントを更新
    col_count[j][char] -= 1
    if col_count[j][char] == 0:
        del col_count[j][char]
        col_types[j] -= 1

# 3. メインのループ処理を実行する
while True:
    to_remove = set()  # 削除対象の座標を格納するセット
    
    # 行の確認
    for i in range(N):
        if row_types[i] == 1 and sum(row_count[i].values()) >= 2:
            for j in range(M):
                if S[i][j] != '.':
                    to_remove.add((i, j))
    
    # 列の確認
    for j in range(M):
        if col_types[j] == 1 and sum(col_count[j].values()) >= 2:
            for i in range(N):
                if S[i][j] != '.':
                    to_remove.add((i, j))
    
    # 削除対象がない場合、ループを終了
    if not to_remove:
        break
    
    # 4. 削除対象のクッキーを除去
    for i, j in to_remove:
        remove(i, j)

# 5. 最終的に残ったクッキーの数を計算し、結果を出力する
result = sum(1 for row in S for cookie in row if cookie != '.')
print(result)

```


# TLEコード(C++)
```cpp:ac.cpp

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>

using namespace std;

// グローバル変数の宣言
int N, M;
vector<vector<char>> S;
vector<map<char, int>> row_count, col_count;
vector<int> row_types, col_types;

// 2. クッキーの除去処理を行う関数removeを定義する
void remove(int i, int j) {
    char ch = S[i][j];  // 除去するクッキーの文字
    S[i][j] = '.';  // クッキーを除去（'.'で置換）
    
    // 行のカウントを更新
    row_count[i][ch]--;
    if (row_count[i][ch] == 0) {
        row_count[i].erase(ch);
        row_types[i]--;
    }
    
    // 列のカウントを更新
    col_count[j][ch]--;
    if (col_count[j][ch] == 0) {
        col_count[j].erase(ch);
        col_types[j]--;
    }
}

int main() {
    // 1. 入力データを受け取り、初期状態を設定する
    cin >> N >> M;  // N行M列のグリッドサイズを入力
    S.resize(N, vector<char>(M));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> S[i][j];
        }
    }

    // 各行、各列におけるアルファベットの出現回数をカウントする辞書
    row_count.resize(N);
    col_count.resize(M);

    // 各行、各列に存在するアルファベットの種類数を記録するリスト
    row_types.resize(N, 0);
    col_types.resize(M, 0);

    // 初期状態のカウントを設定
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (row_count[i].find(S[i][j]) == row_count[i].end()) {
                row_count[i][S[i][j]] = 1;
                row_types[i]++;
            } else {
                row_count[i][S[i][j]]++;
            }
            
            if (col_count[j].find(S[i][j]) == col_count[j].end()) {
                col_count[j][S[i][j]] = 1;
                col_types[j]++;
            } else {
                col_count[j][S[i][j]]++;
            }
        }
    }

    // 3. メインのループ処理を実行する
    while (true) {
        set<pair<int, int>> to_remove;  // 削除対象の座標を格納するセット
        
        // 行の確認
        for (int i = 0; i < N; i++) {
            if (row_types[i] == 1) {
                int sum = 0;
                for (const auto& pair : row_count[i]) {
                    sum += pair.second;
                }
                if (sum >= 2) {
                    for (int j = 0; j < M; j++) {
                        if (S[i][j] != '.') {
                            to_remove.insert({i, j});
                        }
                    }
                }
            }
        }
        
        // 列の確認
        for (int j = 0; j < M; j++) {
            if (col_types[j] == 1) {
                int sum = 0;
                for (const auto& pair : col_count[j]) {
                    sum += pair.second;
                }
                if (sum >= 2) {
                    for (int i = 0; i < N; i++) {
                        if (S[i][j] != '.') {
                            to_remove.insert({i, j});
                        }
                    }
                }
            }
        }
        
        // 削除対象がない場合、ループを終了
        if (to_remove.empty()) {
            break;
        }
        
        // 4. 削除対象のクッキーを除去
        for (const auto& pair : to_remove) {
            remove(pair.first, pair.second);
        }
    }

    // 5. 最終的に残ったクッキーの数を計算し、結果を出力する
    int result = 0;
    for (const auto& row : S) {
        for (char cookie : row) {
            if (cookie != '.') {
                result++;
            }
        }
    }
    cout << result << endl;

    return 0;
}

```