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

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

問題
  日本沈没 2 (Japan Sinks 2) (配点 100点)
  時間制限 : 3 sec / メモリ制限 : 1024 MB

解説

解説担当:松尾凜太朗

小課題 1

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

小課題 2

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

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

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

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

小課題 3

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

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

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

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

小課題 4

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

小課題5 (満点)

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

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