SRM466

TopCoder

仮眠も取って万全のコンディションで望んだ。
・・・はずなのに。

250 LotteryCheating

  • 全探索しか思い浮かばない。
    • 約数が奇数個とか結構良くありそうな気がする。
    • 答えが大きくなるような入力はないのでBFSで間に合う、ということではないだろうか。
  • ・・・
  • 分からないのでBFS書いてから考えよう。
  • ・・・
  • 書けた。サンプル普通に通った。
  • でかいケース入れてみよう。 "1234567890" っとな。
    • 死ーん。
  • ・・・どうしろというのだろう。
  • ・・・
  • ・・・
  • ・・・
  • ・・・
  • ・・・
  • ・・・
  • ・・・？
int divisorCount = 0;
for(int i=1;i*i<=n;++i){
  if(n%i==0){
    if(i*i==n) divisorCount++;   // <- !
    else       divisorCount+=2;  // <- !
  }
}
  • 平方数のときだけじゃん！
    • うわぁぁぁばかばかばかばかぁぁぁ！
  • ごりごりと一番近い平方数までBFSするように書き換える。
  • もっかい最大ケースっと。
    • 死ーん。
  • ・・・
  • ・・・BFSする必要ねぇ！違ってる桁の数を数えるだけだよ！
    • Edit Distanceとは違うんです！
  • ついにできた。もちろん最大ケースも出てきた。
  • submit.
    • このままだと30%ルールに引っ掛かりますよって？
    • BFSと約数カウントの残骸を消した。
  • 今度こそsubmit.

500 LotteryPyaterochka

  • DP臭い。
  • dp[n][s] := n列決まって当たりの数字をs個使った状態の確率、でいけるのかな。
  • 書いたけどsample合わないまま終了。

Challenge Phase

  • 平方数に一瞬で気付いた人がそんなに多いはずがない！
    • みんなBFSしてるに違いない！
  • と思ったけどぜんぜんいない・・・。
    • 一人いた。迷わず撃墜。
  • なんか妙なif文入れている人もいる。これは撃墜できるのでは？
  • ・・・自分のが間違ってる！
  • 桁数の小さい平方数にするのはいいけど、より大きな桁数の平方数にするのはダメだ・・・。
    • '48576' は2が正しいはずなのに 1 ('1048576' = 1024^2) が出てしまうことを確認。
    • 0完確定。
  • 気を取り直して同じミスしてる人を探そう。
    • 残り1分では見つけられませんでしたとさ。

System Test

  • 見なくても分かってる。
  • けど意外と250で落ちる人が多かったのは意外だった。
    • どこが間違ってたんだろう？

Result

  • xxx +50 50.00
  • 1380 -> 1373
  • 私のスキルで飯は食えますか？