AtCoder Beginner Contest 403

A - Odd Position Sum

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

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

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

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

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

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

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

| B_j - B_i| != D

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

サンプル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を求めます。

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

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

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

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

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

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

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

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;
}