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 投稿
Codeforces Round 984 (Div. 3) 問題の解説
C. Anya and 1100
問題URL
Problem - C - Codeforces
解法
文字列中の特定のパターン「1100」の出現回数を管理する問題です。ある位置の文字を変更したとき、それが「1100」の存在にどのような影響を与えるかを考えます。
変更による影響は三種類あります：
「1100」の個数が1増える
「1100」の個数が1減る
変化なし
変更箇所について、それが「1100」のどの位置（1 ...
5月17日 11:24 投稿
競技プログラミングにおける日付処理の典型パターン
競技プログラミングの過去問では、日付を扱う問題が頻出であり、特に省選レベルでは「時刻変換」「曖昧な日付の解釈」「回文日付の探索」の3つの典型的なパターンが見られます。これらは単なる文字列操作ではなく、日付の正当性検証・範囲制約・並び順保証といった実務的な要件を含むため、堅牢な実装が求められます。
ミリ秒から24時間表記への変換
入力として与えられた ...
5月16日 21:08 投稿
行列演算を活用した高速冪乗法の実装と応用
行列の構造と基本演算
行列は \(m\) 行 \(n\) 列の数値配置として定義され、各成分を \(a_{i,j}\) で表すとき、行列 \(\mathbf{A}\) は以下の形式で記述される。
\[
\mathbf{A} = \begin{pmatrix}
a_{1,1} & \cdots & a_{1,n} \\
\vdots & \ddots & \vdots \\
a_{m,1} & \cdots & a_{m,n}
\end{pmatrix}
\]
特殊な行列として「単位行列」が存在する。これは正方行列で ...
5月16日 17:00 投稿
POI2009 PRZ：配列の等価性を判定する階層化ハッシュ手法
問題の定義
本問題は、2つの正整数列 X と Y に対して、再帰的に定義された関数 F(X, Y) の真偽を判定することを目的としています。与えられた関数の構造は以下の通りです。
bool Evaluate(const std::vector<int>& X, const std::vector<int>& Y) {
if (GetUniqueSet(X).size() != GetUniqueSet(Y).size()) return false;
if (GetUniqueSet(X).si ...
5月14日 14:29 投稿