Atcoder Biginner Contest 189 (ABC189)振り返り - rxiveのブログ‐競プロとか数学とか日記とか

A問題
B問題
C問題
D問題
感想

Atcoder Biginner Contest 189に参加しました。

A問題

　 $C_1, C_2, C_3$ が等しいかどうかを確認する。

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

int main() {
  string S;
  cin >> S;
  if(S[0]==S[1] && S[0]==S[2])cout << "Won" << endl;
  else cout << "Lost" << endl;
}

B問題

B - Alcoholic

　飲んだアルコール量は $V_i \times \frac{P_i}{100}$ で計算できるのでこれが $X$ を始めて超える $i$ を探す。ただし、少数の計算は誤差を含む(コンピュータ内部では2進数で計算を行っているため0.01を正確に表せない)ので整数値同士を比較する。

　解答方針：初めて $V_i \times P_i > 100 \times X$ となる $i$ 、なければ-1を出力する。

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

int main() {
  int N, X;
  cin >> N >> X;
  vector<int>V(N);
  vector<int>P(N);
  for(int i=0; i<N; i++)cin >> V[i] >> P[i];
  
  int ans =-1;
  int Alc=0;
  for(int i=0; i<N; i++){
    Alc += V[i]*P[i];
    if(Alc>X*100){
      ans = i+1;
      break;
    }
  }
  cout << ans << endl;
}

C問題

C - Mandarin Orange

　まず全探索できるか考える。
　 $1\le l \le r \le N$ を満たすように $l$ と $r$ を全探索するには

  for(int l=1; l<=N; l++){
    for(int r=l; r<=N; r++){
      //適切な操作
    }
  }

のように二重ループで書くことができる。この時の計算量は[tex: O(N²)]で高々10⁸の計算量で、かつ簡単な操作なのでc++では十分に間に合うので全探索での実装を行う。
　次に $x$ について考えると、 $l \le i \le r$ を満たすすべての $i$ に対して $x \le A_i$ であるから、 $x=min({A_i}) (ただしl \le i \le r)$ である。この[te: x]に対して区間の長さ $r-l+1$ をかけたものが食べるみかんの個数となり、これの最大値を求める。

　解答方針： $x\times (r-l+1)=min({A_i})\times (r-l+1) (ただしl \le i \le r)$ の最大値を全探索により求める。

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

int main() {
  int N;
  cin >> N;
  vector<int>A(N);
  for(int i=0; i<N; i++)cin >> A[i];
  
  int ans=0;
  for(int l=0; l<N; l++){
    int x=A[l];
    for(int r=l; r<N; r++){
      x=min(x, A[r]);
      ans=max(x*(r-l+1), ans);
    }
  }
  
  cout << ans << endl;
}

D問題

D - Logical Expression

　最後がANDかORかでxがTrueかFalseかが変わりそう。

$S_N="AND"$ のとき $x_N = y_N = "True"$
$S_N="OR"$ のとき $x_N="True"$ ならば $y_N$ はなんでもいい
$x_N = "False"$ ならば $y_N = "True"$

　ここで $y_i="True"$ となる $x_0, ..., x_i$ の選び方の個数を $C(x_0, ... x_i)$ とすると、上の条件を考えて

$S_i="AND"$ のとき $C(x_0, ... x_i) = C(x_0, ..., x_{i-1})$
$S_i="OR"$ のとき $C(x_0, ..., x_i) = 2^ i+ C(x_0, ..., x_{i-1})$
ただし $C(x_0)=1$

となる。これをi=Nから0まで計算すればよい。

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

int main() {
  int N;
  cin >> N;
  vector<string>S(N);
  for(int i=0; i<N; i++)cin >> S[i];
  long long n=pow(2, N);
  
  long long ans=0;
  for(int i=0; i<N; i++){
    if(S[N-i-1]=="OR")ans+=n;
    n/=2;
  }
  ans++;
  
  cout << ans << endl;
  
}

感想

　A言われた通りにやる。B言われた通りにやる。C、計算量10⁸が間に合わないと思った。実際には余裕。D、後ろから見ていくところまでは思いついたが、解けず。EFは何をしていいか分からなかった。
　安定してDまで解けるようになりたい。解く速度を上げないと考察に時間が取れなくて厳しいので問題を解きまくっていこうかと思いました。3週連続ABCがあるので頑張ります。　