幅優先探索★3．初の幅優先探索の実装で，queueを使うことまではうっすら知っていましたがどう書けばいいかわからず・・下のリンクを参考にしました．というか自分のソース見ると結果的にほぼパクリです．なので今回はgistはなし．stack9996さんありがとうご…

全探索★3．自力でなんとか再帰が書けた記念． タグはbfsでしたが，dfsしか書き方知らないので今回はdfsで． ループを作るので逆走する動作を封じるために直前の方向を記憶する再帰を書きました． bfsじゃないと解けない問題とかスタックを使わないとオーバー…

DP★3．検証からデバッグまでに3時間ほどかけてしまった・・ まずiさんとjさんが(順調に勝ち上がれば)何試合目にあたるかを求める関数(digit)を作り，あとはM周分の勝率を積算するDPを書きます・・自分でも何言ってるのかわからなくなってきた．int型のビット…

DP★3．やっと自力でACできた記念． まず通常攻撃が必殺技より強ければ通常攻撃だけしていれば良い． そうでない場合： 敵のHP: hを削るのに必要な最小の手数の期待値をとすると， まずにおいて 次ににおいて それより大きい値に対しては 結構単純なので実質…

★3 DP派生．無駄に3時間くらいかかりました・・ 要約すると9以下でを作る方法の数を答えればいいので， でOKだろうと思ったら実は違っていて111111円を1円玉111111枚でも表現可能なことを忘れていた．ということでDPで求めたfの階差が答えでした． 結局自力…

DP，ネタはわかっていてもどうDP化するのかがかなり難しい．結局これも解説見てタネがわかっている状態で実装しました．． 今回は一発でAC．-1の判定が結構雑だけれどまあ今回は本流とは関係ないということで． yukicoder No.247 自分でもよく理由はわからな…

何度もWAが出て途方に暮れていたがdpをmainの外側に出したらACになった． 追記：dp[20000]とmainの中に書いたらACだったのでマクロ関連の挙動が原因だと思われる． 追々記：マクロが原因ではなく，初期化を忘れていたのが原因だった．イージーミスに気づかず…

DP基礎．ナップサック問題実装危うし．AC出すまでかなり時間かかった． yukicoder No.4

愚直に順列・組み合わせ・重複組み合わせを求める問題．だが簡単ではない ※：PRIME = 1000000007は素数 詰まったところ a modpの逆元を求める部分．a^(p-2) = a^(-1)まではわかったのだが，それをO(PRIME)で書いてしまったところ．指数の偶奇で場合分けして…

深さ優先探索の練習に解きました． 自力でdfs書いたの多分初めてじゃないかな・・ 汚いけどなんとか思い通り動いてくれました． yukicoder No.157

今の時点でのC++用テンプレートを書いておきます．色々とまだまだ工夫の余地があるはず（痒いところに手が届かない） IDEはXcode6.4を使っています． AtCoder C++ MyTemplate 速く解答する価値がかなり高いのでこういうのもできる限りメンテナンスしたいとこ…

今までは興味本位で競技プログラミングに数回出たくらいで，アルゴリズムの知識の蓄積があるわけでもなく長続きしていませんでしたが，この歳になって必要性が見えてきました．とにかく続けることを第一の目標にしたいと思います．記事を書けばモチベーショ…