AtCoder Beginner Contest 401

## [A - Status Code](https://atcoder.jp/contests/abc401/tasks/abc401_a)

O(1)
下記を判定しましょう。

```math
200 <= N < 300
```

```C++:C++
#include <bits/stdc++.h>

using namespace std;

int main() {
    int N;
    cin >> N;
    if(200 <= N && N < 300) cout << "Success" << endl;
    else cout << "Failure" << endl;
    return 0;
} 
```

## [B - Unauthorized](https://atcoder.jp/contests/abc401/tasks/abc401_b)

O(N)
loginをしているか状態を管理しましょう。

```C++:C++
#include <bits/stdc++.h>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<string> S(N);
    for(int i=0; i<N; i++) cin >> S[i];

    bool isLogin = false;
    int ans = 0;
    for(int i=0; i<N; i++){
        if(S[i] == "login") isLogin = true;
        if(S[i] == "logout") isLogin = false;
        if(S[i] == "private" && isLogin == false) ans++;
    }
    cout << ans << endl;
    
    return 0;
} 
```

## [C - K-bonacci](https://atcoder.jp/contests/abc401/tasks/abc401_c)

O(N)
フィボナッチ数列の問題の亜種です。
２つ前までの要素の合計ではなく、K個前までの合計を探索します。

```C++:C++
#include <bits/stdc++.h>

using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N+1);

    if(N < K){
        cout << 1 << endl;
        return 0;
    }

    for(int i=0; i<K; i++) A[i] = 1;

    int inf = 1e9;
    int sum = K;
    for(int i=K; i<=N; i++){
        A[i] = sum;
        sum = (A[i] + sum) % inf;
        sum = (sum - A[i-K] + inf) % inf;
    }
    cout << A[N] << endl;

    return 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, K;
    cin >> N >> K;
    vector<int> A(max(N+1, K));
    vector<int> S(A.size()+1);

    rep(i, K) A[i] = 1;
    rep(i, K) S[i+1] = S[i] + A[i];

    const int mod = 1e9;
    for(int i=K; i<=N; i++){
        A[i] = (S[i] - S[i-K] + mod) % mod;
        S[i+1] = (S[i] + A[i]) % mod;
    }
    cout << A[N] << endl;

    return 0;
} 
```

すぬけさんのコードは綺麗ですね。
いつも参考になります。

## [D - Logical Filling](https://atcoder.jp/contests/abc401/tasks/abc401_d)

O(N)
奇数と偶数の関係を求める問題です。
下記のサンプルで考察しましょう。

```
10 4
.o.??.?.??
```

`o`は連続しないという条件があります。
`?`が連続せず一つだけのグループでは`?`を最大で１つ`o`に置き換えることができます。
`??`が連続して二つのグループでは`??`を`o?`と`?o`に置き換えることができ、`o`の位置を固定できない為、`??`となります。

```
.o.??.o.??
```

```
6 3
.o.???
```

`??`が連続して三つのグループでは`???`を`o.o`と置き換えることができます。

```
6 3
.o.o.o
```

`?`が奇数個のグループの場合、`(n+1)/2`にて`o`の最大数を求めて置き換えることができます。
`?`が偶数個のグループの場合、`(n+1)/2`にて`o`の最大数を求めるのみになります。

1. `o`の数を求める
2. `?`の連続する数と、そのグループの数を探索する
3. Kと`o`の数、置き換えることができる`o`の最大数を判定する
4. `?`の奇数と偶数を判定して`?`を`o`と`.`に置き換える 

考察ができました。
コーディングします。

```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, K;
    cin >> N >> K;
    string S;
    cin >> S;

    int circle = 0;
    for(int i=0; i<N; i++) if(S[i] == 'o') circle++;

    if(circle == K){
        for(int i=0; i<N; i++) if(S[i] == '?') S[i] = '.';
        cout << S << endl;
        return 0;
    }

    for(int i=0; i<N-1; i++) if(S[i+1] == 'o' && S[i] == '?') S[i] = '.';
    for(int i=N-1; i>0; i--) if(S[i-1] == 'o' && S[i] == '?') S[i] = '.';

    int cnt = 0;
    vector<pair<int, int>> question;
    for(int i=0; i<N; i++){
        if(S[i] == '?'){
            cnt++;
        }else if(cnt>0) {
            question.emplace_back(i - cnt, cnt);
            cnt=0;
        }
    }
    if(cnt > 0) question.emplace_back(N - cnt, cnt);

    int sum = 0;
    for(auto [i, cnt]:question){
        sum += (cnt + 1) / 2;
    }

    if(sum == K - circle){
        for(auto [index, cnt]:question){
            if(cnt % 2 == 1){
                for(int i=index; i<index+cnt; i++){
                    if((i-index) % 2 == 0) S[i] = 'o';
                    else S[i] = '.';
                }
            }
        }
    }
    cout << S << endl;

    return 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, K;
    cin >> N >> K;
    string S;
    cin >> S;

    rep(i, N){
        if(S[i] == 'o'){
            if(i) S[i-1] = '.';
            if(i+1<N) S[i+1] = '.';
        }
    } 

    int x = K - count(S.begin(), S.end(), 'o');

    vector<pair<int, int>> question;
    rep(i, N){
        if(S[i] == '?'){
            int l = i;
            while(i<N && S[i] == '?') i++;
            question.push_back({l, i});
        }
    }

    int mx = 0;
    for(auto [l, r]:question) mx += (r-l+1) / 2;

    if(x == 0){
        for(auto [l, r]:question){
            for(int i=l; i<r; i++) S[i] = '.';
        }
    }else if(x == mx){
        for(auto [l, r]:question){
            if((r-l) % 2 == 0) continue;
            rep(i, r-l){
                S[l+i] = "o."[i%2];
            }
        }
    }
    cout << S << endl;

    return 0;
} 
```

すぬけさんのコードは綺麗ですね。
このコードを本番のコンテストでコーディングするのは難しい。