ABC130に参加して冷えた話

はじめに

更新をサボり気味なので、これから毎週コンテスト後の感想を綴っていこうと思います。

2完しか出来ずに氷河期を迎えた（茶パフォ）、前回稼いだレートは消えました。

Contest Result - AtCoder

A問題

お決まりのif文知ってますか問題、変数の名前は問題のと異なってます

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

  int n,x;
  string s;
  cin >> n >> x;

  if(n < x) cout << 0 << endl;
  else cout << 10 << endl;  
  
  return 0;
}

B問題

累積和作れば良かったのだと思うのですけど、n番目を考慮漏れして1WAしてしまった

深く考えずにvectorへ突っ込んだ後、上記に気づいてAC

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

  int n,x;
  string s;
  cin >> n >> x;
  vector<ll> L(n+1);
  vector<ll> D(n+1);
  REP(i, n) cin >> L[i];
  ll cnt = 1;
  D[0] = 0;
  vector<ll> vec;
  FOR(i,1,n+1) {
    D[i] = D[i-1] + L[i-1];
    vec.push_back(D[i]);
  }
  sort(vec.begin(), vec.end());

  for(auto &e: vec){
    if(e <= x){
      cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}

C問題

何故か問題を読んだ時から格子状での解法を考えていた。。。

よくよく考えると線の傾きに制限はないので、四角形の中心を通る切り方が最適であると分かる

よって、座標(x, y)が中心に与えられた場合は切り方として無限パターン存在する

その他の場合は1パターンしかない

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

  ll w, h, x, y;
  cin >> w >> h >> x >> y;
  
  cout << fixed << setprecision(20);
  cout << double(w) * double(h) /2 << " " << (x+x == w && y+y == h) << endl;
  //所与の点が中心である ... (w/2, h/2) = (x, y)
  
  return 0;
}

D問題

解法は合っていたが、TLEして終了した

原因は個数を数える際にleft = 0を代入して、逐一計算していたこと

あと途中まで単調増加か否かを無視してしゃくとり法走ってたのも良くなかった...

sumがkの値を以上ならば以降の(n-r+1)の要素についても sum >= kが成立するため、これをansに足し合わせる方針で解けば良い

↑自分の考えと逆の足し方だったので、ちゃんと覚える

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

  ll n,k;
  cin >> n >> k;
  vector<ll> a(n);
  REP(i,n) cin >> a[i];

  ll ans = 0LL, sum = 0LL;

  int r = 0;
  REP(l, n){
    while(sum < k){
      if(r == n) break;
      else{
    sum += a[r];
    r++;
      }      
    }
    if(sum < k) break;
    ans += n-r+1;
    sum -= a[l];
  }

  cout << ans << endl;
  
  return 0;
}

E以降

解いてないので、また今度やります

所感

くっそ冷えて萎えましたが、最近精進できてなかったので致し方ないです

なので今週は、しゃくとり法をそらで高速に書けるよう精進します！

覚えること: 「〜以降は条件を満たす」場合は、後ろから差分を引いてansに加える