競技プログラミング模試解説：数論・文字列・区間クエリ処理
本記事では、CSP（中国情報オリンピック予選）直前に実施された模擬コンテストの4問について、解法と実装を解説する。
A. 素因数分解による数字列変換
各桁の数字を素因数に分解し、大きい素因数から順に出力する問題。例えば「6」は2×3なので、最終的な出力では「3」より「2」が先に来る必要がある。
各数字の素因数の個数を前計算し、7, 5, 3, 2の順に貪欲に出力する ...
9月4日 02:09 投稿
競プロ典型問題の解法パターンと実装テクニック
文字列の構成要素検証
与えられた3文字の文字列が"A"、"B"、"C"の3種類の文字のみで構成されているかを判定する問題。文字の順序は問わず、各文字が1回ずつ出現するかを確認する必要がある。
#include <iostream>
#include <array>
using namespace std;
int main() {
string input;
cin >> input;
array<int, 3> count = {0};
...
8月27日 22:31 投稿
区間MEXの重要な性質とそのアルゴリズム
はじめに
この記事では、数列における区間MEX（Minimum Excluded Value）の重要な性質について考察します。MEXとは、数列に含まれていない最小の非負整数を指します。特に、「極小MEX区間」と呼ばれる概念に焦点を当て、その数がO(n)に収まることを証明し、効率的なアルゴリズムを提案します。
極小MEX区間の定義と重要性
極小MEX区間とは、区間の左端または右端を1つ削除 ...
7月15日 22:49 投稿
線分木を使用した複雑な操作の実装
この問題では以下の4つの操作を実装する必要があります：
操作1: 結果にaを加算
操作2: 結果からaを減算
操作3: 結果にaを乗算
操作4: 結果にa * Xを加算
これらの操作を効率的に処理するために、線分木を使用します。線分木は区間最大値と最小値、加算の遅延評価タグ、乗算の遅延評価タグ、代入の遅延評価タグ、および操作4用の遅延評価タグを管理します。
木の構築
通 ...
6月12日 18:13 投稿
高度なアルゴリズム - バイナリインデックストリーとセグメントツリー
バイナリインデックストリー
単点更新、範囲照会が可能なデータ構造です。
典型的な問題として、数列の特定の位置を更新し、任意の区間の合計を求める操作が考えられます。
このデータ構造の核となるのがlowbit関数です。これは整数xに対して、xの最も右側にある1を含む部分を返す操作です。具体的にはx&-xと表現できます。
実装の基本となるのはtree配列です。各要素t ...
6月10日 23:11 投稿