なんとな~くしあわせ?の日記

「そしてそれゆえ、知識そのものが力である」 (Nam et ipsa scientia potestas est.) 〜 フランシス・ベーコン

アルゴリズム

SoundHound Inc. Programming Contest 2018 - (Ordinary Beauty) 再考

問題 考えたこと 方針 期待値の線形性を利用して数列の美しさの算出を分解する 例 問題 d = 0の場合と d != 0の場合で場合分けする 解答コード 問題は単純なのだが、解法が全然思いつかず。 問題 C - Ordinary Beauty N, M, D が与えられるとき 1 ~ N まで…

AtCoder - AtCoder Beginner Contest 066 (11) を解いてみた

組み合わせ 組み合わせを階乗の式で表す 組み合わせの式 ABC 066 (11) 、解説の解説 問題の考察ヒント 考察 簡単な例 重複を取り除くパターン ABC 040 D問題に使われるアルゴリズム要素は組み合わせ、繰り返し2乗法、階乗のmod逆元、(+累積和的な処理?)…

ゼロから始める動的計画法 - コイン問題

問題設定 Project Euler Problem 31 考察 動的計画法による解答 問題を簡単にする なぜ動的計画法か? まずは2次元配列で Rubyのコードに落とし込む プロジェクトオイラー用に微調整 問題設定 Project Euler Problem 31 ターゲットとする問題は以下 Project…

アルゴリズムまとまってるサイト

メモ用、他にあれば追記する ポータルサイト 英語読めれば大抵の典型問題に関する示唆が得られる 数学問題に対抗するために 大学の授業シラバス系 個人サイト ポータルサイト 英語読めれば大抵の典型問題に関する示唆が得られる www.geeksforgeeks.orgwww.cs…

AtCoder - AtCoder Beginner Contest 040 (道路の老朽化対策について) を解いてみた

アルゴリズム 経路圧縮 rankによる木のマージ処理 ABC 040 D問題に使われるアルゴリズム要素はUnion-Findです。Union-Find自体は前回ブログ記事にしていたのですが…これだけでは足りませんでした。ACするためには経路圧縮とrankによる木のマージ処理が必要で…

動的計画法で組み合わせの総数 nCr を求めてみる

もっと早い組み合わせの総数 (combination)の求め方 動的計画法 - DP(Dynamic Programming) Combinationのための動的計画法 Rubyによるサンプルプログラム 処理内容を表で表現してみる 実際使う時は 参考 もっと早い組み合わせの総数 (combination)の求め方 …