競技プログラミングの問題解決力を鍛えるには、基本的なアルゴリズムやデータ構造について深く理解することが重要です。本記事では、アルゴリズムの時間計算量、グラフ理論、文字列処理、データ構造などの分野からクイズを厳選し、これらの基礎知識を確認していきます。プログラミングの技術的な側面に加えて、論理的思考力や問題解決能力の向上にも役立つはずです。ぜひ、以下のクイズに挑戦してみてください。
Q1 : 二部グラフの最大マッチングを求める際に自然に使える手法はどれか？
二部マッチングは左部と右部をそれぞれ頂点集合とみなし、源点から左部へ、右部から終点へ容量1の辺を張り、元の辺に容量1を与えることで最大流問題に還元できます。これによりFord-FulkersonやDinicなどの最大流アルゴリズムを用いると最大マッチングが求まります。これは二部特有の標準解法の一つです。
Q2 : 二分探索（バイナリサーチ）で正しく使うために述語（predicate）が満たすべき一般的な性質は何か？
バイナリサーチが成立する本質は探索空間に対する述語が単調であること（あるしきい値を境に真から偽またはその逆に一度だけ変化する）です。配列がソートされていることはよくある具体例ですが、本質は単調性であり、探索対象は実数や他の順序集合でも可能です。これを満たさないと二分探索は誤動作します。
Q3 : KMP法（Knuth-Morris-Pratt）のテキスト長n、パターン長mに対する時間計算量は？
KMP法はパターンの接頭辞関数（failure function）をO(m)で前処理し、テキストを走査するときに部分一致情報を利用して巻き戻しを繰り返さずマッチングを進めます。その結果、全文検索の照合処理はO(n)、前処理と合わせて総計O(n+m)の時間でパターン検索が可能となります。
Q4 : 区間加算（区間に値を足す）と区間和（ある区間の合計を求める）という二種類の操作を両方高速に処理する実装として一般に使われる方法はどれか？
区間加算と区間和の両方をO(log n)で処理する一つの方法はFenwick木を2本使う差分テクニックです。一方のBITで加算量の累積を、もう一方で位置に応じた係数を管理することで任意区間の和を求められます。遅延伝播付きセグメントツリーでも可能ですが、ここでの選択肢としては2本のBITが正答になります。
Q5 : Union-Find（Disjoint Set Union）は頂点の結合（マージ）と接続判定に高速だが、一般に『削除（要素の分離）』操作をサポートするか？
標準的なUnion-Findは要素集合の併合（Union）と代表者検索（Find）を効率的に行いますが、要素を集合から取り除く（分離する）操作は逆操作として自然には定義されていません。分離をサポートするためには別途動的木（link-cut tree）やオフライン処理、履歴を持つデータ構造などを用いる必要があり、通常の実装ではサポートされません。
Q6 : 無向グラフにおけるオイラー路（すべての辺をちょうど一度通る道）の存在条件として正しいものはどれか？
無向グラフでオイラー路（始点と終点が一致しない場合を含む）が存在するための条件は、グラフの各辺が同じ連結成分内にあり（非孤立部分の連結）、奇数次数の頂点がちょうど0個または2個であることです。0個ならオイラー巡回（閉路）が存在し、2個なら開いたオイラー路が存在します。次数がすべて偶数は巡回の条件であり、次数>=2や辺数>頂点数は必要十分条件ではありません。}
Q7 : 配列の逆転数を効率的に求める代表的なアルゴリズムの時間計算量は？
逆転数（ia[j] の個数）はマージソートを応用して求める方法や、座標圧縮した上でFenwick木（BIT）を使う方法が典型的です。どちらも各要素について対数時間の集計・更新を行うため全体でO(N log N)の時間で計算できます。単純比較ではO(N^2)になり大きな入力に不向きです。
Q8 : Dijkstra法は負の重み辺が含まれるグラフでも常に正しく動作するか？
Dijkstra法は「未確定の最短距離の中で最小のものを確定する」という貪欲戦略を取り、これは全辺の重みが非負であることを前提に正当性が保証されます。負の重みがあると、確定したはずの頂点に後からより短い経路が現れる可能性があり、誤った結果を返すためBellman-Ford法など負辺を扱えるアルゴリズムを使う必要があります。
Q9 : 有向グラフにトポロジカルソートが存在するための必要十分条件はどれか？
トポロジカルソートは頂点を「すべての有向辺が前から後ろに向く」順序に並べる操作であり、閉路（サイクル）が存在する場合は矛盾が生じて並べられません。したがって向き付き閉路を持たない有向非巡回グラフ（DAG）であることが必要かつ十分です。連結性や重み、頂点数と辺数の大小は直接の条件ではありません。
Q10 : エラトステネスの篩（Sieve of Eratosthenes）の典型的な時間計算量はどれか？
エラトステネスの篩では小さい素数pについてその倍数を消す処理を行い、各整数kに対して1/ p の期待回数だけ処理が行われるため総和は n (1/2 + 1/3 + 1/5 + …) に近く、素数逆数和の漸近はlog log nに比例します。従って全体の時間計算量はO(n log log n)となります。
まとめ
いかがでしたか？ 今回は競技プログラミングクイズをお送りしました。
皆さんは何問正解できましたか？
今回は競技プログラミングクイズを出題しました。
ぜひ、ほかのクイズにも挑戦してみてください！
次回のクイズもお楽しみに。
