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

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

アルゴリズム

プロジェクトオイラーProblem 12を解いてみた

今回はほとんど自力では解けてないので、翻訳実装しただけです。 問題 三角数の数列は自然数の和で表わされ, 7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である. 三角数の最初の10項は: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... となる. 最初の7項に…

AtCoder Beginner Contest 009 (辞書式順序ふたたび) を解いてみた

ABC 009 C問題に使われるアルゴリズム要素は貪欲法です。貪欲法自体は定型のアルゴリズムがあるわけではないので、知識ではなく地頭を問う問題です。 C - 辞書式順序ふたたび 解説:Abc009 問題文 文字列Sとその長さN、そして入れ替えしていい文字数Kが与え…

Neo4jでグラフアルゴリズム

前から調べようと思っていたNeo4jの勉強会に行ってきた。 jp-neo4j-usersgroup.connpass.com グラフアルゴリズム AOJ - 深さ優先探索 データセットの用意 ビジュアライズ アルゴリズム実装 グラフアルゴリズム とりあえず深さ優先探索、幅優先探索、ダイクス…

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)の求め方 …