AtCoder ABC121

競技プログラミング

3完。

A

数学苦手だから5分もかかってしまった。

signed main() {
    int H, W, h, w;
    cin >> H >> W >> h >> w;
    int white = (H-h) * (W-w);
    cout << white << endl;
}

B

各行ごとに計算していく。考察よりもコード書く方に時間を取られた。

signed main() {
    int N, M, C;
    cin >> N >> M >> C;
    vector<int> bs(M);
    for (auto &b : bs) {
        cin >> b;
    }
    vector<vector<int>> as(N, vector<int>(M));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> as[i][j];
        }
    }
 
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int sum = 0;
        for (int j = 0; j < M; j++) {
            sum += as[i][j] * bs[j];
        }
 
        if (sum + C > 0) {
            ans++;
        }
    }
    cout << ans << endl;
}

C

価格の安い順にソートし、貪欲に本数を稼いでいく。

#define int long long  // 競プロ以外で使っちゃいけない
typedef pair<int,int> P;

signed main() {
    int N, M;
    cin >> N >> M;
    vector<P> vs(N);
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        vs[i].first = a, vs[i].second = b;
    }
    sort(vs.begin(), vs.end(), [](P x, P y) {
        return x.first < y.first;
    });
 
    int cost = 0, cur = 0;
    for (int i = 0; i < N; i++) {
        cost += vs[i].first * vs[i].second;
        cur += vs[i].second;
        if (cur > M) {
            int tmp = abs(cur - M);
            cost -= vs[i].first * tmp;
            break;
        }
    }
    cout << cost << endl;
}

D

気づいたことは以下の法則（あってんのかは知らん）

  • f(2^n, 2^(n+1) - 1) = 0
  • f(2^n, 2^(n+1)) = 2^(n+1)
  • f(2^n + 1, 2^(n+1) - 1) = 2^n

これらを再帰かなんかでこねくり回せばいけそうな気がしたが、そこから先がなんもわからん。

所感

なんか30分以内で3完した程度じゃ、たいしてレートが伸びなくなってきてるな。これはいよいよ本格的にD問題を演習していくべき時期なのだろう。
いや、マジで？今のところの本番でのC問題の打率はそこそこだが、過去問では結構解説ACの量の方が多いんですけど。