AtCoder Beginner Contest 403

## [A - Odd Position Sum](https://atcoder.jp/contests/abc403/tasks/abc403_a)

O(N)
A_iの奇数の要素だけカウントします。
0スタートなのでコードでは偶数をカウントしています。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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 N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    int ans = 0;
    rep(i, N){
        if(i % 2 == 0) ans += A[i];
    }
    cout << ans << endl;
    return 0;
} 
```

## [B - Four Hidden](https://atcoder.jp/contests/abc403/tasks/abc403_b)

O(T*U)
全探索です。
２重ループでコードを書きましょう。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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() {
    string t, u;
    cin >> t >> u;
    int n = t.size();
    int m = u.size();

    rep(i, n - m + 1){
        int cnt = 0;
        rep(j, m){
            if(t[i+j] == u[j] || t[i+j] == '?') cnt++;
        }
        if(cnt == m){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;

    return 0;
} 
```

## [C - 403 Forbidden](https://atcoder.jp/contests/abc403/tasks/abc403_c)

O(Q*logM)
O(Q)
・コンテストの全ページへのアクセス権限を管理する配列
・コンテストの各ページへのアクセス権限を管理する配列(vector<set>)
を用意します。

コンテストの各ページへのアクセス権限を管理する配列(vector<set>)
のみだと2のクエリの時、setに全てのコンテストのページ番号をinsertします。
O(Q*M)になりTLEになります。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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 N, M, Q;
    cin >> N >> M >> Q;

    vector<set<int>> A(N);
    vector<bool> B(N, false);

    rep(i, Q){
        int query;
        cin >> query;

        if(query == 1){
            int x, y;
            cin >> x >> y;
            x--; y--;
            A[x].insert(y);
        }

        if(query == 2){
            int x;
            cin >> x;
            x--;
            B[x] = true;
        }

        if(query == 3){
            int x, y;
            cin >> x >> y;
            x--; y--;
            if(B[x] || (A[x].find(y) != A[x].end())){
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }
        }
    }

    return 0;
} 
```

## [D - Forbidden Difference](https://atcoder.jp/contests/abc403/tasks/abc403_d)

```math
| B_j - B_i| != D
```

となるように、必要な要素を削除します。
削除する要素を最小の数にする問題です。
全探索を考察します。

```txt:サンプル1
5 2
3 1 4 1 5
```

全探索で3を基準に、1, 4, 1, 5の要素を順番に比べて差分が2か判定します。
O(N^2)の計算量になり、`N <= 2 * 10^5`なのでTLEになります。
2重ループでは処理が間に合いません。
各要素の値の数を探索します。

| A_i | 1 | 3 | 4 | 5 |
|:-:|:-:|:-:|:-:|:-:|
| cnt_i | 2 | 1 | 1 | 1 |

この表からA_i + Dの関係の要素だけ判定して、最大の要素数になる数列Bを求めます。

```math
ans = sum(cnt) - size(最大の要素数になる数列B)
```

で、「最小でいくつの要素を削除すればよいか」を求めることができそうです。
漸化式は、

```math
dp[i+1][1] = max(dp[i][0], dp[i][1])
```

```math
dp[i+1][0] = dp[i][1] + cnt[i]
```

サンプル1では1, 3, 5の要素の時、D = 2の差分の関係になっています。
dpの表

| cnt | 2 | 1 | 1 |
|:-:|:-:|:-:|:-:|
| 0 | 2 | 1 | 3 |
| 1 | 0 | 2 | 2 |

```math
sum(cnt) - max(dp[n][1], dp[n][0]) = 4 - 3 = 1
```

サンプル1の出力と一緒になっています。
考察ができました。

すぬけさんのコードです。
とても綺麗ですね。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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 solve(vector<int>& a){
    int n = a.size();
    vector<vector<int>> dp(n+1, vector<int>(2, 0));
    rep(i, n){
        dp[i+1][1] = max(dp[i][1], dp[i][0]);
        dp[i+1][0] = dp[i][1] + a[i];
    }
    int m = max(dp[n][1], dp[n][0]);
    int sum = 0;
    rep(i, n) sum += a[i];
    return sum - m;
}

int main() {
    int N, D;
    cin >> N >> D;
    int m = 1000005;
    vector<int> cnt(m);
    rep(i, N){
        int a;
        cin >> a;
        cnt[a]++;
    }

    int ans = 0;
    if(D==0){
        rep(i, m){
            if(cnt[i] > 0) ans += cnt[i]-1;
        }
    }else{
        rep(si, D){
            vector<int> a;
            for(int i=si; i<m; i+=D){
                a.push_back(cnt[i]);
            }
            ans += solve(a);
        }
    }
    cout << ans <<endl;

    return 0;
} 
```