ARC112「B - -- - B」

  • Quiz
  • AC
  • 解説
    • 数直線で考える
    • 到達できる箇所は2つの範囲になる（重なることもある）
    • 左に行くのと右に行くコストが非対称なので、bを場合分けすれば混乱せず書けるだろう
  • 学び
    • 最初、画像左のようにグラフで考えていたのは失敗。辺コストが1,2なので制約(109)を考えるとグラフアルゴリズムは適用しづらい
    • 行ける範囲が連続であることを考えると数直線で考えるほうが自然

図：左はグラフで考えた失敗例。右は数直線で考えた成功例

f:id:peroon:20210216210136p:plain

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll b,c;
    cin>>b>>c;

    vector<PII> V; // ranges

    if(b==0){
      ll left = b-c/2;
      ll right = b + (c-1)/2;
      ll ans = right-left+1;
      p(ans);return 0;
    }
    else if(b>0){
      // right range
      ll right_right = b+(c-2)/2;
      ll right_left = b-c/2;
      V.emplace_back(right_left, right_right);

      // left range
      ll left_left = -b - (c-1)/2;
      ll left_right = -1 * (b - (c-1)/2);
      V.emplace_back(left_left, left_right);
    }
    else{
      // b<0
      // left range
      ll left_left = b - c/2;
      ll left_right = -1 * (-b - (c-2)/2);
      V.emplace_back(left_left, left_right);

      // right range
      ll right_right = -1 * (b - (c-1)/2);
      ll right_left = -b - (c-1)/2;
      V.emplace_back(right_left, right_right);
    }

    ll ans=0;
    sort(ALL(V));
    if(V[0].second>=V[1].first){
      // 重なる
      ans = V[1].second - V[0].first + 1;
    }
    else{
      // 重ならないので独立に
      ans += V[0].second - V[0].first + 1;
      ans += V[1].second - V[1].first + 1;
    }
    p(ans);
    
    return 0;
}