isyumi_netブログ

isyumi_netがプログラミングのこととかを書くブログ

サンプル自動生成力があれば時々青問題が解ける

昨日のAtCoder Grand Contest 043でB問題を解いて2完できた。うれしい。
水色コーダーには望外で僥倖だ。

https://atcoder.jp/contests/agc043/tasks/agc043_b

僕は稀にこの手の青難易度問題を解いてしまうことがある。そのテクニックを紹介しよう。

やること

  • 愚直解を書く
  • テストケースを自動生成するコードを書く
  • For文で小さいケースから順番に全部試す
  • プリントする

昨日のB問題は8桁くらいを一瞬でprintできる。

この手の問題は絶対に簡単な規則性があるので、ずーと眺めていたら何か見つかるかもしれない。

昨日の問題は、「2段目以降は、nが偶数ならトーナメントにして解いても同じ結果になる」ということに気づいた。愚直解なら1段につき1要素しか減らないのでo(n^2)になってTLEだが、トーナメントにして1段を半分にしていいならo(log n)になるのでACできる。ということは、あとはnが奇数の時だけ考えればいい。奇数の時も簡単だ。1段を愚直解すれば長さが偶数になる。

 

// 一段減らす
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になることが分かっていても愚直解をジャッジに投げてほしい。その勇気も必要だ。ペナルティはたかが5分だ。間違った愚直解で時間を失うよりましだ。

 

おススメ

このブログに感化された緑・水色コーダーの方は、ぜひこのやり方でこの問題を解いてみてほしい。
頭で考えるとめちゃくちゃ難しい問題だが、小さいケースからprintしていけば超簡単だ。
https://atcoder.jp/contests/abc059/tasks/arc072_b