動的計画法

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問って何？ 過去の記事についてはこちら！！ 第１回：全列挙 第２回：工夫して通り数を減らす全列挙 第３回：ビット全探索 第４回：順列全探索 第５回：二分探索 第６回：深さ優先探索 第７回：幅優先探索 動的計画法：ナップザック DP 34. Fibonacci Number 35. 0-1 Knapsack Problem 36. Knapsack Problem 37. Coin Changing Problem 38. Longest Common Subsequence 最後に 精選100問って何…

はじめに Pythonで実装しました．そんなところで差が出るなんて，，，という学びがあったので記事にします． 問題 ABC123 C - Typical Stairs 考え方 いわゆるDPの基本的な問題なのだとおもいます．フィボナッチ数列と同じです． 1歩または2歩進めるとうことは，Ｎ段目に到達する方法は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. ポートフォリオ理論：無リス…

権利があるので入緑記事を書きます！ 執筆時レート：もちろん緑色 レート推移(ブランクが長いので傾きがかなり急に見える) 目次 私のスペック 競プロを始めた動機 競プロに取り組むお気持ち 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 以下の個の行動がある． 行動: 動物と動物に円で餌をあげる 行動: 動物と動物に円で餌をあげる 行動: 動物と動物に円で餌をあげる すべての動物に餌をあげるための最小コストを計算したい． 少し観察すると，次の特徴がわかる． 動物に餌をあげるためには，行動 か行動 の少なくとも一方は行う必要がある． したがって，まず動物に対して行動か行動のどちらかによって餌を与えるか決め，さらに動物,と順に餌を与える方法を決めていく動的計画法で解けそうとわかる． : 行動 を使って番目の動物に餌を与えるための最小コスト : 行動 を使わずに番目の動物に餌を与えるための最小コスト と定める．…

これはなに こんにちは、てれじょんです。ブログを書くのは久しぶりですね。最後に記事を書いてからというもの、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…

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…