Wdoi R2 プログラミングコンテスト問題解法
本記事では、プログラミングコンテスト「Wdoi R2」の問題に対する解法を解説します。各問題の戦略と実装の詳細について見ていきましょう。
問題 A: 幻の如く咲く花
解法
配列に対する操作は「要素の反転」と「整数値の加算」の2種類です。配列を反転させる操作は、最大でも1回行えば十分です。なぜなら、2回反転させると元に戻るためです。したがって、反転操作を行う場合 ...
8月7日 20:25 投稿
数列の部分ソート後の指定位置値の特定
問題概要
1からnまでの順列に対してm回の部分ソート操作を実行し、q番目の位置にある数値を求める問題。ソート操作は昇順または降順のどちらかで、指定された区間内の要素を並び替える。
入力形式
n m
a_1 a_2 ... a_n
op_1 l_1 r_1
...
op_m l_m r_m
q
解法概要
二分探索とセグメント木を組み合わせたO(n log²n)のアルゴリズムを使用する。重要なのは「ある値Xより大 ...
5月22日 19:15 投稿