模擬退火アルゴリズムの原理と実装事例
模擬退火法の概要
模擬退火（Simulated Annealing, SA）は、大域的最適解近似アルゴリズムの一種であり、組み合わせ最適化問題などに広く適用される確率的探索手法です。解空間が非常に広大であり、かつ目的関数が単峰性を持たない場合などに有効です。
この手法は、金属加工における「焼きなまし（Annealing）」プロセスに由来します。金属を高温で加熱し、徐々に冷却する ...
7月12日 23:28 投稿
フェニック木（Binary Indexed Tree）の基礎と応用
フェニック木（Binary Indexed Tree, BIT）は、主に数列の prefix sum（接頭辞和）を効率的に管理・計算するために設計されたデータ構造です。セグメント木と比較して実装が簡潔であり、定数倍の計算コストが低いため、頻繁な更新とクエリが発生する箇所で広く利用されています。本記事では、基本的な1次元の構造から、差分を利用した区間更新、および2次元への拡張につい ...
7月11日 16:07 投稿
2023年春季西南民族大学プログラミングコンテスト 第6回 解説
問題解説 - L1-1 今日こそ勝利を掴む
この問題は単純な出力問題です。指定された文字列と日付を出力するだけです。
#include <iostream>
using namespace std;
void process() {
cout << "I'm gonna win! Today!" << endl;
cout << "2022-04-23" << endl;
}
問題解説 - L1-2 ダイヤモンドの植栽
整数nとvが与えられ、nをvで割 ...
7月9日 21:52 投稿
Codeforces 教育ラウンド 66 (Div. 2 対象) 問題 A～F
A - ヒーローからゼロへ
シミュレーション問題です。
kで割れる場合は直接kで割り、そうでない場合は余りを引きます。
コードを見る
#include
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--) {
long long n, k;
cin >> n >> k;
long long c ...
6月30日 19:38 投稿
SMU Autumn 2023 Div.1 コンテスト問題のアルゴリズム解説と実装
問題A：数値の置換と減少による合計値制御
配列の各要素に対して「任意の要素を1減算する」または「任意の要素を他の要素の値へコピーする」操作を繰り返し、配列総和を閾値K以下にするための最小操作回数を求める問題です。
効率的な解法は貪欲法と累積和の組み合わせです。まず配列を昇順ソートします。大きな値を直接減算するよりも、最小値へコピーした方が一度に合計 ...
6月25日 22:31 投稿
SMU Summer 2023 Contest Round 4のアルゴリズム解説
A. Telephone Number
この問題では、与えられた文字列から標準的な11桁の電話番号を作成できるかを判定します。電話番号の最初の数字は'8'でなければならないため、最初の'8'が現れる位置が重要です。文字列の長さを n とすると、最初の'8'のインデックスが n - 11 以下であれば、その後ろに残りの10桁を配置するための十分な文字数が存在します。
#include <iostream&g ...
6月24日 00:42 投稿
SMU Winter 2025 個人コンテスト第3回 解説
A. Vasya and Book
現在のページ x から目的のページ y まで、1回の操作で d ページ進むか戻る（ただし範囲外には行けない）ときの最小操作回数を求める。
以下の3通りを検討し、可能なものの最小値を取る：
|x - y| が d で割り切れる場合：直接移動可能。回数は |x - y| / d。
先頭ページ（1）経由： (y - 1) % d == 0 のとき、x → 1 → y の合計回数は ceil(x / d) + (y ...
6月16日 16:57 投稿
競技プログラミングにおける行列の実装と応用例
行列の定義と基本性質
行列（Matrix）は、数値を長方形の配列状に配置した構造体です。一般に \(m \times n\) の次元を持つ行列 \(A\) は、以下のように表されます。
$$ A = \begin{bmatrix}
a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\
a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{m,1} & ...
6月7日 19:46 投稿
除算式の整数化判定と効率的な約分アルゴリズム
与えられた除法式 $X_1/X_2/X_3/\dots/X_k$ に対して、括弧を任意の位置に挿入して演算順序を変更した際、その結果が整数になるかどうかを判定する問題を考えます。入力として複数のテストケースが与えられ、各ケースごとに整数化が可能か（YES）そうでないか（NO）を出力する必要があります。ここで、$k$は最大で10,000、各$X_i$は最大で100,000,000の正整数です。
こ ...
6月3日 22:20 投稿
AtCoder Beginner Contest 310 各問題のアルゴリズム解説とC++実装例
A: 別の注文方法
料理とセットで購入する場合、特定のドリンクが定価 \(P\) から割引価格 \(Q\) へ変更される。セット購入しない場合は、別のドリンクリストから任意の価格のものを選ぶことができる。支払い額を最小化する問題である。
実装方針は単純である。セット割引適用時の支払い額 \(Q + \min(A)\) と、割引なしの定価 \(P\) を比較し、小さい方を出力すればよい。\ ...
5月22日 01:48 投稿