本記事では、代表的なアルゴリズム問題を題材に、配列走査、プレフィックス和、ビット操作、ハッシュマップによる高速化の4つの核心技術を解説します。各問題は段階的に難易度が上がり、実装の背景にある設計思想と数学的洞察を重視して解説します。

1. 中央要素の条件判定（初級）

整数配列 a が与えられる。インデックス i（先頭と末尾を除く）について、a[i] ≥ a[i-1] + a[i+1] を満たす個数を数える。

アプローチ

• 配列の中央要素（インデックス1～n-2）を順にチェック
• 左右隣接要素の和と比較し、条件を満たす場合カウントアップ

コード例

n = int(input())
arr = list(map(int, input().split()))

count = 0
for idx in range(1, n - 1):
    left_val = arr[idx - 1]
    right_val = arr[idx + 1]
    if arr[idx] >= left_val + right_val:
        count += 1

print(count)

注意点

• ループ範囲：range(1, n-1)（0-indexedで両端を除外）
• 比較演算子：>=（等号を含む）

2. 状態遷移の区間集計（中級）

0と1からなる文字列 s が与えられる。「1→0」の遷移が発生する位置を「成功イベント」と定義し、複数の区間クエリに対して各区間内の成功イベント数を高速に応答する。

アプローチ

• 各位置 i について、s[i-1]=='1' and s[i]=='0' なら成功イベント
• プレフィックス和配列 prefix を構築：prefix[i] = i番目までの累積成功回数
• クエリ [l, r) に対しては prefix[r-1] - prefix[l-1] で計算

コード例

import sys
input = sys.stdin.readline

length = int(input())
state_str = input().strip()
query_count = int(input())

# プレフィックス和配列の構築
prefix_events = [0] * length
for pos in range(1, length):
    prev_char = state_str[pos - 1]
    curr_char = state_str[pos]
    if prev_char == '1' and curr_char == '0':
        prefix_events[pos] = prefix_events[pos - 1] + 1
    else:
        prefix_events[pos] = prefix_events[pos - 1]

# クエリ処理
for _ in range(query_count):
    left, right = map(int, input().split())
    start_idx = max(0, left - 1)
    end_idx = min(length - 1, right - 1)
    result = prefix_events[end_idx] - prefix_events[start_idx]
    print(result)

注意点

• イベント判定条件：直前の文字が'1'かつ現在が'0'
• 境界処理：left-1が負にならないようmax(0, ...)でガード

3. 区間ORクエリのビット単位最適化（上級）

整数配列に対する複数の区間ORクエリを高速に処理する。OR演算はビットごとに独立している性質を利用し、各ビット位置ごとにプレフィックス和を事前計算する。

アプローチ

• 各ビット位置（0～30）について、そのビットが立っている要素の個数をプレフィックス和で管理
• クエリ時、各ビット位置で区間内に1が存在すれば、結果の該当ビットを立てる

コード例

from itertools import accumulate
import sys
input = sys.stdin.readline

size, queries = map(int, input().split())
data = list(map(int, input().split()))

# 各ビット位置ごとのプレフィックス和を格納
bit_prefix = []
for bit_pos in range(31):
    bit_flags = [(num >> bit_pos) & 1 for num in data]
    bit_prefix.append(list(accumulate(bit_flags)))

# クエリ処理
for _ in range(queries):
    l, r = map(int, input().split())
    l_idx = l - 1
    r_idx = r - 1
    result_value = 0
    
    for bit in range(31):
        if l_idx == 0:
            ones_count = bit_prefix[bit][r_idx]
        else:
            ones_count = bit_prefix[bit][r_idx] - bit_prefix[bit][l_idx - 1]
        
        if ones_count > 0:
            result_value |= (1 << bit)
    
    print(result_value)

注意点

• ビット演算の優先順位：シフト後にビットマスクを適用
• 31ビットで十分：符号なし32ビット整数の範囲に対応

4. XOR部分配列と平方数の非該当カウント（最上級）

配列の部分配列のうち、XOR結果が平方数でないものの個数を求める。補集合の考え（全体－該当数）とプレフィックスXOR＋ハッシュマップの組み合わせで効率化。

アプローチ

• 全部分配列数：n*(n+1)/2
• プレフィックスXOR配列を構築：preXor[i] = a[0]^a[1]^...^a[i]
• 部分配列[l,r]のXOR = preXor[r] ^ preXor[l-1]
• 平方数xに対して、preXor[l-1] = x ^ preXor[r] を満たす(l-1)の出現回数をハッシュで管理

コード例

n = int(input())
elements = list(map(int, input().split()))

# プレフィックスXOR配列
prefix_xor = [0] * n
prefix_xor[0] = elements[0]
for i in range(1, n):
    prefix_xor[i] = prefix_xor[i - 1] ^ elements[i]

square_match_count = 0

# 平方数を列挙（0～199^2まで）
for root in range(200):
    target_square = root * root
    xor_freq = {0: 1}  # 空のプレフィックスを初期値として登録
    
    for right_end in range(n):
        needed_prefix = target_square ^ prefix_xor[right_end]
        square_match_count += xor_freq.get(needed_prefix, 0)
        current_xor = prefix_xor[right_end]
        xor_freq[current_xor] = xor_freq.get(current_xor, 0) + 1

total_subarrays = n * (n + 1) // 2
result = total_subarrays - square_match_count
print(result)

注意点

• ハッシュ初期化：{0: 1}（空配列に対応）
• 更新タイミング：現在の値を参照した後で辞書を更新
• 平方数の範囲：入力値の最大値に基づいて調整