AtCoder Beginner Contest 367

## [A - Shout Everyday](https://atcoder.jp/contests/abc367/tasks/abc367_a)

O(24)
シミュレートしましょう。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int a, b, c;
    cin >> a >> b >> c;

    while(b != c){
        if(b == a){
            cout << "No" << endl;
            return 0;
        }
        b++;
        b = b % 24;
    }
    cout << "Yes" << endl;

    return 0;
} 
```

## [B - Cut .0](https://atcoder.jp/contests/abc367/tasks/abc367_b)

O(1)
C++の場合、少数部分の0は自動で表示されなくなります。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    double x;
    cin >> x;
    cout << x << endl;
    return 0;
} 
```

## [C - Enumerate Sequences](https://atcoder.jp/contests/abc367/tasks/abc367_c)

O(N)
dfsの全探索の実装問題です。
各桁毎に、for文で1から探索しましょう。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int N, K;
vector<vector<int>> ans;

void dfs(vector<int>& R, int n, vector<int>& v){
    if(n <= 0){
        int sum = 0;
        rep(i, N) sum += v[i];
        if(sum % K == 0){
            vector<int> to(N);
            copy(v.begin(), v.end(), to.begin());
            ans.push_back(to);
        }
        return;
    }

    for(int i=1; i<=R[N-n]; i++){
        v.push_back(i);
        dfs(R, n-1, v);
        v.pop_back();
    }
}

int main() {
    cin >> N >> K;
    vector<int> R(N);
    rep(i, N) cin >> R[i];

    vector<int> v;
    dfs(R, N, v);

    for(auto a:ans){
        int n = a.size();
        for(int i=0; i<n; i++){
            cout << a[i];
            if(i<n-1) cout << ' ';
            else cout << endl;
        }
    }

    return 0;
} 
```

## [D - Pedometer](https://atcoder.jp/contests/abc367/tasks/abc367_d)

O(N)
累積和、片方を固定しての計算量の削減、循環の複合問題です。

```
N M
A_1 A_2 ... A_N
```

の入力があります。
サンプルの入力１を基準に考察しましょう。

```
4 3
2 1 4 3
```

![D - Pedometer.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/626801/afbb5b6a-5c52-65dd-d975-5fbae929dd9d.jpeg)

Mの倍数の歩数が掛かるr, lの組み合わせを求めましょう。

① 1 ~ 3の歩数
② 4 ~ 1の歩数
③ 4 ~ 3の歩数
④ 3 ~ 2の歩数

歩数の合計 mod M を累積和として取りましょう。
休憩所sをl、から休憩所tをrとして、s[r] - S[l] にて歩数がMの倍数か探索できるようにします。

```
for(int i=0; i<N; i++) S[i+1] = (S[i] + A[i]) % M;
```

表にします。

| i          | 0           | 1           | 2           | 3           | 4
|:-----------|------------:|------------:|------------:|------------:|------------:|
| A[i]       | 2           | 1           | 4           | 3           | -           |
| S[i]       | 0           | 2           | 0           | 1           | 1           |


(l < r)の時、休憩所sから休憩所tまでの歩数は、

```
S[r] - S[l] = 0 ならばMの倍数
```
    
(l < r)の時、休憩所tから休憩所sまでの歩数は、
(上記のS[r] - S[l]以外の部分を求める)
(L = S[4]とする)

```
L - (S[r] - S[l]) = 0 ならばMの倍数
```

r, lに対してA[i]を全て探索するとO(N^2)になりTLEとなります。
(l < r)の時、rを固定して「片方を固定しての計算量の削減」を行います。

```
S[r] - S[l] = 0
```

S[r]が定数なので、

```
S[l] = S[r]
```

S[r]と同じ値がいくつあるかを数えると計測できます。
r = 2の時、S[r]は0、余りが0となるS[l]の要素はS[0]があります。
これは「① 1 ~ 3の歩数」に相当します。
(l < r)の時、S[r] - S[l]以外の部分を求める時は、

```
L - (S[r] - S[l]) = 0 ならばMの倍数
```

LとS[r]が定数なので

```
S[l] = S[r] - L
```

i=0, 
S[l] = S[r]は0になります。
S[l] = S[r] - Lは2になります。

i=1, 
S[l] = S[r]は2になります。
S[l] = S[r] - Lは1になります。

上記の式を使用し、cntの配列を用意してコードを実装します。

```
for(int r=0; r<N; r++){
    ans += cnt[S[r]];
    ans += cnt[(S[r] - L + M) % M];
    cnt[S[r]]++;
}
```

表にしてみましょう。

| i                 | 0           | 1           | 2           | 3           | 4           |
|:------------------|------------:|------------:|------------:|------------:|------------:|
| S[i]       | 0           | 2           | 0           | 1           | 1           |
| cnt[0]            | 0           | 1           | 1           | 2           | -           |
| cnt[1]            | 0           | 0           | 0           | 0           | -           |
| cnt[2]            | 0           | 0           | 1           | 1           | -           |
| S[l] = S[r]       | 0           | 2           | 0           | 1           | -           |
| S[l] = S[r] - L   | 2           | 1           | 2           | 0           | -           |
| ans               | 0           | 0           | 2           | 4           | -           |

ansはサンプルの出力１と同じ答えになっています。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    vector<ll> S(N+1);
    rep(i, N) S[i+1] = (S[i] + A[i]) % M;

    ll L = S[N];
    ll ans = 0;
    vector<ll> cnt(M);
    rep(r, N){
        ans += cnt[S[r]];
        ans += cnt[(S[r]-L+M)%M];
        cnt[S[r]]++;
    }
    cout << ans << endl;

    return 0;
} 
```