異端開発室

高精度計算 トライ木を用いた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 とし、残りの位置には任意の値を入れます。 \[ ...