AtCoder が提供しているABC（AtCoder Beginner Contest）346 のE問題をC++とPythonで解いてみました。ABC346は、2024年3月23日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Paint（Difficulty : 1053）
問題はリンク先をご覧ください。
操作を逆に考えることによって解くことができます。AtCoder Problems による Difficulty は 1053 でした。
解答案
操作を逆に考えます。以下の順に処理していきます。
- 行の場合（Ti＝1）
- すでにその行が塗られていた場合は、この操作は無視する。
- 指定された色のマスの個数を増やす。
- 増やす個数は、行の個数（W）から、この後に塗られる（先に処理されている）列の数を引く。
- その行を塗られていることに更新して、その行を使われていると印をつける。
- 列の場合（Ti＝2）も行と列を入れ替えて同様に処理していきます。
C++ プログラム例（ABC346E）
上でまとめた処理をするために以下のコンテナを用意します。
- その色で塗られている個数を記憶する map コンテナ color：色番号と個数を組で管理します。
- ある行または列が、どの色で塗られているか記憶する vector コンテナ color_h または color_w：初期値は-1で、塗った色を記憶します。操作の逆順に処理するため、このコンテナの値は、一度しか更新しません。
- すでに塗られている行または列を記憶する set コンテナ used_h または used_w：色が塗られた行または列を格納していきます。color を更新する場合に、このコンテナの個数を使います。
上で確認した順番に処理していきます（25ー39行目）。すべて処理できたら、初期値の0になっているマスの個数を求めます。注意は、色0で塗られる場合もあることです。また、コンテナ color に格納するとき（29、36行目）に、結果が0になっていることもあります。このため、1個以上の値を持つ色番号の個数を size として求めておきます。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ll h, w, m;
cin >> h >> w >> m;
vector<ll> t(m);
vector<ll> a(m);
vector<ll> x(m);
for (int i = 0; i < m; ++i) {
cin >> t[i] >> a[i] >> x[i];
--a[i];
}
map<ll, ll> color;
vector<ll> color_h(h, -1);
vector<ll> color_w(w, -1);
set<ll> used_h;
set<ll> used_w;
for (int i = m - 1; i >= 0; --i) {
if (t[i] == 1) {
if (color_h[a[i]] != -1) {
continue;
}
color[x[i]] += w - used_w.size();
color_h[a[i]] = x[i];
used_h.insert(a[i]);
} else if (t[i] == 2) {
if (color_w[a[i]] != -1) {
continue;
}
color[x[i]] += h - used_h.size();
color_w[a[i]] = x[i];
used_w.insert(a[i]);
}
}
ll color_0 = h * w;
for (auto e : color) {
if (e.first != 0) {
color_0 -= e.second;
}
}
color[0] = color_0;
int size = 0;
for (auto e : color) {
if (e.second != 0) {
++size;
}
}
cout << size << endl;
for (auto e : color) {
if (e.second != 0) {
cout << e.first << " " << e.second << endl;
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC346E）
Python 版も基本的な考え方は同じです。連想配列は、defaultdict を使いました。defaultdict は順序がないため、リスト keys に対象を格納してソートして出力しました。以下となります。
"""AtCoder Beginner Contest 346 E"""
from collections import defaultdict
h, w, m = map(int, input().split())
t = [0] * m
a = [0] * m
x = [0] * m
for i in range(m):
t[i], a[i], x[i] = map(int, input().split())
a[i] -= 1
color = defaultdict(int)
color_h = [-1] * h
color_w = [-1] * w
used_h = set()
used_w = set()
for i in range(m - 1, -1, -1):
if t[i] == 1:
if color_h[a[i]] != -1:
continue
color[x[i]] += w - len(used_w)
color_h[a[i]] = x[i]
used_h.add(a[i])
elif t[i] == 2:
if color_w[a[i]] != -1:
continue
color[x[i]] += h - len(used_h)
color_w[a[i]] = x[i]
used_w.add(a[i])
color_0 = h * w
keys = []
for key, value in color.items():
if key != 0 and value != 0:
color_0 -= value
keys.append(key)
if color_0 != 0:
color[0] = color_0
keys.append(0)
keys.sort()
print(len(keys))
for key in keys:
print(key, color[key])こちらも「AC」と判定されました。
最後に
コンテスト中に、このE問題を解くことができました。E問題が解けるとうれしいです。
引き続き ABC の問題を紹介していきます。
