AtCoder参加したったー （ABC189編）

こんにちは！バイオインフォマティクス系オタク修士学生のroadricefieldです！ひさびさにABCに参加したあと記事を書きたい気分と時間があるのでABC189の参戦記録を書きます！  

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

与えられる３文字が同じ文字かそうでないかを調べるだけです．私はそれぞれの文字が一文字目と一致するかどうかで判定しました．  

私の解答

```python
S = input()
C1 = S[0]
for i in range(3):
  if S[i] != C1:
    print("Lost")
    quit()

print("Won")
```

i = 0 のときが完全に無駄な処理ですがまあどうでもいいでしょう．  

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

高橋くんが入力のお酒を１杯ずつ飲んで行くので0で初期化した変数（*v*とします．）に高橋くんが飲んだアルコールの体積をひたすら足していきます．１杯飲んだら*v*が*X*を超えていないかどうかを判定して，もし超えていたならばその時点で高橋くんが飲んだお酒の杯数を出力して終了すればよいです．最後まで*v*が*X*を超えなければ`-1`を出力して終了です．公式の解説にもある通り，何度も浮動小数点演算を繰り返していると誤差がたまっていくので本当は*v = X*でも*v > X*となってしまう場合があります．なので

```python
N, X = map(int, input().split())

now = 0
for i in range(N):
  v, p = map(float, input().split()) #入力を浮動小数として受ける
  now += v*(p/100)
  if now > X:
    print(i + 1)
    quit()

print(-1)
```
のような書き方だと`WA`となります．（私もまんまとひっかかりました．）  

これを防ぐには浮動小数点ではなく整数だけで計算すればいいです．そのために高橋くんのお酒の強さ*X*を実際の100倍にしておき，*v*には実際の体積の100倍，つまり入力の*V × P*を整数のまま足していきます．  

私の解答  

```python
N, X = map(int, input().split())
X *= 100

now = 0
for i in range(N):
  v, p = map(int, input().split())
  now += v*p
  if now > X:
    print(i + 1)
    quit()

print(-1)
```  

# [C問題](https://atcoder.jp/contests/abc189/tasks/abc189_c)  

**C問題にしては難しくね！！？？**問題文を読み替えるとつまりは「配列*A*からある一つ区間を取る．その区間の最小値と区間の長さの積（*P*とする．）が最大となるときを探してその値を出力せよ」ということです．  

私の方針は以下のとおりです．  

1. 空配列`candi`を用意する．
1. 0で初期化した変数`p`を用意する．
2. 配列*A*から要素を一つ選んで`start`とする．  
3. `p += start`．
4. `start`の左隣の要素が`start`以上ならば`p += start`．
5. `start`よりも小さい要素が現れるまでさらに左の要素と`start`を比較して，それが`start`以上であれば`p += start`することを繰り返す．
6. `start`の右隣の要素が`start`以上ならば`p += start`．
7. `start`よりも小さい要素が現れるまでさらに右の要素と`start`を比較して，それが`start`以上であれば`p += start`することを繰り返す．
8. `p`を`candi`に加える．
9. 2~9を配列*A*のすべての要素について行う．
10. `candi`の最大値を出力する．  

上記のような操作を行うことである配列*A*に属する要素を最小値とする区間のとり方で*P*が最大となるときの*P*を集めていってその最大値を出力するという方針です．「ある配列*A*に属する要素を最小値とする区間のとり方で*P*が最大となるとき」とは選んだ要素が最小値である限り区間を左右に伸ばせるだけ伸ばしたときです．  

この計算量は一つの要素につき最大で配列*A*全体の長さである*N*回比較と`p`への加算を行い，それを配列の要素数*N*回繰り返すので計算量は*O(N<sup>2</sup>)*となります．制約では*N*は10<sup>4</sup>以下とのことなので計算見積もりは最大で10<sup>8</sup>となります．**これ，Python間に合うのか？**不安だったのでC++を使いました．  

私の解答  

```C++
#include<iostream>
using namespace std;
 
int main(){
	int N;
	cin >> N;
	int A[N];
	for(int i=0;i<N;i++){
		cin >> A[i];
	}
	int now_max = 0;
	int start;
	int ref1;
	int ref2;
	int j;
	int p;
	for(int i=0;i<N;i++){
		ref1 = 10000000;
		start = A[i];
		p = 0;
		j = i;
		while(ref1 >= start and j >= 0){
			p += start;
			j--;
			ref1 = A[j];
		}
		j = i+1;
		ref2 = A[j];
		while(ref2 >= start and j < N){
			p += start;
			j++;
			ref2 = A[j];
		}

		if(p > now_max) now_max = p; 
	}
    cout << now_max << endl;
    return 0;
}
```

上記のコードでは`candi`配列はつくらず，`start`を変えて計算するたびにそれまでの最大値`now_max`と`p`を比較して更新していっています．こちらのほうが最後に改めて最大値を探す計算を行わない分速いはずです．（たぶん......）  

# [D問題](https://atcoder.jp/contests/abc189/tasks/abc189_d)

N = 1，2，3のときで具体的な答えを計算していると下のように処理すれば答えを出せることに気づきました．  

私の解答  

```python
N = int(input())
S = []
for _ in range(N): S.append(input())

ans = 2**(N+1) - 1

minus = []
for i in range(N):
  if S[i] == "AND":
    minus.append(2**(i+1))

for d in minus:
  ans -= d

print(ans)
```

雑ですみません......  

# 最後に  

**C問題が難しくて肝を冷やしました．**規則性に気づくのに時間がかかってD問題も終了15分前に`AC`しました．当然私の実力ではE問題に挑戦しても解けないと思ったのでD問題を`AC`した時点でセブイレに行ってビールを買いました．今，ラブライブ虹ヶ咲学園スクールアイドル同好会のセブンイレブンイメージガール総選挙というのをやっていて，午後ティーを買えば推しの歩夢ちゃんと栞子ちゃんに投票できるのにそれを失念していてビールのみを買ってしまいました．こうしていてはいられないのでセブイレで午後ティーを買ってきます．ここまで読んでくださり，ありがとうございました！