C-merのブログ

ザ・雑記

AtCoder Beginner Contest 103 D - Islands War

問題
AtCoder Beginner Contest 103 D - Islands War
D - Islands War

使用言語
C++

方針
・取り除く必要のある橋の本数の最小値を求める.島は直線上に並んでいる.
→狭い区間で争いが起きていたら,その外側は必ず行き来できなくなるので気にしなくて良い
→mapで東側の最も近い敵の場所を管理

・取り除く必要のある橋の本数の最小値を求める==壊さない橋の本数を最大化する
→橋を前から順に見ていき,本当に橋を壊す必要があるところまでは壊さない.

ex)
1-2-3-4-5

1 4で争う時,前から見ていくと3のところで橋を壊せば良い
1-2-3|4-5

2-5で争う(ことのみを考える)時,前から見ていくと5のところで橋を壊せば良い
1-2-3-4|5

これらを組み合わせる
まず島1について,最も東側だとして3と4の間の橋を壊せば良い
1-2-3-4-5

島2について,島1の理由で3と4の間の橋を壊されるので,5のことは気にしなくても良い
1-2-3-4-5

島3について,争ってはいないがこれ以上橋をかけたまま東の島を見るわけにはいかないので橋を破壊(ans++)
これ以上,破壊する必要のある橋は今の所ない(r=INF)(もし島3と争っている島があったとしたら,その島の手前の橋を壊すべき橋とする)

ex2)
1-2-3-4-5-6-7-8-9
1-2-3-4-5-6-7-8-9
1-2-3-4-5-6-7-8-9
1-2-3-4-5-6-7-8-9
1-2-3-4|5-6-7-8-9
1-2-3-4|5-6-7-8-9
1-2-3-4|5-6-7-8-9
1-2-3-4|5-6-7-8-9
1-2-3-4|5-6-7-8|9


所感
・union find木っぽさあるが削るし,有り難く直線なので違う
・好きな問題ではある
・コンテスト中に解き終わりたかった

コード

int N, M;
map<int, int> mp;

int main()
{
  cin>>N>>M;
  REP(i,M) {
    int a, b;
    cin>>a>>b;
    if (mp[a] > b || mp[a] == 0) mp[a] = b;
  }

  int l, r = INF, ans = 0;
  FOR(l,1,N+1) {
    if (mp[l] != 0) {
      r = min(mp[l], r);
    }

    if (l>=r) {
      ans++;
      r = mp[l] == 0 ? INF : mp[l];
    }
  }

  cout<<ans<<endl;

  return 0;
}