青染之心の解法：重軽分解とブロック分割法
解法1: 重軽分解によるアプローチ
オフライン処理可能な問題特性を利用し、操作履歴から木構造を構築する。各ノードの解は根からそのノードまでのアイテムを用いた完全ナップサック問題と等価である。
深さ優先探索(DFS)実行時、再帰スタックにナップサック状態を保持する。空間計算量を削減するため、重軽分解(Heavy-Light Decomposition)を適用する。具体的には:
各ノー ...
5月31日 09:21 投稿
上海大学プログラミングコンテスト2023春季ラウンド4の問題解説
A. 二分探索の学習
基本的な二分探索アルゴリズムを実装する問題です。指定された範囲内でターゲット値を見つけるために必要なステップ数を計算します。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int binary_search_steps(int left, int right, int target) {
int steps = 0;
while (left <= r ...
5月28日 10:30 投稿
競技プログラミング問題解説：5つのアルゴリズム問題の実装例
P1628 合并序列 - 文字列のマージ
指定されたプレフィックスで始まるすべての文字列をマルチセットに格納し（重複を許可し、自動的にソートされる）、出力します。
#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
in ...
5月18日 16:12 投稿
スキー問題の動的計画法解法
この問題は、2次元配列の最大下降子列を求める問題と理解できます。
解法
最も単純な方法は、直接のDFS（深度優先探索）です。問題がどこからスタートするかを指定していないため、各点をスタート点としてDFSを実行し、最大値を取得します。
本問題の正解は、メモ化検索と動的計画法（DP）の2種類があります。
メモ化検索
メモ化検索では、各点からスタートし、4つの ...
5月18日 14:20 投稿
アルゴリズム入門：検索、グラフ探索、動的計画法、ハッシュ
検索アルゴリズム
データ集合から特定の要素を見つける操作です。代表的なものに線形探索と二分探索があります。
線形探索: 先頭から順番に各要素を比較し、目的の値が見つかるか、リストの終端に達するまで繰り返します。時間計算量はO(n)です。
二分探索: ソート済みの配列に対して使用されます。探索範囲の中間点の値と目的の値を比較し、探索範囲を半分ずつ狭めていき ...
5月17日 23:06 投稿
Codeforces Round #627 解法解説
A - Yet Another Tetris Problem
n個の整数a_iが与えられます。各操作では、任意のiについてa_iを2増やすか、すべてのa_iを1減らすことができます。すべての値を0にできるか判定してください。
解法：すべての値の偶奇が一致する場合のみ可能です。
#include <iostream>
using namespace std;
void solve() {
int n, first, val;
cin >> n >> first;
fi ...
5月17日 19:21 投稿
SMU Summer 2024 Contest Round 6 問題解説
Many Formulas
問題概要
ある整数が与えられます。この整数の任意の桁と桁の間に + 記号を0個以上挿入することで式を形成し、形成可能なすべての式の合計値を計算します。
解法
1 ≤ |S| ≤ 10 であるため、全探索が現実的です。n桁の整数では、n-1箇所の隙間に加号を挿入するかどうかを決定できます。バイナリビットマスク用于枚举所有可能的加号插入位置。
実装
#include & ...
5月16日 16:51 投稿
競技プログラミング向けアルゴリズム備忘録
メモリ使用量の見積もり
プログラムが使用するメモリ容量を概算する方法：
1 MB = 1024 × 1024 バイト
int 型は 4 バイト
→ 必要メモリ (MB) = (int の要素数 × 4) / (1024 × 1024)
他のデータ型も同様に、各要素のバイト数を掛け合わせて計算する。
実行時間の計測（C++）
CPU時間を用いてコードの実行時間を計測する例：
#include <ctime>
#include <iostream ...
5月16日 05:33 投稿
動的計画法による部分列問題の解法
問題1：最長増加部分列
最長増加部分列（Longest Increasing Subsequence, LIS）問題は、与えられた数列から、要素が厳密に増加する順序で並んでいる最長の部分列を見つける問題です。
class Solution {
public:
int lengthOfLIS(vector<int>& arr) {
// 1. DPテーブルの作成
int size = arr.size();
vector<int> dp(size, 1) ...
5月15日 12:10 投稿
Pythonでフィボナッチ数列を応用した階段の登り方を求解する
問題概要と考察
この問題では、n段の階段を1段または2段ずつ登る場合の、登り方の総数を求める必要があります。各段数における解を観察すると、フィボナッチ数列と同じパターンに従っていることが分かります。
1段：1通り
2段：2通り（1+1 または 2）
3段：3通り（1+1+1、1+2、2+1）
4段：5通り（1+1+1+1、1+1+2、1+2+1、2+1+1、2+2）
つまり、n段目までの登り方の総数 ...
5月14日 19:00 投稿