Dijkstra法の簡潔実装：配列ベースの優先度付き探索
重み付き有向グラフにおいて、特定の始点から各頂点への最短距離を求める単一始点最短経路問題。ここでは、隣接行列を入力とし、優先度付きキューを用いたDijkstra法の実装を示す。構造体を使わず、配列とペアのみで構成する。
入力仕様
1行目に頂点数 n と始点番号 s を指定する。続く n 行の各行に n 個の整数を並べ、隣接行列を表現する。行列の要素が正の整数の場合、 ...
8月15日 12:41 投稿
DPと貪欲法による丑数の計算
丑数とは、2, 3, 5のいずれかの数の積からなる数のことです。
最初、私は深さ優先探索（DFS）と集合（set）を使って解こうとしたが、これは効率的ではありませんでした。代わりに、各丑数を順番に配置したいと考えました。例えば、6の次は8であり、9ではありません。
次の丑数は以下の3つの可能性のうちの最小値になります：
prev1 * 2;
prev2 * 3;
prev3 * 5;
ここで、pre ...
8月3日 22:24 投稿
ABC379 問題解説：C・D・E・F
C問題：石の山の配置
石を後方にしか移動できないという制約下で、目標の配置が可能かどうかを判定し、最小移動回数を求める問題です。
条件を満たす配置は一意に定まるため、以下の3点をチェックします。
石の総数がnと一致しない場合は不可能。
最初の山の位置が1でなければ不可能。
途中の位置で、それまでの石の合計数が必要数に満たない場合は不可能。
解 ...
6月22日 21:01 投稿
等しい要素をマージするアルゴリズムの実装
問題概要
配列内の等しい要素をマージする問題について、2つの異なるアプローチを解説する。
アプローチ1: 優先度付きキューを使用
優先度付きキューを用いて、値とインデックスを管理する方法。以下の手順で処理を行う:
すべての要素を値とインデックスのペアとしてキューに追加
キューの先頭から2要素を取り出し、値が等しければ和を計算して再挿入
等しくなけ ...
5月18日 15:30 投稿