問題
既存投稿一覧ページへのリンク
雑記
一見、簡単に見えたんですよ。でも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枚以上ある行や列を素早く特定できる。
クッキーの除去操作を繰り返し、最終的に残ったクッキーの枚数を計算する。
解法手順
-
入力データを受け取り、初期状態を設定する。
- クッキーの配置を2次元リストSに格納する。
- 各行、各列におけるアルファベットの出現回数をカウントする。
- 各行、各列に存在するアルファベットの種類数を記録する。
-
クッキーの除去処理を行う関数removeを定義する。
- 指定された位置のクッキーを除去し、関連するカウンタを更新する。
-
メインのループ処理を実行する。
- 各行で、アルファベットの種類数が1かつ列数が2以上の場合、その行を削除対象とする。
- 各列で、アルファベットの種類数が1かつ行数が2以上の場合、その列を削除対象とする。
- 削除対象の行と列がない場合、ループを終了する。
-
削除対象の行と列に対して、removeを呼び出してクッキーを除去する。
- 残りの行数と列数を更新する。
-
最終的に残った行数と列数の積を計算し、結果を出力する。
TLEコード(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++)
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;
}