日本沈没
問題はこちら
自分が気づいたところ
小課題1に関しては，愚直にシミュレーションしていけば求まるが，満点をもらうことはできない．
のように，谷になっているものに注目した．すると，問題は「谷となっているところのうち，一番低いところ
と，左右の崖のうち低い方
の間の区間
が，一番重なっているところはどこか」という風に言い換えることができる．
...しかし区間の重なりと捉えたところで計算量が落ちるわけではないのでよく分からない...
解説を読んで
状態ごとに捉えてみる．具体的には，「注目している陸地が一つ沈んだ時に島の数はどうなるか？」について注目する．すると，注目している陸地の左右に注目するだけで変化を捉えることができる．考えていることは近いが，自分は谷に注目していたので処理が煩雑になっていた...
そこで，陸地をsortして順番に海面を上げていき，陸地の数の増加を数えれば良い．計算量はsortがボトルネックとなり
Submission #4936590 - JOI2018/2019 予選ページ
自分の詰まったところ
- 陸地が同じ高さで連続している時に，余分に引き算をしていたので，入力を読み込む時に連続しているものは弾くことが必要．
- 全ての陸地が0の時にバグが発生すので，陸地の入力の最初と最後に高さ0を入れることで解決．
学んだこと
- 注目するものを転換するということは大事だと思った．一つのものに注目していて解法が出ない時，その対照的なものに注目すると答えにつながる可能性がある．
- 状態ごとに捉える（i-1回目からi回目への遷移でどのように答えが変化するか）ことが苦手なので，トレーニングが必要．
- 重複は入力の時点で弾く．
- コーナーケースに対しては，入力の両端に自分で何か加えるとうまくいくことも多い（lower_bound()の時などが思い返される...）
