第22回日本情報オリンピック　二次予選

2022年12月13日
情報オリンピック日本委員会

解説

解説担当：松尾凜太朗

小課題 1

西風の嵐では西から順に，東風の嵐では東から順に，強さと同じ数だけの区画を見ていきます． 「今見ている区画より左の区画の標高の最大値」を持ちながら今見ている区画の標高が減るかを判定していけば， 全体で時間計算量 O(N Q) で処理することができます．

小課題 2

嵐はすべて強さ N であるという制約の小課題です．

i 日目の出来事の直前に，「それより西のどの区画よりも(真に)標高が高い区画」の番号の集まりを l_i， 「それより東のどの区画よりも(真に)標高が高い区画」の番号の集まりを r_i で表すことにします． たとえば 5 日目の出来事の直前に各区画の高さが西から順に 3, 2, 4, 4, 1, 3 だったとすると l_i = { 1, 3 }, r_i = { 4, 6 } です． また，l_i と r_i の要素を合わせたものを t_i とします． すると，この小課題に限らず一般に次のことが成り立ちます．

• l_i のどの要素も， r_i のどの要素よりも小さい．
• i 日目の直前において，区画 j の標高について次のことが成立する．
  t_i に含まれる要素のうち， j 以下で j に一番近いものを L， j 以上で j に一番近いものを R とする．
  i 日目の直前の区画 j の標高は，その時点での区画 L と区画 R の標高，及び初期状態の区画 j の標高の 3 つの値の最小値である．

また，強さ N の嵐しか起こらないこの小課題では以下のことが成り立つことが分かります．

• l_{i + 1} は， l_i のうち大きい方からいくつか ( 0 個の可能性もある) を取り除いてできる． r_{i + 1} は r_i のうち小さい方からいくつか ( 0 個の可能性もある) を取り除いてできる．

最後の項目については，嵐が起きた時の各地点の標高の変化を考えると帰納的に示せます．
従って，嵐に応じて l_i の大きい方， r_i の小さい方からそれぞれ適切に要素を削除し， 今 l_i, r_i に入っている番号の区画の標高が開始から何 m 減ったかを記録していくとよいです． 標高を報告する際には l_i, r_i の中で二分探索をして L, R を出すことで， 求める標高を計算することができます． 計算量は O((N + Q) log(N)) となります．

小課題 3

この小課題では，以下のことが成り立ちます．

• 任意の時点で，標高が最大値をとる地点の番号は 1 つの区間で表すことができる． i 日目の直前において，標高が最大値をとる地点の番号が u_i 以上 v_i 以下であるとする．( u_i ≦ v_i )
• i 日目に強さ x の西風の嵐が起こる時 : 西から数えて min (x, v_i) 個の区画の標高が 1 減り，それ以外の区画の標高は変わらない．
  
  • x < v_i のとき， l_{i + 1} = max ( u_i, x + 1), r_{i + 1} = v_i となる．
  • x ≧ v_i のとき， l_{i + 1} = u_i， r_{i + 1} は，この嵐の直後の時点の区画 v_i から東にで区画 v_i と等しい標高が連続する一番東の区画の番号となる．
• 東風につていも，西風の場合と左右対称で同様のことが起こる．

従って，区間加算と区間最小値取得の機能を持つ遅延伝播セグメント木と呼ばれるデータ構造で各区画の標高を数列として管理すればよいです．

「区画 v_i から東にで区画 v_i と等しい標高が連続する一番東の区画」については，数列を a として， a の v_i, v_i + 1, …, j 番目の最小値が a_vi と等しくなる最大の j を求めればよいので，二分探索をすればよいです．

単純に二分探索して O(log(N)) 回セグメント木に対して最小値クエリを行うと時間計算量は全体で O(N + Q (log(N))²) となります． また，セグメント木の内部構造に立ち入って二分探索を行うと 全体で O(N + Q log(N)) とすることもできます．

小課題 4

この小課題の解法は本質的に小課題 5 の解法と同じ ( 2 種類の嵐のうち片方だけ処理するとこの小課題の解法になる) なので，小課題 5 の解法を参照してください．

小課題5 (満点)

小課題 2 の項で定義した l_i, r_i を管理していく方針をとります． 小課題 2 の項で「一般に次のことが成り立ちます．」とある項目の内容はこの小課題でも使うことができます． i 日目の強さ x の西風の嵐のときを考えます． l_i の要素で小さい方から j 番目のものを l_i,j で表すこととします．

• x が r_i の最小値以上の場合 : 小課題 2 と同様に r が変化する． l は， l_{i + 1} = l_i で変化しない．
• x が r_i の最小値未満の場合 :
  l_i の要素のうち， x 以下で x に一番近いものを L とする． l_i の要素のうち， x より大きく x に一番近いものを R とする． そのようなものが存在しなければ r_i の最小値を R とする．
  もし x < j < R となる j であって，嵐の直前に区画 j と区画 L の標高が等しかったような j が存在すれば，そのうち最小のものは新たに l_{i + 1} に入る．l_{i + 1} からは R が削除されるかもしれない． このような区画 j は今までに 1 度も標高が変化していないため，元の数列 A について「x 番目より後で初めて y 以上となるのは何番目か」という質問に答えることによって求めることができる．

東風の嵐の場合も左右対称の処理をすればよいです． 元の数列 A についての「x 番目より後で初めて y 以上となるのは何番目か」という質問については， 最大値取得の機能を持ったセグメント木上での二分探索や， 最大値を保持したダブリングと呼ばれている手法により O(log(N)) の計算量で答えることができます． l_i, r_i は例えば C++ における std::set を用いて管理すると O(log(N)) で新たな要素の追加，二分探索ができます． また， l_i, r_i に含まれる区画のうち西から，または東からいくつかの区画に 1 を足す処理は遅延セグメント木を使うことで O(log(N)) で実現できます．(差分を管理すれば一点加算区間和取得のセグメント木や Binary Indexed Tree で済みます．) 以上より，この問題は O((N + Q) log(N)) で解くことができます．