解け無さすぎて一月置いてやっとAC取れた。
問題文
H - Grid Eraser
考えること
操作系の問題なのでまずは操作の順番について考えてみます。
行、列の削除の順番は関係あるか？
この問題について考えてみる時、ある操作について獲得可能の総ポイントが減ってしまうことが起こりうるかどうかについて考えます。
この問題において、そのような場合は見つから無さそうです。
よって、削除の順番については関係無いので、まずは消せる所から消す愚直をすれば、(どれだけの時間がかかるかは不明ですが)、解答を導くことが出来ます。
愚直の計算量について考察する。
行と列足してH+Wから探索します。H+W回H+Wについて探索するのでこの時点で
$$
\mathcal{O}((H+W)^2)
$$
です。これは削除済の部分も再度検索されると考えると、等差数列の和から導ける。
次に、行の探索中はW回、列の探索中は一回あたりH回の探索が入るので、結果
$$
\mathcal{O}((H+W)^2)H + (H+W)^2W)
= \mathcal{O}((H+W)^3)
$$
となる。(解説見ながら考えてみたけど、なんか違う気もする、わからん・・・)
解説 - UTPC 2020
高速化について考える
各行と各列の黒マス数と、現在の行数、列数について管理する、
そうすると、ある行、列に対して削除の判定が$\mathcal{O}(1)$になる。
ここで、削除をする際は現在の行数、列数の情報を変更するだけで良いのでこれで、削除を表現出来る。
これにより、計算量は
$$
\mathcal{O}((H+W)^2)
$$
となる。
解く
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
#include <bits/stdc++.h>
#define INF 1e9
#define INFLL 1ull<<60u
using namespace std;
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a) (a).begin(),(a).end()
#define endl "\n"
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using vpii = vector<pair<int,int>>;
void solve() {
int H,W; cin >> H >> W;
vector<string> vs(H);
REP(i,H) cin >> vs[i];
// 各行の黒マスの数、各列の黒マスの数
vector<int> blackH(H,0),blackW(W,0);
REP(i,H) REP(j,W) {
if (vs[i][j] == '#') {
blackH[i]++;
blackW[j]++;
}
}
int cnt = 0;
vector<bool> deleted(H+W,false);
// 現在の行数と現在の列数
int nowH = H, nowW = W;
// 黒マス0で消した行数、黒マス0で消した列数
int deleteWhiteH = 0, deleteWhiteW = 0;
REP(_,H+W) {
REP(watch,H+W) {
if (deleted[watch]) continue;
// 削除された行と列
int deletedH = H - nowH;
int deletedW = W - nowW;
if (watch < H) {
// 行について探索
// 実質黒マスが0 or nowWなら削除
// 実質黒マスが0なら削除
bool flag1 = blackH[watch] - deletedW + deleteWhiteW == 0;
// 実質黒マスが残り行数と一致なら削除
bool flag2 = (blackH[watch] - deletedW + deleteWhiteW) == nowW;
if (flag1 || flag2) {
deleted[watch] = true;
// 現在の行数を減少
nowH--;
cnt++;
if (flag1) deleteWhiteH++;
// cerr << "deleted row: " << watch << " flag: " << (flag1 ? 1 : 2) << endl;
}
} else {
auto w = watch - H;
// 列ついて探索
// 実質黒マスが0 or nowHなら削除
// 実質黒マスが0なら削除
bool flag1 = blackW[w] - deletedH + deleteWhiteH == 0;
// 実質黒マスが残り行数と一致なら削除
bool flag2 = (blackW[w] - deletedH + deleteWhiteH) == nowH;
if (flag1 || flag2) {
deleted[watch] = true;
// 現在の行数を減少
nowW--;
cnt++;
if (flag1) deleteWhiteW++;
// cerr << "deleted column: " << w << " flag: " << (flag1 ? 1 : 2) << endl;
}
}
if (nowH == 1 || nowW == 1) {
if (nowW * nowH == 0) {
cout << 1 << endl;
return;
}
cnt += max(nowH,nowW);
cout << cnt << endl;
return;
}
}
}
cout << cnt << endl;
}
int main() {
solve();
return 0;
}
|
提出 #22070815 - UTPC 2020