Atcoder 復習　備忘録2

# ABC300 B問題


https://atcoder.jp/contests/abc300/tasks/abc300_b

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

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

# ABC300 D問題

https://atcoder.jp/contests/abc300/tasks/abc300_d

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

```cpp:D.cpp
Sieve p(1e6);
for(int pr: p.primes){
    cout << pr << endl;
}
```
で素数が列挙できる。エラトステネスの篩はO(NloglogN)？（参考:https://qiita.com/drken/items/3beb679e54266f20ab63）


# ABC301 B問題

https://atcoder.jp/contests/abc301/tasks/abc301_b

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

```cpp: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問題
https://atcoder.jp/contests/abc305/tasks/abc305_d

```cpp: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問題
https://atcoder.jp/contests/abc308/tasks/abc308_c

`double`型を使うと誤差でWAになる。分母と分子をそれぞれ`pair`に入れる
```cpp: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`を使う。

```cpp: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問題
https://atcoder.jp/contests/abc308/tasks/abc308_d

```cpp: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問題
https://atcoder.jp/contests/abc309/tasks/abc309_c

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

```cpp: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問題
https://atcoder.jp/contests/abc309/tasks/abc309_d

`queue<pair<int,int> >`の使い方
```cpp: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'をすればよい。