G. Old Floppy Drive ～それ、二分探索で求めても間に合うよ～

• Quiz
  • https://codeforces.com/contest/1490/problem/G
• AC
  • https://codeforces.com/contest/1490/submission/107711008
• 解説（というか感想）
  • 何周かして、最後の1周のどこでxに到達できるかという2段階で考える
  • 何周すればいいかは数学でO(1)で求まるが、（周の中のピークも考える必要があり）私は混乱してしまった
  • 冷静になってみると「何周するか？」も二分探索で求まる。これなら混乱せず解けた
• 学び
  • 数学的にO(1)で解ける箇所でも二分探索で間に合うならそれで解くことで混乱を避けられる

ARC112「B - -- - B」

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

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

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;
}

C. Minimum Ties

• Quiz
  • https://codeforces.com/contest/1487/problem/C
• AC
  • paste TODO
• 解説
  • グラフにして矢印でwin/loseを表すと、大抵はwin/loseを割り当てられることが分かる

一般化

• 一般にNが偶数の時はtieがN/2個あり、Nが奇数の時は全てwin/loseを割り当てられる

D. Pythagorean Triples

• Quiz
  • https://codeforces.com/contest/1487/problem/D
• AC
  • https://codeforces.com/contest/1487/submission/107464174
• 解説
  • 式変形をして性質を見つけて(b+1==c), aの探索範囲を狭めて全探索する

TLE?

• TLギリギリな気がするが、最大ケースを作成して2秒に間に合ってので提出。AC

ARC112「A - B = C」

• Quiz
  • https://atcoder.jp/contests/arc112/tasks/arc112_a
• AC
  • https://atcoder.jp/contests/arc112/submissions/20196184
• 解説
  • L<=A<=Rなどの制約が扱いづらいので、全体からLを引いて0<=a<=R-L (A-L=aとおく)として扱いやすくする
  • 満たすべき条件「A = B + C」もそれに従ってa,b,cの式になる（下図）
  • 後は式変形していくと数えられる（下図）

void solve(){
  ll l,r;cin>>l>>r;
  ll d = r-2*l+1;
  if(d<0){
    p(0);return;
  }
  ll ans = d * (d+1) / 2;
  p(ans);
}

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

    // input
    ll N; 
    cin>>N;
    
    while(N--)solve();
    
    return 0;
}

別解：L,Rのまま図形的に考える

• 最終的には上の解法と同じ式に帰着する
• 条件を満たすのは下図のように三角領域になるので、辺の長さが分かれば求まる
• 辺の長さは値域から求まる