動的計画法

atcoder.jp・参考 Editorial - GAMEFREAK Programming Contest 2023 (AtCoder Beginner Contest 317)・説明 参考にも書いてあるが、ナップサック問題のDPと同じように解ける。dp[n]はn議席獲得するために必要な鞍替えさせる最低限の人の数である。 今回は鞍替えさせる人数をコストwと見てこれを最小にすることを考える。コストwはX[i]>Y[i]のとき鞍替えさせる必要がないので0、X[i] #入力。 n=int(input()) X=[] Y=[] Z=[] s=0 for _ in range(n): x,y,z=m…

まだ、初歩的な部分に触れただけなので追記したい。 動的計画法とは 自分の理解 例題 例題の解答コード 参考サイト 動的計画法とは 動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。 細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。 1、帰納的な関係の利用：より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。 2…

atcoder.jp・参考 AtCoder Beginner Contest 314 - YouTube・説明 参考動画の実装をPythonで行った。プログラムの説明は下でコメントアウトしている。 ・実装 n,m=map(int,input().split()) c=[] p=[] s=[] for _ in range(n): l=list(map(int,input().split())) c.append(l[0]) p.append(l[1]) s.append(l[2:]) dp=[10**18 for _ in range(m+1)] dp[0]=0 for i in range(…

＜最適化問題の概要＞ ＜最短経路問題の解説＞ ＜動的計画法の解説＞ ｜まとめ（最適化問題、最短経路問題、動的計画法） 数値計算は、コンピュータを利用して数値的な方法で数式やデータを解析し、問題の解決や最適化を行う手法です。 ここでは、数値計算の中で重要な要素となる「最適化問題」、「最短経路問題」、「動的計画法」の３つをそれぞれ解説していきます。 【令和５年度】 いちばんやさしい 基本情報技術者 絶対合格の教科書＋出る順問題集 作者:高橋 京介 SBクリエイティブ Amazon ＜最適化問題の概要＞ 最適化問題とは、特定の目的を達成する際に、与えられた制約条件の下で最適な解を見つける問題のことで…

atcoder.jp・解説： Editorial - Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306） ・反省点：食べたときと食べなかったときの遷移は別々にやるとWA。食べたときの遷移をして、食べたとき(dp[i+1][0],dp[i+1][1])と食べなかったとき（dp[i][0],dp[i][1]）どちらが大きいか、見る必要がある。・間違ったコード n=int(input()) xy=[list(map(int,input().split())) for _ in range(n)] dp=[[0 for _ i…

atcoder.jp・参考： drken1215.hatenablog.com ・やり方： 基本的には上の記事を参考。jは0でcapslockキーがoff,1でon。dp[i][j]はi文字でのjがON,OFFであったときにかかる時間。 capslockの遷移はdp[i][0]=min(dp[i][0],dp[i][1]+Z)、dp[i][1]=min(dp[i][1],dp[i][0]+Z)。aを入力するにはj=0のときX秒、j=1のときY秒かかるので、dp[i+1][0]=min(dp[i+1][0],dp[i][0]+X),dp[i+1][1]=min(dp[i+1][1],dp[i][…

atcoder.jp ・内容： 貰う DP と配る DP、メモ化再帰、個数制限なしナップサック問題 - Qiita の記事のbfsでの実装をpythonでやった。 ・説明：0から1,6,6*6,,,9,9*9,,,,の辺を取ったグラフと見ればbfsで求められる。詳しくは上の記事を参考。c++ではfor文で6,9の倍数が表現できるがpythonだとそれが少し難しかった。 from collections import deque n=int(input()) dp=[-1 for _ in range(n+1)] #-1で未探索。n円までに必要な引き出し回数。 que=deque() que.a…

はじめに ゲームに有用な数学-計算量と複雑性・テンソル・群論 ゲーム木の複雑度 決定問題と最適化問題 NP困難 NP完全 PSPACE 純碁の計算複雑性理論 5路盤や6路盤では、純碁はPに属する。 7路盤や8路盤では、純碁の計算複雑性は未解決である。 9路盤では、純碁はPSPACE完全である。 トランプのポーカー ルービックキューブ 2×2×2は、最適解が11手以内である。 3×3×3は、最適解が20手以内である。 4×4×4は、最適解が29手以内である。 5×5×5は、最適解の上界は未知である。 テンソル 計算量や複雑さを計算する方法 テンソルの特殊な例 群論 ルービックキューブ群 P≠NP…

はじめに 学内の競技プログラミングサークル"RiPPro"が開催する合宿に参加したので、それについて書く。 今回の合宿は、サークル内の人のみの参加となっており小規模で、日程は1泊2日。予定では6名、そこから2名のキャンセルが出て実際には4名での開催となった。 宿泊に利用する施設は、学内にある「エポック立命21」で、チェックインまでの活動も同施設で行った。 さて、自分が現在所属しているRiPProでは、過去にRUPC(立命館大学競技プログラミング合宿)を開催していたが、RUPC2020がコロナウィルスの影響によって中止されて以来、そのようなイベントは開催できていない。 自分がRiPProに所属し…

2023年9月8日の World Tour Finals 2022 Day1（Open Contest）をもちまして、レートが赤に突入しました！！！ レットコーダーになりました！！！！！！ pic.twitter.com/3sVTYGSX31 — りーふ@競プロ (@leaf_1415) September 8, 2023 のでいっぱい自分語りして気持ちよくなります。 1年目 2017春 競プロに出会う 大学で競プロをやる授業があったのをきっかけに競プロに遭遇。 形式こそはコンテストであったものの、授業なのでそんなに難しい問題は出ません。 が、授業で最難レベルの問題「各マスが白か黒で塗られたグ…

解説を読んだけど、自分でかみ砕いた解説を出来たほうが良いなと思うので、備忘録的に多少雑でもまとめます。 文字列Sが与えられます。この中から8文字を選び、下線を引きます。選んだ文字が左から順に c, h, o, k, u, d, a, i となるような方法は何通りありますか？ ただし、答えが非常に大きくなる可能性があるため、(109 + 7)で割った余りを出力してください。 #### 制約#### ・8<=|S|<=105 ・Sは英小文字からなる 入力例 1 chchokudai 出力例 1 3 chchokudaichchokudaichchokudai上の 33 つが条件を満たします。 ch…

｜アルゴリズム １．アルゴリズムとは ２．アルゴリズムの特性 ３．アルゴリズムの重要性 ４．アルゴリズムの種類 ５．アルゴリズムの評価 ｜アルゴリズムの基本「制御構造」 １．順次構造 ２．選択構造 ３．繰り返し構造 ｜アルゴリズムと流れ図（問題解決の道しるべ） １．端子 (Terminal) ２．処理 (Process) ３．定義済み処理 (Predefined Process) ４．判断 (Decision) ５．入出力 (Input/Output) ｜アルゴリズムと繰り返し制御（ループ） １．繰り返し制御（ループ）の重要性 ２．ループの種類 ｜アルゴリズムの効率性 ｜アルゴリズムの設計 A…

Toyota Programming Contest 2023#5（AtCoder Beginner Contest 320） - AtCoder B - Longest Palindrome 二重ループで全探索。回文は reverse した文字列と等しいかどうかで判定 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define endl '\n' int main() { string s; cin >> s; int n = s.size(); auto check …

久々にプログラムです．ラマヌジャンのτ関数の計数をある程度計算してみようと思います． とはいっても今回は難しいことはしないです．

先日の１ヶ月ぶりのラウンドでは、グリーンを手前から狙っていく時に、アイアンが右に出て、グリーン右のバンカーに捕まるミスが多かった。こういう場合、より大きめの番手を選んで、グリーン奥でもいいから乗せることを考えるべきだったのだろうか？あるいはグリーン左サイド（寄せやすいところ）に外してもいいと考え、そちらを狙うべきだったのだろうか？ muranaga-golf.hatenablog.com コーチに質問してみた。「いろいろな考え方があるけれど、自分は、グリーンを狙える状況なら狙うべきと考えている（左サイドに外すべきではない）」との答え。そう、昔からラウンド・レッスンなどで、コーチには「グリーンに…

はじめに ABC317のA,B,C,D問題をPython3で解きます。 はじめに A問題: Potions 問題の概要 問題の考察 コード B問題: MissingNo. 問題の概要 問題の考察 コード C問題: Remembering the Days 問題の概要 問題の考察 DFSで解く場合のコード bitDPで解く場合のコード D問題: President 問題の概要 問題の考察 コード A問題: Potions atcoder.jp 問題の概要 個の効き目順に並んだ傷薬があり、番目の傷薬を使うと体力がだけ増加する。現体力がで傷薬を1つ使って体力を以上するとき、その条件を満たす最も効き目…