競プロ日記#25/04/23

アルゴ式-和が K 以上のペア

• 2変数と見せかけて片方を固定して固定しているN回のforの中でK - A[i]に二分探索を仕掛けに行く。

int main() {
  int N, K; cin >> N >> K;
  vector<int> A(N);
  for (int i=0; i<N; i++) cin >> A[i];

  // 配列 A を昇順にソートする
  sort(A.begin(), A.end());

  long long count = 0;
  for (int i=0; i<N; i++) {
    // 二分探索
    int left = 0, right = N;
    while (left!=right) { // 解が求まるまで
      // left と right の 中点 mid をとる
      int mid = (left+right)/2;
      if (A[mid]>=K-A[i]) { // もし A[mid] >= B[i] ならば答えは left 以上 mid 以下
        right = mid; // 範囲を狭める
      }
      else { // そうでなければ答えは mid+1 以上 right 以下
        left = mid+1; // 範囲を狭める
      }
    }
    count += N - left;
  }

  cout << count << endl;
  return 0;
}

アルゴ式-何番目の重さ？

• シンプルな二分探索で実装はできた。
• ただ、出力内容が「left」だと1だけ余分に増えた値になる（答えが「0,1,2,3,4」なのに「1,2,3,4,5」）
  もちろん出力の値を「left - 1」にすればACになったのだがこうなる原因が具体的にわからなかった。
  →GPT先生に聞いたら俺のコードはleftの終端が大なりで終わるようになっているから。つまりi = 0でA[0]が1の場合の「1 2 4 5 7 8」の例だとW[mid]がA0より大きい2の位置(添え字でいうと1)で終わるようになっているかららしい。言われてみれば確かに（てか自分で実装してるんだからわかれよ（笑）というかソートしたものと元のやつを扱ってるから頭がこんがらがった）

int main() {
    long long N;
    cin >> N;
    vector<long long> W(N);
    for (long long i = 0;i < N;i++){
        cin >> W[i];
    }
    vector<long long> A(N);
    for (long long i = 0;i < N;i++){
        A[i] = W[i];
    }
    sort(W.begin(), W.end());
    for (long long i = 0;i < N;i++){
        long long left = 0;
        long long right = N;
        
        while (left != right){
            long long mid = (left + right) / 2;
            if (W[mid] > A[i]){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        cout << left - 1 << endl;
        
    }
}

アルゴ式-段階評価

• 割とシンプルな二分探索問題。ここに来てやっと簡単な二分探索を使いこなせるようになった感

int main() {
    int N,K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0;i < N;i++){
        cin >> A[i];
    }
    vector<int> B(K);
    for (int i = 0;i < K;i++){
        cin >> B[i];
    }
    sort(B.begin(), B.end());
    for (int i = 0;i < N;i++){
        int left = 0;
        int right = K;

        if (A[i] >= B[K-1]){
            cout << K << endl;
            continue;
        }
        
        while (left != right){
            int mid = (left + right) / 2;
            if (B[mid] > A[i]){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        cout << left << endl;
    }
}