ABC 189 振り返り

完全に趣味でAtCoderを始めました。そこまでガチガチに頑張っているわけではないですが、できる限り、ABCには参加するようにしています。
より上位を目指していくために、受験したABCを毎回しっかり、振り返っていきます。。

# 自己紹介
ABC189直前の状態で、ギリギリ茶色コーダーです。ただ、コンテスト参加回数は11回なので、もう少しコンテスト受ければ、緑コーダーに上がれるか。。。とワクテカしていました。
ちなみに、ABCでは、A,B,Cは30分以内には解き終わって、残りの時間でD問題を目指す。と言うのが、最近の状況です。
E,Fを解けるようになる程勉強はしておらず、今年のどこかでチャレンジできるようにしていきたいです。

ちなみに、言語は python でやっています。
pythonの勉強がてら、競技プログラミングをやってみるか。と言うのが、最初のモチベーションです。
※ python の勉強はちゃんとしたことはないし、仕事で使ったこともない。なので、pythonの変数ルールとか、あまり守れていない。。。

↓自分のアカウントです。
https://atcoder.jp/users/takeucom
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/237079/9c7ebf17-dd87-d89e-098d-11bad66aacd8.png)


# 結果
A,B,D は解き終わりました。
ただ、今回は間違いが多かった。。。反省しまくりです。
その辺りを振り返りがてら、整理します。

![676A9F33-920A-4A12-952D-1C14D01D9671_4_5005_c.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/237079/f56338ec-0813-53fe-2d2b-42ab9e075bb6.jpeg)

# 各問題の解法と振り返り
## A: Slot
https://atcoder.jp/contests/abc189/tasks/abc189_a

1問目は特に問題なく完了。

```python
s = input()
 
print('Won' if s[0] == s[1] == s[2] else 'Lost')
```




## B: Alcoholic
https://atcoder.jp/contests/abc189/tasks/abc189_b

2問目も特に問題なく完了。と思ったら、まさかの間違い。。。

NGプログラム

```python
N, X = list(map(int, input().split()))
 
total = 0
ans = -1
for i in range(N):
  v, p = list(map(int, input().split()))
  total += v * p / 100
  if total > X:
    ans = i + 1
    break
 
print(ans)
```

他の問題をある程度進めてから、振り返ってみると、割り算でもしかしたら、おかしいことになっているのでは？と気付き、割り算を使用しない方針に変更したところ、正解。
過去にpythonで割り算をしたところ、精度の問題で間違えたことがあったのに、ハマってしまった。 `/ 100` と言うキリが良い数で問題が起きるとは、盲点であった。。。

OKプログラム

```python
N, X = list(map(int, input().split()))
 
total = 0
ans = -1
for i in range(N):
  v, p = list(map(int, input().split()))
  total += v * p # 割り算を使用しないようにする。
  if total > X * 100:  # 割り算をしない分、100を掛けるように変更
    ans = i + 1
    break
 
print(ans)
```

## C:Mandarin Orange
https://atcoder.jp/contests/abc189/tasks/abc189_c

問題を見たところ、全探索ならなんとなくかけそう。。。と思いましたが、 
N=10^4 となっており、何も考えずに書くと、10^8くらいの計算量になりそうで、全探索がギリギリ難しいかもな。。。と言う問題。
一旦、D問題を解いた後に戻ってきました。

結論から言うと、 C++ だったら、解けていたっぽい。。。

一旦、ちょっと工夫した全探索で問題を書いてみるもののTLEになってしまった。。。
と言うところで、時間が来てしまったので、今回は解けず。。。

解説を見ると、ほぼほぼ同じ方法で解いている。。。
C++に変換してみると、普通に成功した。。。

Python:

```python
N = int(input())
a = list(map(int, input().split()))
 
max_count = 0
for l in range(N):
  x = a[l]
  t_mac_count = x
  for r in range(l, N):
    if a[r] < x:
      x = a[r]
    c = x * (r - l + 1)
    if c > t_max_count:
      t_max_count = c
  if t_max_count > max_count:
    max_count = t_max_count
print(max_count)
```

