競プロ日記#25/05/04

アルゴ式

期待値の性質 (3)

• 結局和を取るだけだった

using Graph = vector<vector<int>>;

int main() {
    int N,M;
    cin >> N >> M;
    
    vector<int> A(N);
    vector<int> P(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> P[i];    
    }
    vector<int> B(M);
    vector<int> Q(M);
    for (int i = 0; i < M; i++) {
        cin >> B[i] >> Q[i];    
    }
    double ansEX = 0;
    double ansEY = 0;
    for (int i = 0; i < N; i++) {
        ansEX += A[i] * P[i];
        
    }

    for (int i = 0; i < M; i++) {
        ansEY += B[i] * Q[i];
        
    }

    ansEX /= 100;
    ansEY /= 100;

    cout << fixed << setprecision(10) << ansEY + ansEX << endl;
}

Q2. 右ビットシフト

• ビットシフトの性質を考えれば当然ではあるのだが7,6がそれぞれ右ビットシフトを1回行うと3になるの面白かった

「競技プログラミングの鉄則」

B06 - Lottery

• 最初は自分の考えた累積和の解法を使ったがWA
• ヒントにある「あたりの数・はずれの数それぞれについて累積和を計算」を参考にしてやっとAC。

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    vector<int> win(N);
    vector<int> lose(N);
    for (int i = 0; i < N; i++) {
        if (i == 0){
            if (A[i] == 0) {
                lose[i] = 1;
                
            } else {
                win[i] = 1;
            }
        }
        if (A[i] == 0) {
            win[i] = win[i - 1];
            lose[i] = lose[i - 1] + 1;
        } else {
            win[i] = win[i - 1] + 1;
            lose[i] = lose[i - 1];
        }
    }

            
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        int L, R;
        cin >> L >> R;
        L--;
        R--;
        if ((win[R] - win[L - 1]) > lose[R] - lose[L - 1]){
            cout << "win" << endl;
        } else if ((win[R] - win[L - 1]) < lose[R] - lose[L - 1]){
            cout << "lose" << endl;
        } else {
            cout << "draw" << endl;
        }
    }
}

A07 - Event Attendance

• 前日比用の累積和を考えるという点

int main() {
    int D, N;
    cin >> D >> N;
    int L[100009],R[100009],B[100009],Answer[100009];

    for (int i = 1;i <= N; i++) {
        cin >> L[i] >> R[i] ;
    }
    for (int i = 1;i <= N; i++) {
        B[L[i]]++;
        B[R[i] + 1]--;
    }
    Answer[0] = 0;
    for (int i = 1;i <= D; i++) {
        Answer[i] = Answer[i - 1] + B[i];
    }
    for (int i = 1;i <= D; i++) {
        cout << Answer[i] << endl;
    }
}

A08 - Two Dimensional Sum

• 普通に難しかった。流石に解説AC。
• とはいえアルゴ式とかよりも解説がより初心者向き躓きにくいようになっているので解説を読めばこのレベルの問題も全然理解できた。

int main() {
    int H,W;
    cin >> H >> W;
    int X[1509][1509];
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            cin >> X[i][j];
        }
    }
    int Q;
    cin >> Q;
    int A[100009], B[100009], C[100009], D[100009];
    for (int i = 1; i <= Q; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }

    int Z[1509][1509];
    for (int i = 0; i <= H; i++) {
        for (int j = 0; j <= W; j++) {
            Z[i][j] = 0;
        }
    }

    for (int i = 1;i <= H;i++){
        for (int j = 1;j <= W;j++){
            Z[i][j] = Z[i][j - 1] + X[i][j];
        }
    }

    for (int j = 1;j <= W;j++){
        for (int i = 1;i <= H;i++){
            Z[i][j] = Z[i - 1][j] + Z[i][j];
        }        
    }

    for (int i = 1;i <= Q;i++){
        cout << Z[C[i]][D[i]] - Z[A[i] - 1][D[i]] - Z[C[i]][B[i] - 1] + Z[A[i] - 1][B[i] - 1] << endl;
    }
}

B08 - Counting Points

• 例題のA08 - Two Dimensional Sumで学んだことをアウトプットするつもりが永遠に数値が合わなくて謎だった。
• 仕方なく解説を見たところ、この問題の入力値の都合上Nと平面の最大値との上下関係がわからない（要は点の座標としてあり得るのはx,yともに1500なので累積和の配列を1500 * 1500文初期化しないとおかしなことになる）のに間違えて勝手にN＊Nの平面で考えていた。

int main() {
    int N;
    cin >> N;
    int A[100009], B[100009], C[100009], D[100009];
    int X[1509][1509];
    for (int i = 1; i <= N; i++) {
        int x, y;
        cin >> x >> y;
        X[x][y] += 1;
        
    }
    int Q;
    cin >> Q;
    for (int i = 1; i <= Q; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }
    int Z[1509][1509];
    for (int i = 0; i <= 1500; i++) {
        for (int j = 0; j <= 1500; j++) {
            Z[i][j] = 0;
        }
    }
    // 横方向
    for (int i = 1; i <= 1500; i++) {
        for (int j = 1; j <= 1500; j++) {
            Z[i][j] = Z[i][j - 1] + X[i][j];
        }
    }
    // 縦方向
    for (int j = 1; j <= 1500; j++) {
        for (int i = 1; i <= 1500; i++) {
            Z[i][j] = Z[i - 1][j] + Z[i][j];
        }        
    }
    for (int i = 1; i <= Q; i++) {
        cout << (Z[C[i]][D[i]] - Z[A[i] - 1][D[i]] - Z[C[i]][B[i] - 1] + Z[A[i] - 1][B[i] - 1]) << endl;
    }
}

※1
25/05/03は「競技プログラミングの鉄則」にハマってやっていたので競プロ日記書くの忘れてました
※2
mdの見出しタグの中でリンクを使おうとするとバグるようになった。書き方変えるのですが、これまでの記事も治すとなるとだるすぎる