はてなグループ閉鎖に伴い移行。
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 と違い、隣接した同じ要素しか消さない。