ABC 121

A

A - White Cells

  • H * W - h * W - H * w + h * wが答え
#include <bits/stdc++.h>
 
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef long long int ll;
 
using namespace std;
 
int main() {
  int H, W, h, w;
  cin >> H >> W >> h >> w;
  cout << H * W - h * W - H * w + h * w << endl;
}

Submission #5133607 - AtCoder Beginner Contest 121

B

B - Can you solve this?

  • 問題文に書いてある条件を満たすかどうかを数える
#include <bits/stdc++.h>
 
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef long long int ll;
 
using namespace std;
 
int main() {
  int N, M, C;
  int B[21];
  int A[21][21];
 
  cin >> N >> M >> C;
  REP(i, M) cin >> B[i];
  REP(i, N) REP(j, M) cin >> A[i][j];
 
  int cnt = 0;
  REP(i, N) {
    int sum = C;
    REP(j, M) sum += A[i][j] * B[j];
    if (sum > 0) cnt++;
  }
  cout << cnt << endl;
}

Submission #5133653 - AtCoder Beginner Contest 121

C

C - Energy Drink Collector

  • 価格が安いものから貪欲
#include <bits/stdc++.h>
 
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef long long int ll;
 
using namespace std;
 
int main() {
  int N, M;
  vector<pair<ll, ll>> price;
  ll A, B;
 
  cin >> N >> M;
  REP(i, N) {
    cin >> A >> B;
    price.push_back(make_pair(A, B));
  }
 
  sort(price.begin(), price.end());
 
  ll ans = 0;
  REP(i, N) {
    if (M <= price[i].second) {
      ans += price[i].first * M;
      break;
    } else {
      ans += price[i].first * price[i].second;
      M -= price[i].second;
    }
  }
  cout << ans << endl;
}

D

  • 解けなかった
  • nが偶数のときn^(n-1)が1であることを利用すると4で割った余りに応じてf(0, n)は以下のようになる。
    • 0 → n
    • 1 →1
    • 2 → n^1
    • 3 → 0
  • f(A, B) = f(0, A-1) ^ f(0, B)を利用するとO(1)で解ける
    • AからBまでのiビットの総和は(0からBまでのiビットの総和) - (0からA-1までのiビットの総和)であり、その偶奇は両者のXORを取れば求まる。
#include <bits/stdc++.h>
 
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef long long int ll;
 
using namespace std;
 
ll f(ll n) {
  int r = n % 4;
  if (r == 0) return n;
  else if (r == 1) return 1;
  else if (r == 2) return n ^ 1;
  else return 0;
}
 
int main() {
  ll A, B;
  cin >> A >> B;
  cout << (f(A - 1) ^ f(B)) << endl;
}

Submission #5134237 - AtCoder Beginner Contest 121