ABC174 参加記録

ググり力、灯台下暗しと言ったところでした。

レートは冷えたけど、学びもありました。Eまでは悪くないペースだったと思うけど...

A問題

こう言う問題で秒単位で時間を削るなら3項目演算子使うべきなんだろうけど素直にif文を書いてしまった。いや別にいいんだけど...

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

using ll = long long;
#define REP(i,n) for(int i = 0;i < n;i++)

int main(void){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int x;cin >> x;
  if(x >= 30)cout << "Yes" << '\n';
  else cout << "No" << '\n';

}

B問題

最初入力が実数だと勘違いして(誤読1)誤差大丈夫かなEPS用意しないといけないやつかと思った

流石にB問題だし誤差大丈夫だろと思ってたらそもそも整数だった

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

using ll = long long;
#define REP(i,n) for(int i = 0;i < n;i++)

int main(void){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int ans = 0;

  int n;cin >> n;
  ll d;cin >> d;
  REP(i,n){
    ll x,y;cin >> x >> y;
    if(x*x+y*y <= d*d)ans++;
  }

  cout << ans << '\n';
}

C問題

Mで割ったあまりの周期は高々Mとかになるやつ。最初M%2==0で-1とかやってたら案の定TLEした。うるうる

int main(void){
  cin.tie(0);
  ios::sync_with_stdio(false);
 
  ll k;cin >> k;
 
  if(k % 2 == 0){
    cout << -1 << '\n';
    return 0;
  }
 
  ll ten = 1;
  ll tmp = 0;
  int cnt = 1;
  for(int i = 0;i < 1e7;i++){
    ll add = (7 * ten) % k; 
    tmp = (tmp + add) % k;
    ten = (ten * 10) % k;
    if(tmp == 0){
        cout << cnt << '\n';
        return 0;
    }
    cnt++;
  }
  cout << -1 << '\n';
 
}

D問題

隣接swapだと勘違いして(誤読2)時間を溶かしていた。 Rを全部左に詰めるから、最初の入力で(Rの個数をMとする)、[0,M)の範囲にあるRは動かさなくていいことに注意するとO(N)で計算できる

int main(void){
  cin.tie(0);
  ios::sync_with_stdio(false);
 
  ll n;cin >> n;
  string s;cin >> s;
 
  ll ans = 0;
 
  ll cnt = 0;
  REP(i,n)cnt += (s[i] == 'R');
 
  REP(i,n){
    ans += (i >= cnt && s[i] == 'R');
  }
 
  cout << ans << '\n';
}

E問題

一目見て二分探索だと気づいたので書いて通す。これはすぐできた

ll n,k;
ll a[maxn];
void read(){
    cin >> n >> k;
    REP(i,n)cin >> a[i];
}
 
bool func(int x){
    ll cnt = 0;
    REP(i,n){
        cnt += ((a[i] + x - 1) / x) - 1;
    }
    return cnt <= k;
}
 
int main(void){
  cin.tie(0);
  ios::sync_with_stdio(false);
  read();
  int l = 0,r = 1e9 + 1;
 
  while(l + 1 != r){
    int mid = (l + r)/2;
    // can all len <= mid ?
    if(func(mid))r = mid;
    else l = mid;
  }
 
  cout << r << '\n';
 
}

F問題

fastestが2分を切っているのを見て、データ構造かライブラリか超有名知識なんだろうと察しをつけ、色々とググろうとしたけどダメだった。と言うか、格好つけて英単語を並べて英語の記事を探そうとしてた。普通に日本語の記事に本質があった...(TODO:通したらリンクを貼る)

まとめ

青になって初めてのrated。レートはとかしてしまったけど、データ構造系の有名知識も身につけていかないといけないなと感じ、教訓になった。また頑張ります。 夏休みが近いので、夏休みになったらCFのばちゃとかをたくさんやりたい。1ヶ月しかないと言うか将来のこともやんなきゃいけないけど。