Matsushita's Blog

漸化式

AtCoder ABC D - Mixing Experiment

問題 D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder 解き方 全列挙を考える 全列挙する場合、i番目の薬品を購入する場合としない場合を2パターンをN回行うので、計算量はO(2N)となりNは最大40なので間に合わない。 動的計画法を使う dp(i…

361. Bomb Enemy : Past Google Coding Interview

Problem https://leetcode.com/problems/bomb-enemy/ How to Solve This problem can be solved by using Dynamic Programming. The point of this problem is that one spot in the grid can divide into four direction (up, down, left, right). We can c…

漸化式を立てて「tree DP問題」を解く D - 塗り絵

問題 D: 塗り絵 - AtCoder Beginner Contest 036 | AtCoder N 個の島があります。 島には 1 から N までの番号がついています。 また、N−1 個の橋があります。 i 番目の橋は ai 番の島と bi 番の島をつないでいます。 どの島からどの島へも橋をいくつか経由…

AtCoder ABC D: 経路

問題 D: 経路 - AtCoder Beginner Contest 037 | AtCoder 解法 以下をポイントにして動的計画法により解く。 求めたいもの: 経路数 マスを進む度に変わるもの: (i, j) 現在いるマスがi行j列のマス 進めるマスが無くなったらを抜ける条件にして再帰関数で実装…

最長共通部分列 Longest Common Subsequence

最長共通部分列とは 最長共通部分列(Common Longest Subsequence)とは、2つの与えられてた列X = {x1, x2, …, xm}とY = {y1, y2, …, yn}の最長の共通部分列のことである。 例えばX = {a, b, c, d, f}, Y = {a, f, b, d, a}の最長共通部分列は{a, b, d}となる…

フェルマーの小定理による組み合わせ計算によって経路数を数え上げる

問題 D: いろはちゃんとマス目 / Iroha and a Grid - AtCoder Beginner Contest 042 | AtCoder 解法 まず、この問題のポイントを抑える 問題のポイント 右と下にのみ移動可能なマス目の経路数の数え上げ 縦マスH, 横マスWはそれぞれ、1≦H,W≦100,000 (105) AB…

フェルマーの小定理を用いてコンビネーションを計算する

背景 nCk nCkを計算したい。(n個の中からkこ取り出す組み合わせ) nCkはnCk = n! / k! * (n - k)!となる。これを計算すれば求まる。しかし、分母のk! * (n - k)!の部分に着目した時に、nの値が大きいと値が大きすぎて計算できない。 そこで、プロコンの世界で…

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

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

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

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

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

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