Atcoder 復習 備忘録2

ABC300 B問題

文字列をシフトさせる問題。modを使うと楽に実装できる。

B.cpp

if (A[(i - s + H) % H][(j - t + W) % W] != B[i][j]) ok = 0;

ABC300 D問題

N以下の素数を列挙する必要あり。エラトステネスの篩を使う。
https://github.com/atcoder/live_library/blob/master/prime.cpp
（今回はbool isPrime以下は不要）

D.cpp

Sieve p(1e6);
for(int pr: p.primes){
    cout << pr << endl;
}

で素数が列挙できる。エラトステネスの篩はO(NloglogN)？（参考:https://qiita.com/drken/items/3beb679e54266f20ab63）

ABC301 B問題

for文の中で配列のサイズが変わるとき、a.size()をうまく使う。
a.insert(iter, value)を使う。

B.cpp

for(int i=1;i<a.size();i++){
	if(a[i-1]+1<a[i])a.insert(a.begin()+i,a[i-1]+1);
	if(a[i-1]-1>a[i])a.insert(a.begin()+i,a[i-1]-1);
}

ABC305 D問題

D.cpp

     auto f=[&](int x){
         int i=lower_bound(a.begin(),a.end(),x)-a.begin();
         if(i<0) return 0;
         int res=s[i];
         if(i%2==1) res+=x-a[i];
         return res;
     };

lower_boundは、key以上の要素の内の一番左側のイテレータを返す。lower_boundはイテレータを返すが、-begin()してintにいれればint型になる。

ABC308 C問題

double型を使うと誤差でWAになる。分母と分子をそれぞれpairに入れる

C.cpp

    vector<pair<int, int>> ab;
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        ab.emplace_back(a, a + b);
    }

sortは安定ソートではない。stable_sortを使う。

C.cpp

    auto f = [&](int i, int j) {
        auto [ai, aj] = ab[i];
        auto [bi, bj] = ab[j];
        return (long long)ai * bj > (long long)aj * bi;
    };
stable_sort(p.begin(), p.end(), f);

ちなみに、二次元vectorを特定キーでソートする場合。
https://qiita.com/Arusu_Dev/items/c36cdbc41fc77531205c

ABC308 D問題

D.cpp

auto dfs = [&](auto &dfs, int i, int j) -> void {
        seen[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int ni = i + dx[k];
            int nj = j + dy[k];
            if (ni < 0 or ni >= h or nj < 0 or nj >= w) continue;
            if (s[ni][nj] != next[s[i][j]]) continue;
            if (seen[ni][nj]) continue;
            dfs(dfs, ni, nj);
        }
    };

main内での再帰関数の書き方注意。関数自体を引数に参照渡し。->voidがないと戻り値が不明瞭というエラーがでることも。
dfs(dfs,ni,nj)の前後にseen[ni][nj]=trueとseen[ni][nj]=falseを入れてたためTLEになってしまった。以後気を付ける。

ABC309 C問題

2次元配列を第一キーでソートする方法

C.cpp

//pairを使う方法
vector<pair<int,int>> p(N);	
for(int i=0;i<N;i++){
	cin>>p[i].first>>p[i].second;
}
sort(p.begin(),p.end());

//vectorを使う方法（こっちの方が一般的？）
vector<vector<int>> ab(N,vector<int>(2));
rep(i,N){
    cin >> ab[i][0]>> ab[i][1];
}
sort(ab.begin(), ab.end(),[](vector<int> &alpha, vector<int> &beta){return alpha[0]< beta[0];});

ABC 309 D問題

queue<pair<int,int> >の使い方

D.cpp

queue<pair<int,int> > q; //>と>の間は必要なので注意
q.push(make_pair(1,0)); //値の代入

//値の取り出し方
int num,cnt;
tie(num,cnt)=q.front();
q.pop();

今回の問題はこれをやらなくても解ける。
cntで管理している値を配列で管理する。
すなわち、bfsでqueueからint xを取り出したとすると、xの次に取り出す値yにおける距離を配列vector<int> distを用いて'dist[y]=dist[x]+1'をすればよい。