rxiveのブログ‐競プロとか数学とか日記とか

競技プログラミングとか数学とか日記

Atcoder Biginner Contest 187 (ABC187)振り返り

Atcoder Atcoder Biginner Contest 競技プログラミング

お久しぶりです。2021年あけましておめでとうございます。
私用で忙しかったためしばらく更新が遅れていました。無理のない程度に再開していきたいと思います。

 Atcoder Biginner Contest 187に参加しました。 atcoder.jp

A問題

A - Large Digits
　10進法での各桁の和を求めます。
　Aを10で割った余り(A%10)を求めた後、Aを10で割って(A/10)一の位を除きます。
これを繰り返せして和をとれば(A)が分かり、Bについても同様にしてS(B)を求めて大きいほうを出力します。

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

int main() {
  int A, B;
  cin >> A >> B;
  int S_A=0;  int S_B=0;
//はじめS(A)=0, S(B)=0としておきます

  for(int i=0; i<3; i++){
    S_A+=A%10;  S_B+=B%10;
    A/=10;  B/=10;
/*A, Bの一の位をS(A), S(B)に足して, A,Bは10で割ります。
  桁数以上だけ繰り返します。*/
  }
  cout  << max(S_A, S_B)  << endl;
}

　一般に整数AをN進数で表したいときはNで割った余り(A%N)をメモしておきAを商に置き換えること(A/=N)を繰り返せば、下から順に各桁の数を求めることができます。計算量は O( log_N(A))程度でしょう。

B問題

B - Gentle Pairs
　素直に実装するとO(N2)で、Nは最大でも3000程度なので十分間に合います。
　さて、傾きの求め方は(yの増加量)/(xの増加量)ですので -1 \le \frac{Y_j - Y_i}{X_j - X_i} \le 1を満たす(i, j)の個数をカウントすればよいことになります。
　ところで、分数に変数が含まれて分母が0になる可能性がある場合には分母を払っておくと実装が容易になることが多いですが、不等号を含むこの問題で分母を払うためには X_j - X_iの符号で場合分けする必要があります(負の数をかけると大小関係が逆転するため)。幸いにも範囲が-1~1なので絶対値をとることで容易に解決します。つまり、 |\frac{Y_j - Y_i}{X_j - X_i}| \le 1とまとめることができるので絶対値をつけたまま分母を払って以下のようになります。

|Y_j - Y_i| \le |X_j - X_i|

一次関数のグラフの傾きが-1以上1以下になるには「X方向の変化の大きさよりもY方向の変化の大きさが小さければよい」という直感的に理解しやすい式になりました。

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

int main() {
  int N;
  cin >> N;
  vector<int>X(N);
  vector<int>Y(N);
  for(int i=0; i<N; i++)cin >> X[i] >> Y[i];
  
  int ans=0;
  for(int i=0; i<N; i++){
    for(int j=i+1; j<N; j++){
//i<jなのでj=i+1からスタート
      if(abs(Y[j]-Y[i])<=abs(X[j]-X[i]))ans++;
 //条件にあてはまる個数をカウント
    }
  }
  
  cout << ans << endl;
}

C問題

C - 1-SAT
文字列 S_iと'i'+ S_iが両方存在すれば、それが不満な文字列である。最大でN=2*105なのでお互いの文字列の組み合わせをすべて調べるとO(N2)となり間に合わない。
　set を使うと効率よく調べることができる(らしい)。setって何でしょうか。要検索です。ところでsetを知らない私はソートして順に調べました。
　方針としては!から始まる文字列配列S[i]と英小文字から始まる文字列配列S[j]をそれぞれソートした状態で用意しておき、S[i]>S[j]ならばj++;S[i]<S[j]ならばi++;とすればN回の要素の比較で済むため計算量はソートのO(NlogN)で間に合うはずだというもの。実装で2回ミスをした程度には煩雑なコードになってしまった。

#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];
  sort(S.begin(), S.end());
  int count =0;
  for(int i=0; i<N; i++){
    if(S[i][0]=='!'){
      count ++;
      S[i]=S[i].substr(1);
    }
  }
  /*'!'スタートのものの個数を数えて
  比較しやすいように!は取り除いておく*/
  
  string ans="satisfiable";
  int j=count;
  for(int i=0; i<count; i++){
    if(j>=N)break;
    while(S[i]>S[j]){
      //S[i]>S[j]ならばj++;して次のものと比較
      j++;
      if(j>=N)break;
    }
    if(S[i]==S[j]){
      //一致したらそれが不満な文字列
      ans=S[i];
      break;
    }
  }
  cout << ans << endl;
}

D問題

D - Choose Me

高橋氏が演説した場合としなかった場合を比較してみる。
演説しなかった場合→演説した場合
青木氏　 A_i→ 0　(変化 -A_i)
高橋氏　 0→ A_i + B_i　(変化 A_i + B_i)
　高橋氏は演説をすることで青木氏との差を 2A_i + B_iだけ縮めることができる。よって 2A_i + B_iが大きい順に町で演説を行えばよいことが分かる。

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

int main() {
  int N;
  cin >> N;
  vector<long long>A(N);
  vector<long long>B(N);
  vector<long long>C(N);
  long long sa =0;
  for(int i=0; i<N; i++){
    cin >> A[i] >> B[i];
    C[i]=A[i]*2+B[i];
    sa-=A[i];
//C[i]=2A[i]+B[i]とする。またあらかじめ青木氏の得票数の和をを引いておく
  }
  
  sort(C.begin(), C.end());
  reverse(C.begin(), C.end());
  //C[i]を大きい順に並べ替える
  for(int i=0; i<N; i++){
    sa+=C[i];
    if(sa>0){
      cout << i+1 << endl;
      break;
    }
  } 
//高橋氏の得票が上回ったら終了
}

感想

EF問題が分からない。グラフアルゴリズムの勉強しないといけないなーとか思ってはいるけれど、探索系をやりたい。
C問題でつまづいたのがとても痛手。個人的にはDのほうがずいぶん簡単だったがこれは知識不足。レート変化はほぼなかったから、2021年は可もなく不可もない(どちらかといえば不可な)滑り出しでした。