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

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

Atcoder Biginner Contest 188 (ABC188)振り返り

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

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

atcoder.jp

A問題

atcoder.jp

　XとYのうち小さい数に3を足すと大きい数より大きくなるかどうか つまり、min(X, Y)+3>max(X, Y)となるかどうかを判別する。

　XとYの差が3未満と言い換えることができるのでabs(X-Y)<3としてもよい

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

int main() {
  int X, Y;
  cin >> X >> Y;

  if(min(X, Y)+3>max(X, Y))cout << "Yes" << endl;
  else cout << "No" << endl;
}

B問題

B - Orthogonality

問題文中にある通りに計算する。計算量O(N)で明らかに間に合う。

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

int main() {
  int N;
  cin >> N;
  vector<int>A(N);
  vector<int>B(N);
  for(int i=0; i<N; i++)cin >>A[i];
  for(int i=0; i<N; i++)cin >> B[i];
  
  int ans=0;
  for(int i=0; i<N; i++){
    ans+=A[i]*B[i];
  }
  
  if(ans==0)cout << "Yes" << endl;
  else cout << "No" << endl;
}

C問題

C - ABC Tournament

　決勝戦ではトーナメントの前半で最もレートが高い選手と後半で最もレートが高い選手が戦う。この二人のうちレートが低いほうが準優勝者である。よってそれぞれのレートと番号を求めればよい。

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

int main() {
  int N;
  cin >> N;
  int n=pow(2, N); //n=2^Nとする
  vector<int>A(n);
  for(int i=0; i<n; i++)cin >> A[i];
  int A1=0;  //トーナメント前半最高レート
  int A2=0;  //トーナメント後半最高レート
  int i1=0;  //前半最高レートの人の番号
  int i2=0;  //後半最高レートの人の番号
  
  for(int i=0; i<n/2; i++){
  //前半[0, n/2)での最高レートと番号をもとめる
    if(A1<A[i]){
      A1=A[i];
      i1=i;
    }
  }
  
  for(int i=n/2; i<n; i++){
  //後半[n/2, n)での最高レートと番号をもとめる
    if(A2<A[i]){
      A2=A[i];
      i2=i;
    }
  }

  //準優勝者の番号を出力して終了
  if(A1<A2)cout << i1+1 << endl;
  else cout << i2+1 << endl;
}

D問題

D - Snuke Prime
　ある日の使用サービスの合計料金と定額料金のうち安いほうを支払う。imos法(累積和)を用いて料金を計算すればよい。ただし日数が最大で109であり一日ずつ計算すると間に合わないため、変化のない部分はまとめて計算する(座標圧縮というらしい)。

　例を参考に考えてみよう。

N=2 C=6
a[0]=1 b[0]=2 c[0]=4  //サービス0を1日目から2日目までの2日間利用
a[1]=2 b[1]=2 c[1]=4  //サービス1を2日目から2日目までの1日間利用

answer=10

　b[i]-a[i]では利用日数にならないので正しい日数が得られるようにa[i]から1引いて考える。(b[i]に1足すでもよい)
　利用料金はa[i]-1日目の終わりに+c[i]増えて、b[i]日目の終わりにに-c[i]増えるとすればaとbを区別せずにまとめることができる。 (imos法) 　実際にまとめた後にソートしてみると次のようになる。

N=2 C=6
a[0]-1= 0  c[0]= 4  //0日目終了時点の料金は0+4=4
a[1]-1= 1  c[1]= 4  //1日目終了時点の料金は4+4=8
  b[0]= 2 -c[0]= -4 //2日目終了時点の料金は8-4=4
  b[1]= 2 -c[1]= -4 //2日目終了時点の料金は8-4=0

　ここで定額料は6であることに注意すれば、
0~1日目料金4×1=4
1~2日目料金6×1=6
2日目以降0
　であるため和をとって答えは10になる。

　以上をまとめると次のようになる。
　1. a[i]をa[i]-1とする
　2. すべてのb[i]について-c[i]として(a[i]-1, c[i])と(b[i], c[i])をまとめてソートする。
　3. 料金変動があった日ごとに min(個別料金の和, 定額料金)×次の変動日までの日数 を計算して和をとる

では実際にやってみる。

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

int main() {
  int N, C;
  cin >> N >> C;
  vector<long long>a(N);
  vector<long long>b(N);
  vector<long long>c(N);
  
  for(int i=0; i<N; i++)cin >> a[i] >> b[i] >> c[i];
  vector<pair<long long, long long>>ABC(N*2);
  //a[i]とb[i]をまとめて一つにする。ソートしやすいようにpairを用いている
  
  for(int i=0; i<N; i++){
    ABC[i]=make_pair(a[i]-1, c[i]);  //a[i]-1日目の終わりにc[i]増加
    ABC[N+i]=make_pair(b[i], -c[i]);  //b[i]日目の終わりに-c[i]増加
  }
  
  sort(ABC.begin(), ABC.end());  //変化があった日付順になった
  
  long long Q=0;  //ある日利用したサービスの個別料金の和
  long long ans=0;  //答え、つまり支払う金額の和
  
  for(int i=0; i<N*2; i++){
    Q+=ABC.at(i).second;  //変動後の個別料金の和
    if(i<N*2-1){
      ans+=min(Q, C)*(ABC.at(i+1).first-ABC.at(i).first);
  //min(個別料金の和, 定額料金)×次の料金変動日までの日数
    }
  }
  
  
  cout << ans << endl;
}

感想

A~Cまでは簡単な印象。Dは日数が多いのでいかに計算量を減らすかを考えた。問題をみてすぐにimos法を考えたが座標圧縮と日数の調整に手間取った。EはDFSっぽいと思ったが、うまく計算量を落とすところまで頭が回らず解説を見てなんとなく理解。Fはわからない。