ABC121

atcoder.jp

所要時間

• 測るの忘れた．AB2完に10分未満，CはWA 2ケースが解消できずに自力ACならず，DはTLEでgive up

解答メモ

A

• シミュレーション

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

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

  int H, W, h, w;
  cin >> H >> W >> h >> w;

  cout << H * W - (h * W + w * H - h * w) << endl;

  return 0;
}

B

• シミュレーション
  • 時間計算量はだけどMもNも小さいので問題ない

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int B[20];

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

  int N, M, C;
  cin >> N >> M >> C;
  REP(i, M) { cin >> B[i]; }

  int ans = 0;
  int sum = 0;

  int tmp_a = 0;

  REP(i, N) {
    sum = 0;
    REP(j, M) {
      cin >> tmp_a;
      sum += B[j] * tmp_a;
    }
    if (sum + C > 0) {
      ++ans;
    }
  }

  cout << ans << endl;

  return 0;
}

C

• 自力出といたら3問WA踏んで解決できずに終了
• 原因はAが重複するケースを想定しておらず（マジで馬鹿），AとBの組み合わせをmapで持たせたので重複があると解が正解より大きくなる実装になっていた
• cppでは重複を許可するmapみたいなデータ構造を表現するクラスはstdには用意されていないので，vector<pair>を使うのが定番のようだ
• あとcin >> p[i].first >> p[i].second;でペアにまとめて標準入力を代入できるの知らんかったので覚えておきたい

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

ll A[100000];

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

  ll N, M;
  cin >> N >> M;
  vector<pair<ll, ll>> cost(N);
  REP(i, N){
    cin >> cost[i].first >> cost[i].second;
  }
  sort(cost.begin(), cost.end());
  ll ans = 0;
  ll current_m = 0;
  REP(i, N){
    current_m += cost[i].second;
    ans += cost[i].second * cost[i].first;
    if(current_m >= M){
      ans -= cost[i].first * (current_m - M);
      break;
    }
  }

  cout << ans << endl;

  return 0;
}

D

• 当たり前だけどそのままA..Bのxorを取ったらTLEした
• 解法を見るととの性質を使って解く必要があった．
• 各ビットの1の個数を数える手も考えられたが，それでも10¹²のループが時間計算量的に厳しそうだったので断念した
• 数列の部分和を求める時もそうだが，特定の連続した範囲における解を求める場合は差分を使う方法が効率的に解ける事が多いように感じた

参考リンク:

drken1215.hatenablog.com

#include <bits/stdc++.h>
using namespace std;

long long x(long long a) {
    if (a % 4 == 0) return a;
    if (a % 4 == 1) return 1;
    if (a % 4 == 2) return a + 1;
    return 0;
}
int main() {
    long long a, b;
    cin >> a >> b;
    cout << (x(b) ^ x(a - 1)) << endl;
}