AtCoder Beginner Contest 189

##[A - Slot](https://atcoder.jp/contests/abc189/tasks/abc189_a)

O(1)

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

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main() {
     string s;
     cin >> s;

     if(s[0] == s[1] && s[0] == s[2] && s[1] == s[2]) cout << "Won" << endl;
     else cout << "Lost" << endl;

    return 0;
}
```

##[B - Alcoholic](https://atcoder.jp/contests/abc189/tasks/abc189_b)

O(N)
全て整数で計算します。
言語によってはdecimalを使えますね。
コンピュータは２進数の計算しかできません。
全ての１０進数の少数を２進数で表すことはできません。
0.1を１０回足すと限りなく１に近い0.99999...になるのは有名です。

少数の計算はECサイトなどの消費税計算、ロボット工学などでのアームの細密操作などに使用します。
エンジニアを目指す方はぜひ覚えましょう！

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

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main() {
    ll n, x;
    cin >> n >> x;

    vector<ll> v(n), p(n);
    rep(i, n) cin >> v[i] >> p[i];

    ll sum=0;
    ll cnt=-1;
    rep(i, n){
        sum += v[i] * p[i];
        if(sum>x*100){
            cnt = i+1;
            break;
        }
    }
    cout << cnt << endl;

    return 0;
}
```

##[C - Mandarin Orange](https://atcoder.jp/contests/abc189/tasks/abc189_c)

O(N^2)
10000 * 10000 = 100000000, 1億ループです。
軽い処理なら、C++だと１sec以内にできます。
この処理時間の知識は必須です。
迷う場合は、clock関数を使用して、n=10000, Ai=100000の最大値で実行時間の計測を行うと提出できるかと思います。
下記のプログラムの場合は、1.000...secだったのでACを確信しました。

この２週間、数学Bの数列を勉強していました。
数列っぽく解答したかったので下記の手法を使いました。

###漸化式？
数学つよつよエンジニアの方がいましたら教えてください。
私は今年の全国模試の偏差値３５でした。

```txt:漸化式
dp_1_1 = 0
dp_i_(j+1) = dp_i_j + a_i (a_j >= a_i)
res = dp[i][j+1] (dp[i][j+1] > res)
```

###入力値

| 変数 | 入力値 |
|:-----------|------------:|
| n    | 6           |
| Ai   | 2 4 4 9 3 9 |

###２次元配列

| j/i | 2  | 4  | 4  | 9  | 3  | 9  |
|:----|---:|---:|---:|---:|---:|---:|
| 0   | 0  | 0  | 0  | 0  | 0  | 0  |
| 2   | 2  | 0  | 0  | 0  | 0  | 0  |
| 4   | 4  | 4  | 4  | 0  | 3  | 0  |
| 4   | 6  | 8  | 8  | 0  | 6  | 0  |
| 9   | 8  | 12 | 12 | 9  | 9  | 9  |
| 3   | 10 | 0  | 0  | 0  | 12 | 0  |
| 9   | 12 | 4  | 4  | 9  | 15 | 9  |

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

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int dp[10000][10001];

int main() {
    //clock_t t = clock();

    int n;
    cin >> n;
    //n = 10000;

    vector<int> a(n);
    rep(i, n){
        cin >> a[i];
        //a[i] = 100000;
    }

    int res = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(a[j] >= a[i]){
                dp[i][j+1] = dp[i][j] + a[i];
            }
            res = max(dp[i][j+1], res);
        }
    }
    cout << res << endl;
    //execution_time(t);

    return 0;
}
```

###感想
自己最高パフォーマンスの７８０が出ました。
２週間ほどAtCoderの過去問は解かずに、数学の参考書、共通テストの数学の問題を解いていました。
基礎学力の大切さを改めて実感しています。

#追記
##[D - Logical Expression](https://atcoder.jp/contests/abc189/tasks/abc189_d)

解説によると簡易的なdpとのことです。
true or falseの全てのパターンを漸化式にして処理を行います。

###漸化式

dp[0]をfalseの数
dp[1]をtrueの数

```txt:漸化式
dp[0]=1 (初期値)
dp[1]=1 (初期値)

dp[0] = dp[0] * 2 + dp[1] (s[i] == AND)
dp[1] = dp[1] * 2 + dp[0] (s[i] == OR)
```

###y[0]

| x |
|--:|
| 1 |
| 0 |

###y[1]

| x | y | OR |
|--:|--:|--:|
| 1 | 1 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 0 | 0 |

###y[2]

| x | y | z | OR |
|--:|--:|--:|--:|
| 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 |

x0 = trueの場合、x1がfalseでもtrueでも必ずtrueになります。
その為、true数*2を加算。
x0 = falseの場合、x1がtrueのみtrueになります。
その為、false数を加算。

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

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main() {
    int n;
    cin >> n;
    vector<int> S(n);
    vector<ll> dp(2, 1);
    rep(i, n){
        string s;
        cin >> s;

        if(s == "AND"){
            dp[0] = dp[0]*2 + dp[1]; 
        }else{
            dp[1] = dp[1]*2 + dp[0];
        }
    }
    cout << dp[1] << endl;

    return 0;
}
```

##感想
もう少し漸化式を勉強しないと難しい。