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

A問題

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

私の解答

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

print("Won")

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

B問題

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

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を整数のまま足していきます．

私の解答

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問題

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

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

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

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

この計算量は一つの要素につき最大で配列A全体の長さであるN回比較とpへの加算を行い，それを配列の要素数N回繰り返すので計算量はO(N²)となります．制約ではNは10⁴以下とのことなので計算見積もりは最大で10⁸となります．これ，Python間に合うのか？不安だったので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問題

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

私の解答

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した時点でセブイレに行ってビールを買いました．今，ラブライブ虹ヶ咲学園スクールアイドル同好会のセブンイレブンイメージガール総選挙というのをやっていて，午後ティーを買えば推しの歩夢ちゃんと栞子ちゃんに投票できるのにそれを失念していてビールのみを買ってしまいました．こうしていてはいられないのでセブイレで午後ティーを買ってきます．ここまで読んでくださり，ありがとうございました！

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

A問題

B問題

C問題

D問題

最後に

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