Pythonで最も長い回文部分文字列を検索する方法
問題定義
最も長い回文部分文字列とは、対称的な構造を持つ文字列のことです。例えば、文字列 s = "ababd" の場合、"aba" や "bab" が回文として該当します。
解決方針
最初の考えでは、括弧のマッチングのようなアプローチを使用し、スタックで要素を「ペア消去」することで回文を判定しようと考えました。しかし実際には「対称軸」の位置が固定されておらず、前方の消 ...
6月6日 21:19 投稿
AtCoder ABC389のアルゴリズム実装と解説
問題C: キューによる区間管理のシミュレーション
この問題では、列の先頭への追加や末尾からの削除、特定位置の要素へのアクセスを効率的に行う必要があります。全ての要素を個別に保持するとメモリや計算量が膨大になるため、連続する要素を「区間」として管理する手法をとります。
各区間について「先頭からの相対距離（開始位置）」と「区間の長さ」を構造体で定義し ...
6月6日 19:20 投稿
C++ STLアルゴリズムの使い方と実装例
1. 非変更シーケンス操作
これらのアルゴリズムはコンテナの要素を変更しない。
1.1 find系関数
find(first, last, value)：値がvalueと等しい最初の要素を検索。
find_if(first, last, pred)：述語predを満たす最初の要素を検索。
find_end(first, last, s_first, s_last)：部分列の最後の出現位置を検索。
#include <vector>
#include <algorithm>
#inc ...
6月4日 19:07 投稿
AtCoder Beginner Contest 366 の問題解説と実装
はじめに
今回のコンテストでは問題Eに大部分の時間を費やすことになり、残り15分でようやく正解にたどり着くという危ない場面でした。緑色レベルの問題にも苦戦するようでは、まだまだ実力不足を感じます。
A - Election 2
高橋君と青木君のどちらかが過半数の票を獲得したかどうかを判定するシンプルな問題です。
#include <iostream>
using namespace std; ...
6月4日 17:22 投稿
除算式の整数化判定と効率的な約分アルゴリズム
与えられた除法式 $X_1/X_2/X_3/\dots/X_k$ に対して、括弧を任意の位置に挿入して演算順序を変更した際、その結果が整数になるかどうかを判定する問題を考えます。入力として複数のテストケースが与えられ、各ケースごとに整数化が可能か（YES）そうでないか（NO）を出力する必要があります。ここで、$k$は最大で10,000、各$X_i$は最大で100,000,000の正整数です。
こ ...
6月3日 22:20 投稿
C++を用いた配列操作：最大値除外、平均算出、配列比較の実装手法
最大値と異なる数値の総和を求める
与えられた整数列の中から最大値を特定し、その最大値と一致しない要素のみを抽出して合計を算出するプログラムの実装です。
実装コード
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int elementCount;
if (!(std::cin >> elementCount)) return 0;
std::vector&l ...
5月30日 15:39 投稿
スライディングウィンドウの最大値を求めるアルゴリズム
スライディングウィンドウ問題において、各ウィンドウ内の最大値を効率的に求めるには、双方向キュー（deque）を活用した単調キューというデータ構造が有効である。このアプローチにより、O(n)の時間計算量で解を導出できる。
双方向キューの特性と選択理由
通常のキュー（queue）は、要素の追加が末尾から、取り出しが先頭からのみ可能である。一方、双方向キュー（deq ...
5月29日 23:52 投稿
コーディングテスト演習（一）——Codeforces 784B Santa Claus and Keyboard Check
はじめに
最近、コーディングテストの準備をしており、練習問題をまとめています。 元々はC言語の経験しかありませんでしたが、実際に使用会发现C++の方がテストに向いています。ライブラリ関数も豊富で、より多くの操作をサポートでき、コードを簡潔に記述できます。 例えば、C言語で文字列を定義するにはchar s[1000]が必要ですが、C++ではstring sだけで済みます。
問 ...
5月29日 16:25 投稿
二分探索木の有効性検証：中間順走査によるアプローチ
問題の概要
二分探索木（BST）が有効であるかどうかを判定するには、各ノードが以下の条件を満たしているかを確認する必要があります。
ノードの左部分木に含まれるすべての値は、そのノードの値より厳密に小さい。
ノードの右部分木に含まれるすべての値は、そのノードの値より厳密に大きい。
左右の部分木もそれぞれ二分探索木でなければならない。
これを効率的にチェ ...
5月29日 04:49 投稿
最小部分文字列の探索：スライディングウィンドウ手法の実装
問題定義
2つの文字列 s と t が与えられた場合、s 内の部分文字列の中で、t のすべての文字（重複を含む）を含む最小の長さを持つものを見つけます。該当する部分文字列が存在しない場合は空文字列を返します。
この問題は、スライディングウィンドウ（Sliding Window）アルゴリズムの典型例です。左右2つのポインタを用いてウィンドウの範囲を動的に管理することで、効率 ...
5月29日 02:43 投稿