昨日のAtCoder Grand Contest 043でB問題を解いて２完できた。うれしい。
水色コーダーには望外で僥倖だ。
https://atcoder.jp/contests/agc043/tasks/agc043_b
僕は稀にこの手の青難易度問題を解いてしまうことがある。そのテクニックを紹介しよう。
やること
- 愚直解を書く
- テストケースを自動生成するコードを書く
- For文で小さいケースから順番に全部試す
- プリントする
昨日のB問題は8桁くらいを一瞬でprintできる。
この手の問題は絶対に簡単な規則性があるので、ずーと眺めていたら何か見つかるかもしれない。
昨日の問題は、「２段目以降は、nが偶数ならトーナメントにして解いても同じ結果になる」ということに気づいた。愚直解なら１段につき1要素しか減らないのでo(n^2)になってTLEだが、トーナメントにして１段を半分にしていいならo(log n)になるのでACできる。ということは、あとはnが奇数の時だけ考えればいい。奇数の時も簡単だ。１段を愚直解すれば長さが偶数になる。
// 一段減らす
vector<int> sub(vector<int> &v) {
if (v.size() == 1) return v;
vector<int> v2(v.size() - 1);
rep(i, v.size() - 1) {
v2[i] = abs(v[i] - v[i + 1]);
}
return v2;
}
// 半分にする
vector<int> tournament(vector<int> &v) {
vector<int> next;
for (int i = 0; i < v.size(); i += 2) {
int a = abs(v[i] - v[i + 1]);
next.push_back(a);
}
return next;
}
// 偶数なら半分にする
// 奇数なら一段減らしてから半分にする
int solv(vector<int> v) {
while (v.size() != 1) {
if (v.size() % 2 == 0) {
v = tournament(v);
} else {
v = sub(v);
}
}
return v.front();
}
提出前にすること
「多分解けたな」と思ったら、せっかくなのでさっき作ったテストケース自動生成コードを使って確認してほしい。小さいサンプルで、愚直解と同じ結果になるか試すのだ。結構地味なコーナーケースを検出することがある。大体こういう問題はnが極端に小さい時に例外がある。昨日の問題なら2231の時だけこの方法ではうまくいかないことが検出できた。小細工をして通した。逆に言えば、nが小さいケースを全部通せたらだいたいACできる。
その他
愚直解も実装が複雑な問題であれば、TLEになることが分かっていても愚直解をジャッジに投げてほしい。その勇気も必要だ。ペナルティはたかが５分だ。間違った愚直解で時間を失うよりましだ。
おススメ
このブログに感化された緑・水色コーダーの方は、ぜひこのやり方でこの問題を解いてみてほしい。
頭で考えるとめちゃくちゃ難しい問題だが、小さいケースからprintしていけば超簡単だ。
https://atcoder.jp/contests/abc059/tasks/arc072_b
