HOME
情報オリンピック予選

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

重み付きグラフの全頂点ペア最短経路を、負の辺がない場合にV回ダイクストラを行って解く計算量はどれか。

1回のダイクストラにO(E log V)かかるため、それをV回繰り返すとこの計算量になる。

2026年4月30日

国際情報オリンピック（IOI）の参加資格として定められている年齢制限（卒業年度等）はどれか。

IOIは大学教育を受ける前の生徒（主に高校生以下）を対象とした競技である。

2026年4月30日

「走査線（スウィープライン）アルゴリズム」が用いられる代表的な問題はどれか。

仮想的な線をスライドさせながら、イベント点ごとに状態を更新して処理する。

2026年4月30日

桁DP（Digit DP）において、状態として管理される典型的なフラグはどれか。

「未満フラグ」を持つことで、与えられた数値以下の条件を満たす数を数え上げる。

2026年4月30日

中国剰余定理（CRT）が解く問題の種類はどれか。

異なる法（mod）に対する余りが与えられたとき、元の数を特定する定理である。

2026年4月30日

木構造における「最小共通祖先（LCA）」を求めるための代表的な手法はどれか。

2^k個上の親を記録しておくことで、任意のペアの共通祖先をO(log N)で求める。

2026年4月30日

「最小費用流問題」を解くために、最短経路の反復を利用する手法はどれか。

ポテンシャルを利用して負の辺を除去し、ダイクストラを繰り返す手法が一般的。

2026年4月30日

Suffix Array（接尾辞配列）を構築する際、もっとも高速なアルゴリズムの計算量はどれか。

SA-IS法などの高度なアルゴリズムを用いると、線形時間で構築が可能である。

2026年4月30日

平方分割（Square Root Decomposition）において、バケットのサイズは通常どれくらいか。

全体をルートN個のブロックに分けることで、更新とクエリのバランスを最適化する。

2026年4月30日

二部グラフの最大マッチング問題を、最大流問題として解く際の始点と終点の役割はどれか。

ソースから一方の集合、もう一方はシンクへ繋ぎ、容量1の辺を張ることで解ける。

2026年4月30日