Asa's Blog

ABC205

Tags: AtCoder  ABC  Competitive-Programming 

Published on 2021.06.13. Last Modified on 2021.06.22.

今週もやっていきましょう振り返りを。(謎の倒置)

今回解けたのは A から D。かなり時間がかかってしまった…。

問題概要

A

100mL あたり A kcal のドリンクが B mL のとき、何 kcal?

B

1 以上 N 以下の整数からなる長さ N の数列が与えられる。この数列が $ (1,2,…,N) $ の並び替えで得られる?

C

「A の C 乗」と「B の C 乗」の大小比較

D

正整数列 $ A = (A_1, A_2, …, A_N) $ (ソート済) と Q個のクエリ。
$ i $ 番目のクエリでは、$ K_i $ が与えられる。 $ A $ に属さない正整数のうち、小さいほうから数えて $ K_i $ 番目のものを求める。

提出結果

ここから 提出結果がわかります。

A

提出 #23396970 - AtCoder Beginner Contest 205

#include <bits/stdc++.h>
using namespace std;
int main(){ cout << fixed << setprecision(15);
  double a,b;
  cin >> a >> b;
  cout << (b*a/100) << endl;
  return 0;
}

普通に、計算するだけ。だけど、 double 型じゃないとアウト。
提出時刻は 21:00:56。1 分以内に提出できた…!

B

提出 #23403526 - AtCoder Beginner Contest 205

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> v(n,0);
  loop(i,n){
    int a;
    cin >> a;
    v[--a]++;
    if(v[a] > 1){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}

長さ N なので、重複して数字が出なければ OK。なので、長さ N の数列 A を用意して、与数列に数 x が出てきたら、A[x-1]を+1 する。で A[x-1]が 2 以上ならNoを出力して終了、という流れ。
今思えば、+1 する前にチェックしてもよかったかも。

提出時刻は 21:03:29。まあ、いつも通りという感じ…?

C

提出 #23426950 - AtCoder Beginner Contest 205

#include <bits/stdc++.h>
using namespace std;
int main(){
  ll a,b,c;
  cin >> a >> b >> c;
  if(a==b){ cout << "="; }
  else if(a==-b && c%2==0){ cout << "="; }
  else if(c%2==0 && abs(a)>abs(b)){ cout << ">"; }
  else if(c%2==0 && abs(b)>abs(a)){ cout << "<"; }
  else if(c%2==1 && a*b<0 && a<0){ cout << "<"; }
  else if(c%2==1 && a*b<0 && b<0){ cout << ">"; }
  else if(c%2==1 && a*b==0 && b>0){ cout << "<"; }
  else if(c%2==1 && a*b==0 && b<0){ cout << ">"; }
  else if(c%2==1 && a*b==0 && a>0){ cout << ">"; }
  else if(c%2==1 && a*b==0 && a<0){ cout << "<"; }
  else if(c%2==1 && a*b>0 && a<b){ cout << "<"; }
  else if(c%2==1 && a*b>0 && a>b){ cout << ">"; }
  cout << endl;
  return 0;
}

完全にテンパって WA を 3 回やってしまいました。場合分けを丁寧にしていれば…後悔。
chokudai さんの 解説(?) Spaces で、C = (C%2) ? 2 : 1 (つまり C が偶数なら 2、奇数なら 1 に置き換え) にしてそのまま $ A^C $ と $ B^C $ を比較すればいい、と仰っていたらしく、なるほどと思った。もっと早く気づいていれば…。
しかも ABC 解説放送で「C が奇数なら A と B の大小関係そのまま」と仰っていて、「そうだよなぁ…こんな汚いコードにならないよなぁ…」とか考えながら聞いていました。

提出時刻は 21:28:39。それに 3 ペナなので、実質 21:43:39。つらい…。

D

提出 #23447498 - AtCoder Beginner Contest 205

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ull1d = vector<ull>;
int main(){
  ll n,q;
  cin >> n >> q;
  ull1d A(n+1,0);
  loop(i,n){ cin >> A[i+1]; }
  loop(i,q){
    ll k; cin >> k;
    if(A[1]-1 >= k){ cout << k << endl; continue; }
    if(A[n]-n < k){ cout << k+n << endl; continue; }
    ll ok=n, ng=-1;
    while(abs(ok - ng) > 1){
      ll mid = (ok + ng)/2;
      if(A[mid]-mid >= k){ ok = mid; }
      else{ ng = mid; }
    }
    ok--;
    cout << k+ok << endl;
  }
  return 0;
}

えっと、制約から $ N,Q \le 10^5 $ だったので、計算量的に log が出てくる二分探索かなーとすぐに気づけました。それと、$ A_x - x $ の値が、「 $ A $ に属さない正整数かつ $ A_x $ 以下(or 未満)の個数」と同じだとすぐに気づけ、かなり考察力が上がったなと実感できました。

いろいろローカルで試行錯誤してみました。メモをとって、きちんと計算をしていればすぐにミスに気づけたと思いますが…。

方針としては、
[1] $ A_1 \gt K_i $ の場合を考えると、1 から $ A_i - 1 $ までの数字は $ A $ に属していないので、そのまま $ K_i $ を出力。
[2] $ A_N \lt K_i $ の場合、$ A_N + 1 $ 以上の数はすべて属さないので、求める数は $ K_i - (A_N - N) = K_i + N $ を出力。$ (A_N - N) $ は、「$ A_N $ 以下で $ A $ に属さない整数の個数」なので。
[3] それ以外の場合、二分探索で $ A_x - x \ge K_i $ となる $ x $ を求めて、x を-1 します。そのあとに、先ほどと同じ理由で、 $ K_i - (A_x - x) = K_i + x $ を出力。

提出時刻は 22:24:45。1 ペナにより実質 22:29:45 です。

結果と感想

ABC197 以来の 4 完です。3177 位で、レーティングは+22 の 652 です。

C と D 問題のペナルティと、D 問題のメモ無しが響いてきたと思います…。
4 ペナがなければ、 20 分マイナスで 84:45 となったため、順位は 2870 位となり、680 くらいまで届いたのかなぁと。ミス修正の時間も引けばさらに上がったかも…。

何とかレーティングは下がりませんでした。これからも維持できるよう頑張りたいです。

そんなことよりABC197以来の4完はかなりうれしい...!

keyboard_arrow_up