1957年,Bellmanによって提案された多変数最適化問題を解くための手法. 目的関数に再帰性 (可分性) と単調性があり,制約式が逐次的であるとき,原問題をある部分問題群に埋め込んで,各部分問題の最適値を定義し,相隣る問題の最適値間の関係式 (再帰式) を導く.これを逐次解いて,最後に与問題の最適解を求める方法である.解法の効率化のためには,決定変数,状態変数,評価関数などの選択・設定に個々の創意工夫を要する.
(「OR用語辞典」より)
*リスト::数学関連
参考にさせてもらった元記事↓ 動的計画法超入門! Educational DP Contest の A ~ E 問題の解説と類題集 - Qiita 元記事を見た前提で、C#を使ってDP_A - Frog1を解いていきたいと思います。 まず、DPのテンプレートとして紹介されているchmax,chminをC#で実装した例を紹介します。 public bool chmin<T>(ref T a, T b) where T : IComparable { if(a.CompareTo(b) > 0) { a = b; //aの参照元に直接bを代入 return true; } return false…
アルゴ式のテスターに応募したらなんと選ばれちゃいました. note.com 現状 アルゴ式の取組状況はこんな感じ. ちなみにAtCoderの色は茶色(2021/10/11)highestは847(緑) なお,大学院まで数学専攻ですがもう10年以上経っていますし,なんなら位相幾何学専攻でしたので競プロに役立つとされる整数分野は高校では未履修です(たぶん).でも高校数学は割とできます. 今後 TwitterのDMによるやり取りで,興味ある分野をDPと申告したので,とりあえずDPのコンテンツに取り組んでみて,進捗報告をしていくことになりました. AtCoderのEDPCも途中で挫折してしまっています…
AtCoder版!蟻本の貪欲法の例題としてあげられているAOJ Coin Changing ProblemをPythonで解いていきます。 (function(b,c,f,g,a,d,e){b.MoshimoAffiliateObject=a;b[a]=b[a]||function(){arguments.currentScript=c.currentScript||c.scripts[c.scripts.length-2];(b[a].q=b[a].q||[]).push(arguments)};c.getElementById(a)||(d=c.createElement(f),d.src…
こんにちは。paizaラーニングでコンテンツ制作をしている学生スタッフの工藤です。みなさん、「DP(Dynamic Programming、動的計画法)」って知っていますか?DPは代表的なアルゴリズムのひとつで、競技プログラミングの問題を解く際にも多く用いられます。そのため耳にしたことはあるかもしれませんが、慣れるまでは扱いが難しく実用性が分からないという方も多いと思います。ただし、ある程度問題を解いていくとパターンのようなものが見えてくるはずなので、たくさん問題に触れてみるのがおすすめです。そこで今回は、paizaラーニングのレベルアップ問題集に追加された「DPメニュー」を使って、DPの問題…
動的計画法の練習のために、簡単な問題を解きます。 動的計画法は、まだまだ使いこなせてないのですが、使って解けた時はとてもスッキリするので、好きなテクニックのうちの1つです。 色々とパターンはあるのですが、基本的には漸化式で問題を表現して、計算結果を配列に記録して、その結果を使いまわして解くようなイメージです。最初なので動的計画法に分類しても良いのかどうかと思うくらい簡単な問題からいきます。https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_A&lang=ja整数Nが与えられて、そのN項目のフィボナッチ数列を求める…
今日も "初中級者が解くべき過去問精選 100 問" を解いていきたいと思います! 精選100問って何? 過去の記事についてはこちら!! 第1回:全列挙 第2回:工夫して通り数を減らす全列挙 第3回:ビット全探索 第4回:順列全探索 第5回:二分探索 第6回:深さ優先探索 第7回:幅優先探索 動的計画法:ナップザック DP 34. Fibonacci Number 35. 0-1 Knapsack Problem 36. Knapsack Problem 37. Coin Changing Problem 38. Longest Common Subsequence 最後に 精選100問って何…
問題 E - Queen on Grid 行列のマス目がある。左上のマス目をとして、上から番目、左から番目のマス目をマスとする。1手ごとに、そのマスから下、右、右下方向の好きなマスに移動できる。ただし、障害物に移ったり、障害物をを飛び越える移動や、マス目の外に出る移動は許されない。マスに移動する方法は何通りか? 初手の考察 素朴な遷移式 マス目にいく方法をとする。マス目について、左、上、左上方向のそれぞれで最もに近い障害物のある座標をとする。遷移式は となる。 実装 メモ化再帰で実装します(思考停止)。 結果 落ちます。 考察をやり直す という値を定義します。こうすると、遷移式は、 です。それ…
はじめに Pythonで実装しました.そんなところで差が出るなんて,,,という学びがあったので記事にします. 問題 ABC123 C - Typical Stairs 考え方 いわゆるDPの基本的な問題なのだとおもいます.フィボナッチ数列と同じです. 1歩または2歩進めるとうことは,N段目に到達する方法はN-1段目から来る,またはN-2段目から来るの2通りです.したがってdp[N]をN段目に到達する方法とすれば, dp[N] = dp[N-1] + dp[N-2] と表すことができ,これはフィボナッチ数列の一般項と同じです.ここに壊れている床は使えないという条件を加えてやればACとなります. …
今回もEDPCをPythonで解いてみようと思います。 DとE問題が似ていましたので合わせて記事にしました。参考にした記事はこちらです。勉強になります。 動的計画法超入門! Educational DP Contest の A ~ E 問題の解説と類題集 - Qiita EDPC D - Knapsack 1 D - Knapsack 1 問題文 N個の品物があります。 品物には1,2,…,Nと番号が振られています。 各i(1≤i≤N) について、品物iの重さはwiで、価値はviです。 太郎君は、N個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量は…
最近競技プログラミングに取り組み始めたので練習日記のような形で解説記事を投稿していこうと思います。未熟者ですのでご指摘等あれば遠慮なくお申し付けください。 ここ数日は動的計画法の勉強を集中的に行っているのでまずはそのうちの一問をとりあげます。 問題へのリンク https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_d 方針 愚直に+と-の組み合わせを列挙するのはO()なので無理だということはすぐにわかる。そこで動的計画法による解法を考える。動的計画法について学んだことがないという方は以下のdrkenさんの記事がとてもわかりやすいので読んでみる…
証券投資(現代ポートフォリオ理論)をコンパクトに学ぶべく、比較的最近に発刊され薄めの本である証券投資理論 (Minervaファイナンス講座)作者:八木恭子,澤木勝茂ミネルヴァ書房Amazonを参考に学んでいきます。 1. 資本市場と有価証券・リスクと確率の基礎 2. ポートフォリオ理論:基礎 3. ポートフォリオ理論:効率的ポートフォリオ 4. ポートフォリオ理論:平均=分散モデル 5. ポートフォリオ理論:効率的ポートフォリオの性質① 6. ポートフォリオ理論:効率的ポートフォリオの性質② 7. ポートフォリオ理論:無リスク資産を含めた効率的ポートフォリオ① 8. ポートフォリオ理論:無リス…
atcoder.jp 与えられたDFSの行きがけ順 を達成するような 頂点の根付き木の数を求める問題. 部分木の形はその部分木の外にある頂点の置き方にはほとんど影響を与えないので,部分木ごとに数を数えて組み合わせる動的計画法が有力に見える. そこで次のように定める. : 頂点 からなる行きがけ順 を満たす部分木の数 指定された行きがけ順を満たすために注意すべき点は,あるノードの子が複数ある場合には番号が小さいほうから訪れるという条件である. この条件より,ある頂点を兄弟ノードとして足す場合には,これから足す頂点の番号が現在ある兄弟ノードの中で最も番号が大きいものよりもさらに大きくなっている必要…
権利があるので入緑記事を書きます! 執筆時レート:もちろん緑色 レート推移(ブランクが長いので傾きがかなり急に見える) 目次 私のスペック 競プロを始めた動機 競プロに取り組むお気持ち 1. アウトプットが一番伸びる 2. レートに固執しない 3. 比べるのは昨日の自分 具体的にこれまでやってきたこと 開始から継続的にしてきたこと 開始~0.5ヶ月(3月前半) ~1ヶ月(3月後半) ~1.5ヶ月(4月前半) ~2ヶ月(4月後半) ~2.8ヶ月(5月前半,執筆時) 最後に 私のスペック 競プロを本格的に開始して3ヶ月くらいで入緑しました! Twitterのプロフには「文系大学生」とありますが,実…
4年前に会社の福利厚生を使ってスタンフォードの授業を取ってみたら面白く、 働きながらでも続けられそうだなという実感を得たので、 2年後、受験を経てジョージア工科大学にリモートで通い始めた。 そして先日、ジョージア工科大学からコンピュータサイエンス修士号をいただくことができた。 画像の学位記は卒業式イベント用の非公式のもので、1~2か月すると Masterとちゃんと書いてある本物が来るらしい *1 。 After 1 year and 9 months, I graduated from Georgia Tech and got a master's degree in computer sci…
Atcoder Beginners Contest 250(ABC250)で無事,茶色になれましたので何をやったかのご紹介をいたします.これが初心者プログラマーやAtcoderをやってみたいけど何をすればいいか分かっていない人の参考になれば幸いです.
atcoder.jp 以下の個の行動がある. 行動: 動物と動物に円で餌をあげる 行動: 動物と動物に円で餌をあげる 行動: 動物と動物に円で餌をあげる すべての動物に餌をあげるための最小コストを計算したい. 少し観察すると,次の特徴がわかる. 動物に餌をあげるためには,行動 か行動 の少なくとも一方は行う必要がある. したがって,まず動物に対して行動か行動のどちらかによって餌を与えるか決め,さらに動物,と順に餌を与える方法を決めていく動的計画法で解けそうとわかる. : 行動 を使って番目の動物に餌を与えるための最小コスト : 行動 を使わずに番目の動物に餌を与えるための最小コスト と定める.…
問題 atcoder.jp 提出解答 atcoder.jp 問題の概要 集合 があり, 最初, である. 次の操作を好きなだけ行なう. 円払い, に を加える. 円払い, に を加える. 円払い, に を加える. 円払い, に を加える. 円払い, に を加える. 円払い, に を加える. にするためには最低何円必要か? 制約 解法1 「 円払い, に を加える.」という操作を操作 ということにする. このとき, にするためには, 操作 と操作 のうちのどちらか一方を行わければならない (操作 は操作 とする). ということになる. ここで, のときは とつながっているが, のときは であると…
これはなに こんにちは、てれじょんです。ブログを書くのは久しぶりですね。最後に記事を書いてからというもの、FFTとか、FSTとかFCTとかまあ色々実装してはいた*1のですが記事を書くのが面倒(しかも別に書かなくてもググればだいたい情報が出てくるし、適当な教科書を読めば大丈夫)で、記事を書いていないのがかれこれ2年くらい続いていました(怠惰の言い訳か?)。しかし最近球面調和関数変換(以下SHT*2 )の実装をしたのですが、ググってもググっても自分で実装しましたみたいな話が全くなくて*3、不便だったので、自分が実装したまでの道筋を備忘録的に残しておこうと思って記事を書くことにしました。自分で実装し…
https://dl.acm.org/doi/abs/10.1145/3341301.3359646?casa_token=L-sKQKrRoE4AAAAA%3AYKo9NPdnPyG6IouMN5jfTHTCYFAGORDxen32GKAteeSG-ROhqx_OX-hVOfuyHiVBXLLJH0RPujhFPEk @inproceedings{narayanan2019pipedream, title={PipeDream: generalized pipeline parallelism for DNN training}, author={Narayanan, Deepak and …
はじめまして!!!最近競技プログラミングをしているざわカスタネットと申します。twitter.com (この後すぐARCで茶色に戻るのですが・・・多分この記事が投稿されるころには緑に戻ってます・・・!)(追記 戻りました)競技プログラミングを(本気で始めて)3ヶ月、ABC249で緑色になりました!!(大学やTwitter等で)周囲に強い人が多く、「うえ〜〜い!!私最強〜〜〜〜〜〜!!」だなんて手放しには喜べませんが、比較的短期間(? 自分の能力値にしては早いと思う)でここまでこれたのはかなり嬉しく感じます! 今回は、AtCoderの灰・茶・緑下位レベルで個人的に好きな問題を集めました!(追記 …
Codeforces Round #674 (Div. 3)(2022/5/3) A: Floor Number の時だけ場合分けをして残りは割り算によって求まる. https://codeforces.com/contest/1426/submission/155732980 B: Symmetric Matrix まず が奇数の時は明らかに敷き詰められない. が偶数の時は, 対角成分を敷き詰めるために, 1,0成分と0,1成分が等しい行列が存在する必要がある. 逆に, 全ての要素をこの行列で敷き詰めたものは対角行列になる. https://codeforces.com/contest/14…
Codeforces Round #656 (Div. 3)(2022/5/4) A: Three Pairwise Maximums ひたすら場合分けをした. 公式解説によると1パターンだけ場合分けをすればよかったらしい. https://codeforces.com/contest/1385/submission/155820941 B: Restore the Permutation by Merger 前から見ていって, 初出の数なら答えの順列に追加, そうでなければ無視をすればよい. https://codeforces.com/contest/1385/submission/155…
CPCTF22に参加しました。そのwrite-up記事です。
第10回アルゴリズム実技検定(PAST) 競プロリハビリとAtCoder社へのお布施のためにと思って受験(自費)しました。[通常受験] 2022/5/3 9:02-14:02 9時ちょうどに開始ボタンを押しましたがシリアルコードではなく注文IDを入力していたためエラーで仕切り直しとなりました。 とりあえず目標は現状維持(上級)とします。(・・・試験内容に関する口外禁止期間中なので詳細は略・・・)試験時間は5時間あるのですが、開始から3時間54分のところ(13時少し前)でまさかの全完してしまいました。 PASTは途中で全完しても開始から5時間経過するまで判定は出ないというムダ知識(トリビア?)を…
学部の頃に卒論としてプロ野球チームの勝率を最大化するような打順の計算プログラムを開発しました。時間が経った今、改めてメンテナンスを行なっており試合開始前に各対戦カードでの勝率を計算できるようにしています。今回は、その理論的な説明と実際の使用方法をご紹介します。コードはGithubで公開しています。 github.com 理論 2002 年にメジャーリーグのオークランドアスレチックスが野球を数理分析するセイバーメトリクスという手法を取り入れ全 162 試合で 103 勝をあげました。このような数理分析は日本でも盛んになっています。その状況で以下の論文が出てきました。 Kira, A. and I…