C++:

```C++
#include<bits/stdc++.h>
using namespace std;
int a[10010];
int main(){
	int n;
	cin >> n;
	for(int i=0;i<n;i++)cin >> a[i];
	int ans=0;
	for(int l=0;l<n;l++){
		int x=a[l];
		for(int r=l;r<n;r++){
            if(a[r] < x) {
                x = a[r];
            }
            int c=x*(r-l+1);
			ans=max(ans,c);
		}
	}
	cout << ans;
}
```

## D:Logical Expression
https://atcoder.jp/contests/abc189/tasks/abc189_d

この問題は、紆余曲折があって、ようやく解けたので、その経緯を書いていきます。

### bit全探索で解いてみる。
まずは、bit全探索で解いてみるが、当たり前の如くTLE...

```python
N = int(input())
 
s = []
for _ in range(N):
  s.append(input())
 
 
count = 0
for i in range(2 ** (N + 1)):
  ans = i >> 0 & 1
  for j in range(N):
    x = i >> (j + 1) & 1
    if s[j] == 'AND':
      ans = ans and x
    else:
      ans = ans or x
  if ans:
    count += 1
 
print(count)
```

### 論理的に問題がある状態で解いてしまう。

次に、 `OR` で区切ることを考える。 `OR`で区切れば、区切ったブロックごとにその演算がTRUEになれば、全パターン網羅できたことになるのじゃないかな？と。
要は、
{...AND...AND...AND} OR {AND...AND...AND} ...　と言う感じでブロックで区切ることを考えると、
1つのブロックが全てFALSEになるパターン数は求められるので、
全パターンから FALSE OR FALSE OR FALSE と全てFALSEになるケースを引けば、答えが出るんじゃないの！？と言うことで、プログラムを書いてみる。

例題では、正解が出たのですが、実際には間違い。。。

```python
N = int(input())
 
false_pattern = 1
and_count = 1
for _ in range(N):
  if input() == 'OR':
    false_pattern *= 2 ** (and_count) - 1
    and_count = 1
  else:
    and_count += 1
false_pattern *= 2 ** and_count - 1
 
print(2 ** (N + 1) - false_pattern)
```

### bit全探索の結果と自作の問題を掛け合わせることによって、考え変えたの間違いに気づく。
何が違うんだ！と言うことで、自作の問題を作って、いくつか試してみるが、自分の考えとロジックは間違ってなさそう。
考え方が違うのかな？と言うことで、bit全探索で答えを出してみると、明らかに答えが違った。

ここで、考え方の間違いに気づく。
`論理演算は前から演算していくから、そもそもブロックの考え方が間違っているじゃないか！`

と言うことで、1から考えることに。。。

### 答えを導く。
順番に演算していく必要がある、と言うことを基にもう一度解き方を考えてみる。
- ANDが来たら、ANDの直前の結果がTrueで直後がTrueだったら、Trueになる。
- ORが来たら、ORの直前の結果がTrueで直後がTrue / False か、直前の結果がFalseで直後がTrueだった、Trueになる。

と言うことを思いつき、`True / False のパターンの数をちゃんと数えていけば、計算量も少なく、結果が導けるのでは！？` と考え、早速書いてみたところ、うまくいく！！

```python
N = int(input())
 
t = 1 # Trueとなるパターン数
f = 1 # Falseとなるパターン数
for _ in range(N):
  if input() == 'OR':
    t = t + f + t
    f = f
  else:
    t = t
    f = t + f + f
 
print(t)
``` 

# 総括
今回は、反省が残る結果に。。。とは言え、次への教訓はシンプルで、
- python だと計算量とか精度の問題で、不利である。
- 結果の確認は重要。簡単なパターンを自作で問題を考えて、ちゃんとチェックした方が良い。

と言うことで、次のABCでは、以下を実践しようと思う。
- 簡単な問題はpython。複雑そうな問題は、C++で解くようにする。
- 問題を間違えたら、自作の問題を数パターン作成して、確認するようにする。簡単であれば、全探索のプログラムを作った方が確実。