競技プログラミング模試解説：数論・文字列・区間クエリ処理
本記事では、CSP（中国情報オリンピック予選）直前に実施された模擬コンテストの4問について、解法と実装を解説する。
A. 素因数分解による数字列変換
各桁の数字を素因数に分解し、大きい素因数から順に出力する問題。例えば「6」は2×3なので、最終的な出力では「3」より「2」が先に来る必要がある。
各数字の素因数の個数を前計算し、7, 5, 3, 2の順に貪欲に出力する ...
9月4日 02:09 投稿
Binary Indexed Tree の基礎と応用
概要
Binary Indexed Tree（BIT）は、単点更新と区間クエリを効率的に処理できるデータ構造です。計算量 O(log N) で操作を実行可能であり、競技プログラミングやアルゴリズム最適化で広く利用されます。
構造と原理
BIT は 2 進数表現に基づく構造を利用します。任意の整数は複数の 2 のべき乗和で表せることから、配列要素をべき乗区間で管理します。lowbit 演算（x & - ...
6月25日 18:51 投稿
AtCoder ABC389のアルゴリズム実装と解説
問題C: キューによる区間管理のシミュレーション
この問題では、列の先頭への追加や末尾からの削除、特定位置の要素へのアクセスを効率的に行う必要があります。全ての要素を個別に保持するとメモリや計算量が膨大になるため、連続する要素を「区間」として管理する手法をとります。
各区間について「先頭からの相対距離（開始位置）」と「区間の長さ」を構造体で定義し ...
6月6日 19:20 投稿