AtCoder Beginner Contest 243

## [A - Shampoo](https://atcoder.jp/contests/abc243/tasks/abc243_a)

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

char ans[3] = {'F', 'M', 'T'};

int main() {
    int V;
    cin >> V;
    vector<int> A(3);
    rep(i, 3) cin >> A[i];

    int cnt=0;
    while(V>=0){
        V -= A[cnt];
        if(V<0){
            cout << ans[cnt] << endl;
        }
        cnt++;
        if(cnt>2) cnt=0;
    }

    return 0;
} 
```

残り９５分

## [B - Hit and Blow](https://atcoder.jp/contests/abc243/tasks/abc243_b)

O(N)
制約は、1≤N≤1000です。
O(N^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> A(N), B(N);
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> B[i];

    int ans1=0, ans2=0;
    rep(i, N){
        if(A[i] == B[i]) ans1++;
        rep(j, N){
            if(i==j) continue;
            if(A[i] == B[j]) ans2++;
        }
    }
    cout << ans1 << endl << ans2 << endl;

    return 0;
} 
```

残り９0分

## [C - Collision 2](https://atcoder.jp/contests/abc243/tasks/abc243_c)

O(N)
y座標でグループ分けします。
0≤Yi≤10^9の為、配列での管理はできません、連想配列を使用します。

'L'と'R'でグループ分けして、
Rの要素より大きいLの要素があるなら"Yes"。

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

    map<int, vector<P>> mp;
    rep(i, N){
        P p;
        int y;
        cin >> p.first >> y;
        p.second = i;
        mp[y].push_back(p);
    }
    
    string s;
    cin >> s;
    int ok=0;
    for(auto m:mp){
        vector<P> v = m.second;
        if(v.size()<2) continue;

        sort(v.begin(), v.end());

        char l = ' ';
        for(auto vv:v){
            if(s[vv.second] == 'R') l = 'R';
            if(l == 'R' && s[vv.second] == 'L') ok = 1;
        }
        if(ok) break;
    }
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}  
```

残り70分

## [D - Moves on Binary Tree](https://atcoder.jp/contests/abc243/tasks/abc243_d)

O(N)
まず完全二分木である整数の性質を見つけます。
親の要素は、X　/=　2
左の子要素は、X　=　X　*　2
右の子要素は、X　=　X　*　2　+　1
であることが分かります。
しかし、「高橋君が N 回の移動後にいる頂点の番号は10^18以下である」という制約から、
オーバーフローする事が推測できます。
よってpythonで次のコードを提出しました。

```python:python
import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    N, X = list(map(int, input().split()))
    S = str(input())

    for i in range(N):
        if S[i] == 'U':
            X = X//2
        elif S[i] == 'L':
            X = X*2
        elif S[i] == 'R':
            X = X*2+1
    
    print(int(X))

# エントリポイント
if __name__ == '__main__':
    main()
```

TLEとなりました。
大きな桁数の為、計算に時間がかかりTLEとなっています。
オーバーフローしないための工夫が必要です。
まず、最もオーバーフローするテストデータを作成します。

```text:text
(R or L)が5*10^5並んだ文字列 + 'U'が5*10^5並んだ文字列
```

ここから考察します。
５というデータを、X　=　X　*　2 or (X　=　X　*　2　+　1)してからX　=　X　/　2をします。

```text:text
(LU) 5*2=10   10/2=5
(RU) 5*2+1=11 11/2=5
(UL) 5/2=2    2*2=4   
(UR) 5/2=2    2*2+1=5
```

(L or R)の次に(U)があるなら２文字を消去しても大丈夫そうです。
'U'+(L or R)は不可逆です。
消去する操作は、

```text:text
RRRR + 'U'　→ RRR
RRR + 'U'　→ RR
RR + 'L'　→ RRL
RRL + 'U'　→ RR
```

のような操作を行います。
・First in last outの操作ができる事
・最後に先頭の文字列から最後の文字列までループできる事
よってdequeを使用します。

```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() {
    ll N;
    ll X;
    cin >> N >> X;

    string s;
    cin >> s;
    deque<char> deq;
    rep(i, N){
        if(s[i] == 'U' && deq.size()>0 && deq.back() != 'U'){
            deq.pop_back();
        }else{
            deq.push_back(s[i]);
        }
    }

    while(deq.size()>0){
        char s = deq.front();
        deq.pop_front();
        if(s == 'U') X = X/2;
        else if(s == 'L') X = X*2;
        else if(s == 'R') X = X*2+1;
    }
    cout << X << endl;

    return 0;
} 
```

考察が終わったのでpythonをやめて全てC++で書き直しました。
ACです。

残り35分