AtCoder Beginner Contest 411

## A - Required Length
[問題文](https://atcoder.jp/contests/abc411/tasks/abc411_a)

O(1)
データ構造の問題です。
stringの長さを取得して比較しましょう。

```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 n;
    string s;
    cin >> s >> n;

    if(s.length() >= n){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}
```

## B - Distance Table
[問題文](https://atcoder.jp/contests/abc411/tasks/abc411_b)

O(N^2)
全探索の問題です。
制約が小さいので2重ループで処理ができます。

```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 n;
    cin >> n;
    vector<int> d(n-1);
    rep(i, n-1) cin >> d[i];

    rep(i, n){
        int sum = 0;
        repx(j, i, n-1){
            sum += d[j];
            cout << sum;
            if(j < n-1) cout << ' ';
        }
        cout << endl;
    }

    return 0;
} 
```

## C - Black Intervals
[問題文](https://atcoder.jp/contests/abc411/tasks/abc411_c)

制約は、
`1≤N,Q≤5×10^5`
なので2重ループで全探索を行うとTLEを起こします。

別の手法を考察しましょう。
黒く塗られたマスが連続している区間の数をansとします。
a_iのマスを黒にした時、
- 左右に黒があるならans--
- 左右に黒がないならans++
- 左右の片方のみ黒なら増減なし

a_iのマスを白にした時、
- 左右に黒があるならans++
- 左右に黒がないならans--
- 左右の片方のみ黒なら増減なし

これでO(q)で処理をできます。
下記がコンテスト中のACのコードです。

```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 n, q;
    cin >> n >> q;
    vector<int> a(q);
    rep(i, q) cin >> a[i];

    vector<bool> graph(n);

    if(n==1){
        rep(i, q){
            graph[a[i]-1] = !graph[a[i]-1];
            if(graph[a[i]-1]) cout << 1 << endl;
            else cout << 0 << endl;
        }
        return 0;
    }

    int cnt = 0;
    rep(i, q){
        graph[a[i]-1] = !graph[a[i]-1];

        if(graph[a[i]-1]){
            if(a[i]-2 >= 0 && graph[a[i]-2] && a[i] < n && graph[a[i]]){
                cnt--;
            }
            if(a[i]-2 >= 0 && graph[a[i]-2] == false && a[i] < n && graph[a[i]] == false){
                cnt++;
            }
            if(a[i]-2 < 0 && a[i] < n && graph[a[i]] == false){
                cnt++;
            }
            if(a[i]-2 >= 0 && graph[a[i]-2] == false && a[i] >= n){
                cnt++;
            }         
        }else{
            if(a[i]-2 >= 0 && graph[a[i]-2] && a[i] < n && graph[a[i]]){
                cnt++;
            }
            if(a[i]-2 >= 0 && graph[a[i]-2] == false && a[i] < n && graph[a[i]] == false){
                cnt--;
            }
            if(a[i]-2 < 0 && a[i] < n && graph[a[i]] == false){
                cnt--;
            }
            if(a[i]-2 >= 0 && graph[a[i]-2] == false && a[i] >= n){
                cnt--;
            } 
        }
        cout << cnt << endl;
    }

    return 0;
} 
```

もっと綺麗にできないか考察しましょう。
if文の分岐パターンが多くなっているのは、`vector<bool> graph(n);`で記載しているのが問題です。
`vector<bool> graph(n+2);`なら`a[i]-2`、`a[i] < n`の判定がいらなくなりますね。

```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 n, q;
    cin >> n >> q;
    vector<int> a(q);
    rep(i, q) cin >> a[i];

    vector<bool> graph(n+2);
    int ans = 0;
    rep(i, q){
        graph[a[i]] = 1 - graph[a[i]];

        if(graph[a[i]]){
            if(graph[a[i]-1] && graph[a[i]+1]){
                ans--;
            }else if(graph[a[i]-1] == false && graph[a[i]+1] == false){
                ans++;
            }      
        }else{
            if(graph[a[i]-1] && graph[a[i]+1]){
                ans++;
            }else if(graph[a[i]-1] == false && graph[a[i]+1] == false){
                ans--;
            }   
        }
        cout << ans << endl;
    }

    return 0;
} 
```

コードはかなり整理されました。

## D - Conflict 2
[問題文](https://atcoder.jp/contests/abc411/tasks/abc411_d)

考察が必要な問題です。
まず全探索のコードを書いてみました。

```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 n, q;
    cin >> n >> q;
    string server = "";
    vector<string> pc(n);
    rep(i, q){
        int query;
        cin >> query;

        if(query == 1){
            int p;
            cin >> p;
            p--;
            pc[p] = server;
        }
        if(query == 2){
            int p;
            string s;
            cin >> p >> s;
            p--;
            pc[p] += s;            
        }
        if(query == 3){
            int p;
            cin >> p;  
            p--;
            server = pc[p];     
        }
    }
    cout << server << endl;

    return 0;
} 
```

時間は2528msでTLE。
メモリは3627196KiBでMLE。
10^6の長さのstring型の連結がこの状態を発生させていると気づくことができます。
サーバーと関連ある文字列のみを処理しましょう。
逆順で処理をしてサーバーと関連ある文字列のみ保持をします。

```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 n, q;
    cin >> n >> q;
    vector<int> op(q), p(q);
    vector<string> s(q);
    rep(i, q){
        cin >> op[i] >> p[i];
        if(op[i] == 2){
            cin >> s[i];
            reverse(s[i].begin(), s[i].end());
        }
    }

    int server = 0;
    string ans = "";
    for(int t = q-1; t>=0; t--){
        if(op[t] == 1){
            if(server == p[t]){
                server = 0;
            }
        }else if(op[t] == 2){
            if(server == p[t]){
                ans += s[t];
            }      
        }else {
            if(server == 0){
                server = p[t];
            }
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;

    return 0;
} 
```

`p`のPCの文字をサーバーの文字で上書きするので、

```C++:C++
            if(server == p[t]){
                server = 0;
            }
```

サーバーの文字を`p`のPCの文字で上書きするので、

```C++:C++
            if(server == 0){
                server = p[t];
            }
```

ここが実装で難しい所です。
何度も復習したいですね。
クエリを逆順する以外の回答も記載します。
追加する文字列をindexで管理ます。
その時に親ID+追加する文字列をpairで管理します。
最後に逆順で文字列を復元していきます。
結局何かを逆順で処理をしないといけないですね。

```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 n, q;
    cin >> n >> q;
    vector<int> pc(n+1);
    for(int i=0; i<=n; i++){
        pc[i] = i;
    }
    map<int, pair<int, string>> mp;
    int cnt = 0;
    rep(i, q){
        int query;
        cin >> query;

        if(query == 1){
            int p;
            cin >> p;
            pc[p] = pc[0];
        }
        if(query == 2){
            int p;
            string s;
            cin >> p >> s;
            reverse(s.begin(), s.end());
            int index = pc[p];
            pc[p] = n + cnt + 1;
            if(mp.find(index) != mp.end()){
                mp[pc[p]] = {index, s};
            }else{
                mp[pc[p]] = {-1, s};
            }
            cnt++;        
        }
        if(query == 3){
            int p;
            cin >> p;
            pc[0] = pc[p]; 
        }
    }
    string ans = "";
    if(mp.find(pc[0]) != mp.end()){
        auto item = mp[pc[0]];
        while(item.first != -1){
            string s = item.second;
            ans += s;
            item = mp[item.first];
        }
        string s = item.second;
        ans += s;
        reverse(ans.begin(), ans.end());
    }
    cout << ans << endl;

    return 0;
} 
```