2025牛客暑期多校訓練キャンプ第1回 解説
G. Symmetry Intervals
文字列 $S$ と $q$ 個のクエリが与えられる。各クエリでは文字列 $T$、整数 $a$、および区間 $[l, r]$（ただし実装上は $T$ 全体を対象）が与えられ、$S_{a+x-1} = T_x$ がすべての $x \in [l, r]$ で成り立つような連続部分区間の個数を求める。
アプローチとしては、$T$ の各位置 $j$ に対して対応する $S$ のインデックス $ps = j + a - 1$ を計 ...
5月16日 19:59 投稿
循環配列における次の大きな要素の検出と「雨水を貯める」問題のアルゴリズム解説
503. 循環配列における次の大きな要素 II (Next Greater Element II)
循環配列（最後の要素の次が最初の要素となる配列）が与えられた場合、各要素に対して「次に大きい要素」を見つける問題です。要素xの次に大きい要素とは、配列を巡回順で走査した際、xの後に現れる最初のxより大きな数値を指します。そのような数値が存在しない場合は-1を出力します。
解法アプロー ...
5月16日 17:53 投稿
ICPC 2018 横浜大会における主要アルゴリズムの解説
2018年に開催されたICPCアジア地区予選横浜大会の出題問題より、いくつかの典型的な実装手法とアルゴリズムの考え方を解説します。
1. 文字列と数値の混合ソート
文字列中に含まれる数値とアルファベットを個別に識別し、辞書順および数値の大きさに基づいた比較を行う問題です。主なロジックは以下の通りです。
両文字列が完全に一致する場合は対象外とする。
...
5月16日 06:48 投稿
二つのソート済み単方向リストのマージアルゴリズム
二つの非減少順（昇順）に整列された単方向連結リストを、一つの新たなソート済みリストに統合する問題。統合後のリストは、元の二つのリストに含まれるすべてのノードを再利用して構成され、追加のメモリ割り当ては不要である。
核心的なアプローチは以下の通り：
- **ダミーノード**（仮想ヘッド）を導入し、新規リストの先頭を一貫して扱えるようにする
- 結果リス ...
5月14日 23:26 投稿
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 投稿
可変長スライディングウィンドウの実装パターンと典型問題
スライディングウィンドウの適用条件
スライディングウィンドウは、配列や文字列における連続した部分列に関する問題に有効です。特に、以下のような要件を持つ問題に適しています：
部分配列・部分文字列の最小/最大長を求める
特定の条件を満たす最短/最長の連続要素を探索する
許容誤差（例：最大k個の0を1に変換）付きでの最適解を求める
基本的な実装手順
...
5月13日 15:34 投稿
ハッシュテーブルを活用したアルゴリズム問題の効率的な解法
ハッシュテーブルは、キーと値のペアを格納し、平均的に定数時間O(1)でデータの検索、挿入、削除を行うことができる非常に効率的なデータ構造です。ここでは、ハッシュテーブルの特性を利用して計算量を削減し、アルゴリズムのパフォーマンスを最適化する代表的な問題について解説します。
有効なアナグラムの判定
2つの文字列がアナグラム（文字の並び替え）であるかどう ...
5月11日 10:22 投稿