反省会 AtCoder Grand Contest 029
いくつか紙に書いてみるべきだった
毎回WWWWBBBBのようになる
Submission #3806738 - AtCoder Grand Contest 029
signed main() {
string s = sin();
N = s.size();
int now = 0;
rep(i, N)
{
if (s[i] == 'W') {
cou += i - now;
now++;
}
}
cout << cou << endl;
return 0;
}
最大のペア数なので、二部マッチングか貪欲に選べるはず
書き出してみると、小さい数の方が相手が多いため、大きい数から貪欲に選んで良さそうだと見当がつく
実際、最大値の相手は高々1つしかないためこれでいいと分かる。
（最大値xでx+yが2冪の時、(x+y)/2 < x かつ (x+y)*2 > (x+x) のため）
Submission #3807197 - AtCoder Grand Contest 029
signed main() {
cin >> N;
addAll(A, N);
vi beki = {1};
rep(i, 33) beki.pb(beki[i] * 2);
umap<int, int> map;
rep(i, N) map[A[i]]++;
rsort(A);
rep(i, N) {
int su = upperBound(beki, A[i]);
int aite = su - A[i];
if (map[aite]) {
if (--map[aite] >= 0 and --map[A[i]] >= 0) {
cou++;
} else {
map[aite]++, map[A[i]]++;
}
}
}
cout << cou << endl;
return 0;
}
文字を数字で扱うとわかりやすい
毎回可能な限り小さい文字列を使うべきで
長さが伸びる場合は、末尾に000をつけ
縮む場合は、いらない部分をカットして末尾を1増やせばいい
上の処理は最終的な文字種がわかっていれば一意に出来るので二分探索を使う。
mapを使えば0の部分を持たなくてすみ、インクリメントは高々N回しか行われないため、時間の掛かりそうな要素の削除もN回程度しか行われない
文字種が1の場合、10^9回繰り上げ処理が行われることに注意
Submission #3817239 - AtCoder Grand Contest 029
bool calc(int x) {
if (x == 1) {
rep(i, 1, N) {
if (A[i - 1] >= A[i])return false;
}
}
map<int, int> map;
rep(i, 1, N) {
if (A[i - 1] >= A[i]) {
map.erase(map.lower_bound(A[i]), map.end());
rer(j, A[i] - 1) {
if (map[j] < x - 1) {
map[j]++;
brk;
} else {
map.erase(j);
if (j == 0) {
return false;
}
}
}
}
}
return true;
}
signed main() {
cin >> N;
addAll(A, N);
int ok = INF, ng = 0;
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (calc(mid))ok = mid;
else ng = mid;
}
cout << ok << endl;
return 0;
}
高橋くんは止まれない（新作マンガ）
列iで終わる場合の答えはoo。という風に考え、複雑にしてしまった。
解法が思いついても、1つぐらい紙に書き、考えを整理するべきだと反省した。
そうすると、各行につきどの列まで行けるかを持ちたくなり、素直に解ける。
Submission #3817239 - AtCoder Grand Contest 029
vi hw[2 * k5];
signed main() {
cin >> H >> W >> N;
umap<P, int> map;
rep(i, N) {
int a, b;
cin >> a >> b;
a--, b--;
map[{a, b}] = 1;
hw[a].pb(b);
}
rep(w, W + 1) {
map[{H, w}] = 1;
hw[H].pb(w);
}
rep(h, H + 1) {
map[{h, W}] = 1;
hw[h].pb(W);
sort(hw[h]);
}
if (map[{1, 0}])fin(1);
int r = 0;
rep(h, 1, H) {
if (map[{h, r + 1}] == 0)r++;
if (hw[h + 1][0] <= r)fin(h + 1);
}
return 0;
}
今回の反省点
Aが解けなかったのはひどすぎる。
処理の結果を紙に描いて法則を考えましょう。
とりあえず二分探索
マッチングは貪欲かもしれない
処理が思いついても複雑な場合、紙に描いて分かりやすく捉え、細かく考える
