2005-07-02から1日間の記事一覧

Haskellでも書いてみた

メモライズと聞いては、Haskellを出さないわけには行かない。 いろいろやっているうちに30行を切った。 あの、苦戦したD問題がこんな小さなコードになってしまったよ。 実行時間は12秒ぐらいなので十分現実的なコードだろう。 import Control.Monad import D…

計算量評価

↑でちょっとあんまりな結果になってしまったので 大分取り乱してしまいましたが… 冷静になって計算量を評価してみる。 計算をキャッシュするテーブルが30*(2^8)=7680 それ一つを計算するのに必要な再帰的呼び出しの数=30*8=240 というわけで全体の計算量は18…

書いてみた

書いてみた。なにこれ?超簡単。 3時53分から書き始めて4時5分に完成。 12分だった。しかも、一箇所のバグもなし。 コンパイルもFirst Inputも一発通過。 なにこれ? 書いてる途中一回も迷わなかったし。 しかも実行速度超速い。 提出したやつ(-O3で) → 9秒 …

さらに追記

ありゃあ??? なんか、↑で別解を検討していたら思ったんですけど、 これってもしかして、 関数型プログラマである私が超超超得意とする 深さ優先探索+メモライズで解けちゃうですか? なんたるちあ。 いまから実装してみます。

D別解

本体サイトのほうで、D問題、馬券の使い方を固定してその8!に対して ダイクストラを最初に思いついたが、馬券を固定してのダイクストラが分からなかった、 見たいな事を書いたが、今さっき思いついてしまった。 ある地点までにある枚数を使ったその時点での…

国内予選

G〜N〜C〜、う〜ら〜め〜し〜や〜。 もとい。 うらやましい〜です。 もう、おめでとうとしか言えません。 問題数で負けてますからね。 今年はすでに各所で問題の考察が公開されていますが、 私も一応書いておきました。 (本体サイトのほうに。) E以外のソー…