SRM 498 DIV1 参加記録

はてなグループ閉鎖に伴い移行。
Practice では解けるのに、本番ではなぜか一度も正解できていない DIV1。参加前レートは 1205。
どうせ落ちるんだから……くらいのつもりで気楽に参加。

1 250 FoxSequence

方針

問題読む。把握把握。

a, b, c, d を全部試しても 50 ** 4 = 625万だし(実際は大小関係があるからもっと少ない)、
総当たりで解けるはず。

実装

実装。等号がついたりつかなかったりに気をつけて慎重に。

サンプル通る。submit 前に確認。

あ、等差数列ということしかチェックしてなかった。
これだと3,2,1,2,3,3,4,5,4みたいなのもYESになってしまう。
サンプルケース不親切だなぁ(→ こういうとんでもない勘違いするのは私くらいか……)

修正して submit

一応、3,2,1,2,3,3,4,5,4みたいなケースを作っておく。

2 450 FoxStones

450 だし、これも解けちゃったりしてと欲を出す。

方針

問題読む。把握。

サンプルケース眺める。これは、一部の部分が交換されてるだけだなぁ。
そうか、各点からの距離が等しいやつらをグループにして、そのなかで
permutation。その組み合わせの積だ!

計算量は、えっと、全ての点 200x200 = 4万 について、全てのマーク地点 50個との
距離を求めるわけだから、十分だよね。

実装

「全ての点 200x200 = 4万 について、全てのマーク地点 50個との距離」を覚えておくには
map だけど、map のインデックスって、int [50] みたいな配列もアリ?

書いてみる。なんかエラーになった。vector <int> に変更。コンパイルできた。
全ての点 200x200 = 4万 だから、shortでいいや。

あとは、階乗を求めて掛けるだけ。階乗をメモする必要は……掛け算はせいぜい40000回だから
不要。あと、最後の計算は long long にしておくのを忘れない。

コンパイル。サンプルケースの最後のほうでWA。
あ、階乗の計算の中も long long にしておかないとダメか。

修正。サンプルケース通った。提出。

Challenge Phase

なんと2問も解けてしまったぞと調子に乗るが、同時に、「どうせバグ残ってるんだろうなぁ」と弱気。

他の人のを見ていく。さすがに DIV2 と違って「見た瞬間に分かる」ミスはない。

あれ? なんで 250 でみんな N の数チェックしてるの? ゲ、N = 1 の場合あるのか……
やばい。

でも、まてよ、自分のは、

for (int i = 1; i< seq.size() - 3; i++) { // 実は signed が必要!!!
 ...
}
return "NO";

みたいな感じでループ回してるから、N = 1 の時はループ入れずに、いきなり return "NO"
に飛ぶからいいんじゃない? 助かった。

……と思ってたら、落とされた。なぜ?????

結果

250 challenged; 450 passed system test で、1205→1270。

考察

{1} で落とされたらしい。gdb で調査する。

そうか、vector::size() は unsigned な値を返すから、 1 - 3 = -2 になるんじゃなくて、
すごく大きな数になってしまって、ループが回っちゃうのか。

最近、オーバーフローは前もってチェックするようになったけど、unsigned でマイナスに
なるのは全く考えていなかった。普段、わざわざ unsigned なんて使わないしなぁ。

教訓: 「size() は unsigned を返す! アンダーフローに注意」

他の人のコードで勉強。for (int i = 1; i < seq.size(); i++) でループ回せばいいのか。どうせ内側のループが回らないだけだから。あるいは、階差数列を作っておいて、STL の unique でもいいらしい。STL の uniq は Ruby の Array#uniq と違い、隣接した同じ要素しか消さない。