HOME
情報オリンピック予選

「情報オリンピック予選」の記事一覧

行列累乗を用いてフィボナッチ数列の第N項を求める計算量はどれか。

2×2の行列の累乗を繰り返し二乗法で行うため、対数時間で計算できる。

2026年4月30日

山から石を取るゲーム「Nim（ニム）」において、勝敗を決定する値はどれか。

全ての山の石の数の排他的論理和（ニム和）が0でないなら先手必勝である。

2026年4月30日

座標圧縮が必要になる主な状況はどれか。

値の大小関係のみが重要な場合に、値を1から始まる小さな整数に変換して扱う。

2026年4月30日

平面上のN個の点集合を包含する最小の凸多角形を求める問題を何と呼ぶか。

全ての点を包み込む、最も外側の境界となる凸多角形のことである。

2026年4月30日

平衡二分探索木の一種で、ノードの回転操作を用いて高さを低く保つものはどれか。

挿入・削除のたびにバランスを調整し、検索効率をO(log N)に保つ。

2026年4月30日

文字列検索アルゴリズム「KMP法」の計算量はどれか（本文長N、パターン長M）。

一度の走査で一致位置を特定するため、線形時間で動作する。

2026年4月30日

逆元（aのmを法とする逆数）を求めるために必要な条件はどれか。

フェルマーの小定理や拡張ユークリッドの互除法を用いる際、互いに素であることが必須。

2026年4月30日

巡回セールスマン問題を動的計画法で解く際の計算量はどれか（頂点数N）。

ビットDPを用いることで、指数関数的ではあるが階乗よりは高速に解ける。

2026年4月30日

フェニック木（Binary Indexed Tree）が主に解決する課題はどれか。

セグメント木より限定的な機能だが、実装が非常に簡潔で高速な区間和管理構造。

2026年4月30日

木構造上での動的計画法（木DP）において、計算の順序はどうなることが多いか。

子ノードの結果を統合して親の状態を決めるため、ポストオーダー（帰りがけ順）で行う。

2026年4月30日