メモ化

ナップザンク問題

dp(i, j)を以下のように定義する。 dp(i, j) := i番目の荷物を重さj以下のなるように操作した時(その荷物を入れるか否か)の最大の価値 深さ優先で、その荷物を入れる場合と入れない場合とを比べ、価値がより大きくなるものを選択していく。

ドワンゴからの挑戦状 B - ニコニコレベル

問題 B: ニコニコレベル - 第3回 ドワンゴからの挑戦状 予選 | AtCoder ニコニコ文字列とは、25 を 0 回以上繰り返した文字列のことをいいます。たとえば 25 や 252525 や空文字列はニコニコ文字列ですが、123 や 225 はニコニコ文字列ではありません。 ある…

重複組合せを用いた多重ループ

問題 D: 多重ループ - AtCoder Beginner Contest 021 | AtCoder 解法 問題文の以下に注目 このプログラムの出力する答えは 1≦a1≦a2≦…≦ak≦n であるような整数の組 (a1,a2,…,ak) の個数に等しい 公式の解説に則ってこの文章を以下のように変換して考える。 「…

パスカルの三角形を用いてコンビネーション(組み合わせ)のクラスを実装する

コンビネーション(組み合わせ)とは nCk = n! / k! * (n - k)! n個の中からk個取り出す場合の数を算出するものである。 パスカルの三角形とは 2項展開における係数を三角形状に並べたものである。 パスカルの三角形 - Wikipedia それぞれの値はnCkの計算結果…

動的計画法が困難なナップザック問題

問題 D: ナップサック問題 - AtCoder Beginner Contest 032 | AtCoder 解法 この問題はナップザック問題を応用したものである。入力値は以下の3つの条件のどれかが当てはまる N <= 30 のケース それぞれの荷物の価値Viが1000以下のケース それぞれの荷物の…

動的計画法を使うことでアスレチックで遊ぶ時に体力の消耗を抑える

問題 C: 柱柱柱柱柱 - AtCoder Beginner Contest 040 | AtCoder 解き方 全探索では計算量がO(2n)となり間に合わない。よって動的計画法を用いて解く。 なぜ動的計画法が使えるか 部分問題を解き、その計算結果を保存し再利用することで全体の問題が解ける。i…

動的計画法を使ってグリッドの経路数を求める

問題 C: 経路 - AtCoder Beginner Contest 034 | AtCoder 100点解法 ※この問題は101点満点なので、満点解法ではない。 動的計画法を用いて経路数を算出する。 動的計画法を用いることができるのは以下の2つのポイントをおさえているから。 分割統治法: 部分…

漸化式を用いた動的計画法の関数の作り方

わんちゃんかわいいですね。 動的計画法勉強中で流れを掴むために関数の作り方を整理します。そのため間違った内容などもあるかもですがまとめてみます。 もし、間違っていたらコメントください。 動的計画法とは 動的計画法は以下の2種類の条件を満たすア…

食費を節約するために動的計画法を用いる

問題 C: 節制 - AtCoder Beginner Contest 013 | AtCoder はじめ、高橋君の満腹度は H です。N 日間のそれぞれの日について、その日にとる食事を次の 3 種類の中から 1 つ選びます。 普通の食事: A 円の出費をして、満腹度が B 増える。 質素な食事: C 円の…