異端開発室

動的プログラミング基礎問題集 ======= 問題1: スキー場の最長滑走ルート 難易度: 入門～中級 解法: メモ化探索 スキー場の地図が与えられ、各地点の標高がわかっています。標高が高い地点から低い地点へのみ滑ることができるとき、最長の滑走ルートの長さを求めてください。 解法として、すべての地点を起点としてDFS（深さ優先探索）を行い、メモ化テクニックを用いて ...

概念 挿入型動的計画法（DP）とは、特定の順列に基づいてDPを行う問題で、計算量は一般的にO(n2)からO(n3)の範囲内です。この種の問題では、順列内の昇順や降順の変化点が答えに大きな影響を与えます。 基本的なアプローチは以下の通りです： 数値を小さい順に挿入し、その段階で状態設計を行います。これにより、既に挿入された数値は現在の数値より小さく ...

高精度計算 トライ木を用いたA+B #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; struct TrieNode { int children[26]; int value; } nodes[1000]; char buffer[100]; int nodeCount = 0, totalNodes = 0, resultSum = 0; bool negativeFlag; void insertNumber() { int cur ...

動的計画法（DP）とは 動的計画法（Dynamic Programming, DP）は、問題をより小さな部分問題に分割し、その結果を再利用することで効率的に解く手法です。特に「重複部分問題」と「最適部分構造」を持つ問題に有効です。 DPの一般的な手順 状態の定義：DPテーブル（dp配列）の各インデックスが何を表すかを決める。これがすべての基盤となる。 状態遷移式：dp[i]を求める ...

C問題：石の山の配置 石を後方にしか移動できないという制約下で、目標の配置が可能かどうかを判定し、最小移動回数を求める問題です。 条件を満たす配置は一意に定まるため、以下の3点をチェックします。 石の総数がnと一致しない場合は不可能。 最初の山の位置が1でなければ不可能。 途中の位置で、それまでの石の合計数が必要数に満たない場合は不可能。 解 ...

すべての行に少なくとも 1 つの 1 を配置する必要があるため、行ごとに処理し、その行にいくつかの 1 を追加することを考えます。現在の状態を表すために、dp[i][j] を「最初の i 行を埋めた時点で、1 がすでに存在する列が j 列ある場合の埋め方の総数」と定義します。遷移では、現在の行で新たに 1 を追加する位置の数を k とし、残りの位置には任意の値を入れます。 \[ ...