週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

夜1時から開始。前回が凄惨だったので失ったratingを取り戻しに来ました。

とは言ったものの、明らかに眠かったです。もう400 pts の問題が全然読めませんでした。 なかなか問題が意味不明だったし。とりあえず250 ptsと400 ptsを解いて、1000眺めてたら時間終了していました。解いた問題でも、一番重いケースやコーナーケースを全然試していません。さらにChallenge Phaseではもう寝てました。

朝起きたら部屋二位。かなりの人が400 ptsをSystem Testで落としていました。どんなコーナーケースがあったのでしょう。とりあえずratingは半分以上取り戻しました

前回があまりにもひどかったので、まじめに復習して次回に備えることにしました。

しかし75分で解けたのは250点と500点だけ。両方ともSystem Testは通りました。1000点は時間内にテストケースを通すことができませんでした。まだSystem Testを通すプログラムができていません。

250点は瞬殺で242.16点。500点は解けたはずなのにはまりました。メモ化して探索するのですが、

int search_impl(args) {
  if (outOfDomain())
    return 0;
  // snip;
}
int search(args) {
  int& memo = table[args];
  if (memo<0)
    memo = search_impl(args);
  return memo;
}
と書いて、tableが配列で、argsにoutOfDomainとなる負の値を入れて領域外アクセスをしてしまいました。テストケースが通らないので気付きましたが。

1000点は本番ではスルーした最大流問題です。解きかたは上位の解答を見て把握したものの、最大流なんてしばらく書いていないので酷いことになりました。 そもそもICPC現役のときも最大流はChunにまかせていたような気もしますが。 いまだに計算時間が遅く、もっとも大きいテストケースでこけます。

追記:計算量の問題ではありませんでした。よく調べたらdfsがバグって無限ループしていました。

ところで、Practice roomの1000点解答があまりに酷いので撃墜しておきました > shinhさん

仕事を切りあげて18時から参加したら爆死。-50点ですよ-50点。250と500とをSystem Test failedしたうえにChallengeを二回失敗しました。

250点はO(N^3), N=1000で計算がまにあうんですね。目測を誤って難しいプログラムを書いてしまいました。時間がかかりまくった上に、最終的には、a,b,c自体は1000を超えることに気付いていませんでした。さらにO(N^3)でまにあうことに気づいていなかったのでO(N^3)にChallengeしてペナルティーをもらうというありさま。

500点は探索関数をMemo化すればよいことに気づきませんでした。ほかの方法で枝刈りをしまくって時間短縮させたところ、結果的に(おそらく)枝刈りを間違えて失敗しました。


4月27日追記: 500点はTLEでした。オーダーの壁がありました。復習

250点問題のみ + 1 challenge failure:(

500点は p(n, r) = 1^r + 2^r + ... + n ^r (mod 1000000007)を求めるだけ。Bernolli Polynomialsは初めて聞きました。 しかし、冷静に考えると地道に公式を導出する方法が書けた気がします。p(n, r)をnのr+1次の多項式として、その係数を求めます。p(n, r') (r'<r)さえ求まっていればあとは適当にやれば解けます。係数が分数になるところは、modの逆数を掛けるのが正解です。本番では係数をどう保存していいのかわからなかったのでこの方法はとれませんでした。

今問題を読んでいます。まだ解法はわかっていません。解法以前に間違った実装を大量に思いつきます。

  • ランダムな都市からランダムな都市にゆける確率と勘違いして、sample 0を 63/64にしてみる。
  • いちばん通りにくい2都市を通れる確率で十分と思って、sample 2を 1/121にしてみる。

どれもsampleで検出できるのが親切。

ところでsample 3の1.0000000000000002ってふざけてるの。

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。