ABC 363 E — Sinking Land

考察

区画は海へ接するまでは沈まず、年kに初めて海へ接したならmax(k,A_{i,j})年に沈む。沈没時刻は隣接区画の沈没から一方向に伝播する。

標高と年Yが整数で上限も小さいため、沈没予定年ごとのbucketを用意できる。同じ年のbucketへ追加された低地もその年中に連鎖して沈む。

採用する候補: 外周を初期海岸として、沈没年bucketを1..Yの順に処理し、新たに接した隣接区画を予定年へ登録する。

棄却する候補: 各年ごとに全gridを走査し、海に接する高さ以下の区画がなくなるまで更新する。

地形が一列ずつ沈む場合に同じcellを年ごと・連鎖段階ごとに繰り返し調べる。

remaining=HWとし、外周の未登録cellを標高bucketへ入れる。k=1..Yでbucket[k]をqueueとして最後まで処理し、cellを沈めてremainingを減らす。未登録の四近傍はyear=max(k,A)がY以下ならそのbucketへ登録する。各年処理後のremainingを出力する。

典型の発動条件

時刻bucket付きflood fill

発動条件: event時刻が小整数で、到達により将来eventが一度だけ発生するとき。

priority queueの代わりに年別queueを昇順処理する。

境界からの浸水伝播

発動条件: 外部と連結した低い領域だけが閾値に応じて有効化されるgrid問題。

外周をsourceとし、到達時刻とcell固有閾値のmaxを次時刻にする。

問題固有の要素

単にA≤kのcellを消すのではなく、海への連結性が満たされた時刻とのmaxが実際の沈没年になる。

別の問題へ持ち帰る視点: 閾値と到達性が組み合わさる過程では、event時刻をmax(arrival,threshold)で伝播する。

正当性

外周cellは時刻0に海へ接したとみなし、A≤Yならbucket Aへ入れる。visitedは沈没時でなく初回登録時に立てて重複投入を防ぐ。 年kに沈むcellの隣がA≤kなら同じbucket kの末尾へ入るため、一年内のflood fillも通常queue処理に含まれる。 各cellを海へ接した最初の一度だけ登録し、その年までの沈没数を逐次集計できる。

実装上の注意

  • 四隅を外周四辺から重複登録しない。A>Yのcellもvisited扱いをどうするか統一し、同年bucketの動的追加を最後まで処理する。

復習の核

  • 低い盆地が高い外壁の沈没年に同時連鎖する例を追う。visitedを「海へ接した」時点にする理由とbucketへの登録年をセットで検証する。

計算量と制約

時間

O(HW+Y)、各cell一回登録・沈没、Y年のbucket。

空間

O(HW+Y)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq H, W \leq 1000; 1 \leq Y \leq 10^5; 1 \leq A_{i,j} \leq 10^5; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Sinking Land の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: event順にactive集合を更新する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: event・値順のオフライン走査

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: event順にactive集合を更新する

      • 値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。

      この解説で扱わないこと:

      • 更新を単に逆順へ読む処理、答えの局所寄与だけを集計する順序交換、sort-uniqueしたkeyの添字化、および固定方向の単純scan。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題