LeetCodeスライディングウィンドウパターン徹底解説
スライディングウィンドウ入門
「連鎖・部分文字列・配列の問題は、まず双方向ポインタを考えよ。
双方向ポインタ三兄弟、それぞれに魅力あり。
速いポインタと遅いポインタは魔法使い、連結リスト操作に敵なし。
マージソートで中点を探し、連結リストの循環を判定。
左右ポインタが最も一般的、配列の両端から中央へ。
反転配列にはこれを頼れ、二分探索は弟分。
スライ ...
6月8日 18:46 投稿
競技プログラミング問題集：基本アルゴリズムの実践
最短区間カバー問題
指定された種類数を満たす最小連続区間を探索する問題です。スライディングウィンドウ手法を用い、要素の出現頻度を動的に管理しながら最適解を導出します。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> cookTypes(n);
for (int i = 0; i < n; ++i ...
5月31日 19:21 投稿
スライディングウィンドウの最大値を求めるアルゴリズム
スライディングウィンドウ問題において、各ウィンドウ内の最大値を効率的に求めるには、双方向キュー（deque）を活用した単調キューというデータ構造が有効である。このアプローチにより、O(n)の時間計算量で解を導出できる。
双方向キューの特性と選択理由
通常のキュー（queue）は、要素の追加が末尾から、取り出しが先頭からのみ可能である。一方、双方向キュー（deq ...
5月29日 23:52 投稿
最小部分文字列の探索：スライディングウィンドウ手法の実装
問題定義
2つの文字列 s と t が与えられた場合、s 内の部分文字列の中で、t のすべての文字（重複を含む）を含む最小の長さを持つものを見つけます。該当する部分文字列が存在しない場合は空文字列を返します。
この問題は、スライディングウィンドウ（Sliding Window）アルゴリズムの典型例です。左右2つのポインタを用いてウィンドウの範囲を動的に管理することで、効率 ...
5月29日 02:43 投稿
Codeforces Round 938 Div.3 問題セット解説とアルゴリズム実装
問題A：ヨーグルト購入の最適化（貪欲法）
課題の概要
1本あたりの価格が single 円、2本セットの価格が pair_cost 円のヨーグルトが販売されている。合計 n 本を購入する際、最小の総支出額を求める。
実装アプローチ
セット購入の単価（pair_cost / 2）と通常価格を比較する。セット単価が通常価格より安価な場合は、可能な限りセットで購入し、余った分を単品で処理する ...
5月14日 06:06 投稿
可変長スライディングウィンドウの実装パターンと典型問題
スライディングウィンドウの適用条件
スライディングウィンドウは、配列や文字列における連続した部分列に関する問題に有効です。特に、以下のような要件を持つ問題に適しています：
部分配列・部分文字列の最小/最大長を求める
特定の条件を満たす最短/最長の連続要素を探索する
許容誤差（例：最大k個の0を1に変換）付きでの最適解を求める
基本的な実装手順
...
5月13日 15:34 投稿