AtCoder Beginner Contest 409

## A - Conflict

[問題文](https://atcoder.jp/contests/abc409/tasks/abc409_a)

O(N)

ループ文の問題です。

```C++:C++
if(t[i] == 'o' && a[i] == '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;
    cin >> n;
    string t, a;
    cin >> t >> a;
    rep(i, n){
        if(t[i] == 'o' && a[i] == 'o'){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}
```

## B - Citation

[問題文](https://atcoder.jp/contests/abc409/tasks/abc409_b)

O(N^2)
日本語を読むのが難しい問題です。
Aに、`x`以上の要素が重複を含めて`x`回以上現れるか。
を求める問題です。

```
3
1 2 1
```

の時、1の要素は1以上、2回現れます。
条件を満たしています。

```
1
```

になります。
もう一つサンプルを書きましょう。

```
5
0 5 5 5 5
```

の時、5の要素は4回現れます。
5回以上ではないので条件を満たしません。
4は5が4回以上現れるので条件を満たしています。

```
4
```

考察が終わりました。

```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];
    sort(a.begin(), a.end());
    int ans = 0;
    rep(i, 101){
        int cnt = 0;
        rep(j, n){
            if(a[j] >= i){
                cnt++;
            }
        }
        if(cnt >= i) ans = max(ans, i);
    }
    cout << ans << endl;
    return 0;
} 
```

## C - Equilateral Triangle

[問題文](https://atcoder.jp/contests/abc409/tasks/abc409_c)

O(N)
1辺の長さは`l / 3`です。
３点の距離が等しい時、`l % 3 == 0`の時だけ判定を行います。
0スタートです。
下記のように値を受け取りましょう。

```C++:C++
    ll n, l;
    cin >> n >> l;
    vector<ll> cycle(l);
    ll p = 0;
    cycle[p]++;
    rep(i, n-1){
        int d;
        cin >> d;
        p+=d;
        p %= l;
        cycle[p]++;
    }
```

円周上のどの点かは下記で判断できます。

```
p % l
```

3辺の距離は等しい組み合わせの数は、

```C++:C++
    ans += cycle[(i) % l] * cycle[(i+ab) % l] * cycle[(i+ab+ab) % l];
```


```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() {
    ll n, l;
    cin >> n >> l;
    vector<ll> cycle(l);
    ll p = 0;
    cycle[p]++;
    rep(i, n-1){
        int d;
        cin >> d;
        p+=d;
        p %= l;
        cycle[p]++;
    }

    if(l % 3 != 0){
        cout << 0 << endl;
        return 0;
    }

    ll ab = l / 3;
    ll ans = 0; 
    rep(i, l){
        ans += cycle[(i) % l] * cycle[(i+ab) % l] * cycle[(i+ab+ab) % l];
    }
    cout << ans / 3 << endl;

    return 0;
} 
```

## D - String Rotation

[問題文](https://atcoder.jp/contests/abc409/tasks/abc409_d)

O(N)
1つの入力ファイルに含まれるNの総和は10^5以下とあります。
全探索で間に合います。

最初に`a[i] > a[i+1]`となった`a[i]`を`t`とします。
`t`が`a[i] > a[i+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; }

void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;

    char first = ' ';
    rep(i, n-1){
        if(s[i] > s[i+1]){
            if(first == ' '){
                first = s[i];
            }else if(first != ' ' && first != s[i]){
                break;
            }
            swap(s[i], s[i+1]);
        }
    }
    cout << s << endl;
}

int main() {
    int t;
    cin >> t;
    rep(i, t){
        solve();
    }
    return 0;
} 
```

もう少し綺麗な書き方を考察しましょう。
`l`から、`l+1`と`r`の間を基準に回転させます。

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

void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;

    int l = -1;
    rep(i, n-1){
        if(s[i] > s[i+1]){
          l = i;
          break;
        }
    }
    if(l != -1){
      int r = n-1;
      repx(i, l+1, n-1){
        if(s[l] < s[i+1]){
          r = i;
          break;
        }
      }
      rotate(s.begin()+l, s.begin()+(l+1), s.begin()+(r+1));
    }
    cout << s << endl;
}

int main() {
    int t;
    cin >> t;
    rep(i, t){
        solve();
    }
    return 0;
} 
```