Javaアルゴリズム速習ガイド
Javaアルゴリズムクイックリファレンス
リスト
初期化
List<Integer> 数値リスト = new ArrayList<>();
主なメソッド
add(Object 要素);
size();
get(int インデックス);
isEmpty();
contains(Object o);
remove(int インデックス);
マップ
マップはキーと値のペアを保持するコレクションです。
初期化
Map<String, Integer> マップ = new HashMap< ...
6月4日 16:11 投稿
連続部分列の最大和を求めるときの主要3つのアルゴリズム
整数配列から和が最大となる連続した部分配列（要素は1つ以上）を見つけ、その和を返す問題を取り上げます。配列内の任意の連続する区間の合計値のうち最大値を求める手法として、漸化式を用いた線形走査、累積和の差分最適化、そして分割統治法を解説します。
手法1：漸化式による線形走査（Kadaneのアルゴリズム変形）
あるインデックス i で終了する連続部分配列の最大 ...
6月3日 22:26 投稿
USACO 2021年オープンコンテスト金問題の解法アプローチ
問題1: 農場の統一された牛群
各要素の前後で最初に現れる同一要素の位置をprevおよびnext配列で管理します。区間[l, r]が有効となる条件は、next[l] > rかつprev[r] < lを満たすことです。
左端点lを固定し、右端点の有効性をセグメント木で管理します。prev[r] < lを満たすrを二重ポインタで追跡しながら、セグメント木の対応位置をインクリメントします。各lで ...
6月2日 17:58 投稿
回文部分文字列と回文部分列の動的計画法による解法
回文部分文字列のカウント
この問題の難しさは、DP配列の定義と漸化式の構築にあります。直接dp[i]を[0,i]の部分文字列に含まれる回文の数と定義すると、漸化式を見つけることができません。回文の性質を利用して、次のような漸化式を構築できます：[i,j]が回文かどうかを判断するために、s[i] == s[j]の場合は[i+1,j-1]が回文かどうかを確認するだけで済みます。s[i] != s ...
6月1日 11:09 投稿
青染之心の解法：重軽分解とブロック分割法
解法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 投稿