ABC165振り返り

ABC165の振り返りをします。

結果はA,B,D,Eの4完で、レートが上がりました^ ^

コンテスト中

A問題

aからbまでの間にkの倍数があるかどうかを調べました。

  for(ll i = a; i <= b; i++){
   if(i % k == 0){
     cout<<"OK"<<endl;
     return 0;
   }
 }
 cout<<"NG"<<endl;

B問題

1.01^100 がeくらいになるはずなので、計算量は十分間に合いそうなのはわかりながら実装しました。
1.01倍は1/100を足すなどの操作の方がよかったようです。

double型の仮数部は52bit、精度は10^(-16)くらいで、誤差が生まれる可能性があることにも注意するべきでした。

  while(m < x){
   ans++;
   m *= a;
   m = floor(m);
 }

C問題

時間がいつもよりかかりましたが問題文を理解して、全探索すれば解けそうなことはわかりました。

しかし、実装が長くなりそうでミスしそうだったので先にD問題にいきました。

D問題

sampleのA,Bに関して色々なxで試してどのようなxで条件をみたすか考えました。

ll N = X/B * B - 1;
 if(N == -1) N = X;
 // cout<<N<<endl;
 // nを利用
 ll tmp1 = floor(A*N/B);
 ll tmp2 = A * floor(N/B);

 ll ans = tmp1 - tmp2;
 cout<<ans<<endl;

E問題

D問題が終わってから、E問題の問題を理解してC問題とどちらを解くか迷いました。
E問題が解けそうだったのでとりあえず配点の高いE問題に取り掛かることにしました。

問題文を読んで感じたのは、本質はそれぞれの数字の差が被らないようにすることだと思いました。

sampleを試しながら、Nが奇数の時は簡単だと気付きました。
それぞれの差が奇数ならば、奇数から奇数を引けば偶数になるからです。

Nが偶数の時は、半分までは奇数を採用し、それ以降は偶数を採用するという方法で処理することができました。

  if(N %2 == 1){
   ll tmp = (N - 1) / 2;
   rep(i,M){
     a[i].first = tmp - i;
     a[i].second = tmp + i + 1;
   }

 }
 else{
   ll tmp = (N + 1) / 2;
   for(ll i = 0; i < (M + 1) / 2; i++){
     a[i].first = tmp - i - 1;
     a[i].second = tmp + i;
   }
   for(ll i = (M + 1) / 2; i < N; i++){
     a[i].first = tmp - i - 1;
     a[i].second = tmp + i + 1;
   }
 }

F問題

E問題が終わった後に順位表をみてC問題を解いても順位がほとんど変わらなそうだったのでF問題をみました。

F問題の内容はLISに関する問題で蟻本でやったことがあったのでできるかもと思いましたが、木の処理にも慣れていなくまだまだ実力不足だと感じました。

コンテスト後

C問題

C - Many Requirements

再帰を利用して簡潔にかけることを解説放送から学びました。
この実装ってC問題にしては難しい気がします。

void dfs(vector<ll> A){
 // cout<<A.size()<<endl;
 if(A.size() == n + 1){
   ll tmp = 0;
   rep(i,q){
     if(A[b[i]] - A[a[i]] == c[i]) tmp += d[i];
   }
   ans = max(ans , tmp);
   return ;
 }

 A.pb(A.back());
 while(A.back() <= m){
   dfs(A);
   A.back()++;
 }

}

二日連続でABCがあるので本日も頑張ります(^^)