ABCの解き直しをやっていて、ちょっと悩みましたがなんとか解き切りました。解説を見てみると、ちょっと効率の良い解法だったので一応残します。
解法
各島について西側からなめつつ、自身より西側のみを考える。
自身より東側に仲の悪い島がある場合、その島に到達した際に自身との関係性を決めることができるので、東側については考える必要はない。
さらに言うと、各島について自身に最も近い仲の悪い島のみを考えれば十分である。なぜなら、その島と陸続きでなくなった時点で、それより遠い島との関係性も断絶するためである。
次はどこで橋を落とすか考えると、これは未だ自身と仲の悪い島が陸続きになっている場合に必ず落とす必要があり、自身のすぐ西の橋を落とすのが最適となる。これは、
- 自身より西側の島同士の関係はすでに決定されているため、西側の島にとって最適な橋の落とし方は考えなくてよい
- 自身より東側の島について考えると、陸続きになっていない島が多ければ多いほど、仲の悪い島が陸続きであり続けている場合が明らかに減る
ということからわかる。
これらの考察から、以下の方針でACを取ることができる。
- 長さの配列を用意し、各島について、自身より西にいる仲の悪い島のうち、最も東の島をメモする。(=自身より小さいかつ最大のインデックスを持つ仲の悪い島をメモする)
- 東から見て陸続きになっている最も西の島をメモしながら、配列をなめる。
- 仲の悪い島が陸続きな場合は、陸続きな最も西の島を自身に更新しつつ、解を更新する。
初めのメモは単に入力をなめればよいだけなので、その後の操作もメモしたサイズの配列をなめるだけなのでとなり、全体でとなる。
コードは以下の通り。