【初心者勝手に解説AtCoder】ABC189の私の回答と考え方を公開します

今回はAtCoderのABC189を題材に初級者の私の回答とその思考過程を説明します。

この記事シリーズは「こんなレベルでも大丈夫なのか」と皆さんにぜひ思っていただくのが目的なので1つの参考になれば嬉しいです。

ABC189の問題

全体について

今回の問題のdifficultyはこんな感じです。difficultyの数値はその値のAtCoderのレートの人が50%正答できるという基準です。ざっくりとした難易度に翻訳したものを一番右の列に書いています。

残念ながら時間内にD問題を提出できなかったため出来としては良くないですが、道筋は立ったので今回もD問題まで紹介します。

A問題

3文字の英字が同じ文字かどうかを判定する問題です。3文字の文字列として入力を受け取るので1文字ずつ比較すればOKです。

x = input()
if x[0] == x[1] == x[2]:
    print("Won")
else:
    print("Lost")

B問題

$i$番目に飲むお酒に含まれるアルコールの量は$V_i \times P_i / 100$mlです。アルコールは蓄積されるので、毎回飲むアルコールごとに、総摂取量が$X$mlを超えるかどうかを判定すればOKです。

数学のように割り算を使うのは誤差のもとになるのでなるべく避ける意味でもどちらも100倍した値の大小を比較するようにしています。

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

C問題

真っ先に思いつく脳筋戦法は1から$N$のうち$l$と$r$の取りうるすべての組み合わせを試して最大値を求めるという方法ですね。しかしその組み合わせは約$N^2$通りで時間内には処理するのは厳しそうなので少し考えます。

まずわかるのは$l$から$r$まで選んだときの最大のみかんの個数は、選んだ区間の中の最小の$A_i$と区間内の皿の枚数の積だとわかります。なぜなら各皿で食べるみかんの個数$x$は$x \leq A_i$という制限がついているからです。

そう考えると思いたのは数字を適当に選んだとき、その数字が最小となる区間はどこまでかを考えればよいのではないかということです。

そこで、左から順番に数字を選び、その数字が最小となる区間を求めて食べられるみかんの個数を計算し、その中から最大値を見つけるというものです。下の図だと赤い$A_3$に注目したときに左右どちらにも自分より小さい値に出会うまでは自分が最小値である区間となります。

そこで実装は$A_1$から始めて左右どちらの方向にも自分より小さい値がでるまで区間をどれだけ広げられるかを探索し、区間内の皿を数えるという作戦にしました。

N = int(input())
item = list(map(int, input().split()))

max_orange = 0
for i in range(len(item)):
    val = item[i]
    cnt = 1
    for j in range(1, i+1):
        try:
            if val <= item[i-j]:
                cnt += 1
            else:
                break
        except:
            break
    for j in range(1, N-i):
        try:
            if val <= item[i+j]:
                cnt += 1
            else:
                break
        except:
            break
    candidate = val * cnt
    if candidate > max_orange:
        max_orange = candidate

print(max_orange)

try-except句は探索の始点が両端だったときに、探索をしようとするとリストが存在しない場所をしてしまうことになり回避策として加えました。それ以上の意味はありません。

D問題

$y_i$が前の値$y_{i-1}$を引きずっている点がポイントですね。まずは$y_i$と$y_{i-1}$と$x_i$の関係を整理します。0はFalse、1はTrueを表します。

まず前提として$y_i$は0か1のどちらの値しかとらないということ。そして、$(x_0…x_N)$の組み合わせは$(y_0…y_N)$の組み合わせに1対1に対応しているということです。

• $S_i$がANDかつ$y_i=1$のとき、取りうる組み合わせは1通りに決まる
• $S_i$がANDかつ$y_i=0$のとき、取りうる組み合わせは3通りある
• $S_i$がORかつ$y_i=1$のとき、取りうる組み合わせは3通りある
• $S_i$がORかつ$y_i=0$のとき、取りうる組み合わせは1通りに決まる

${x_i}$の組み合わせの総数さえ求まれば良いので、${y_i}$の組み合わせを考えても同じです。例題で考えてみましょう。

上の表を参考にして$y_i$の取りうる組み合わせを樹形図で表したのが下図です。同じ組み合わせがあるように見えますが、対応する$x_i$の値が異なっているので実際には異なる組です。このように樹形図で表すと答えが５通りになるのは容易にわかります。

そこで実装では$y_i$は0か1のどちらの値しかとらない点に注目して、$y_i$の時点で0が何個、1が何個あるかのみに注目します。

例えば$y_2$では[0,1]、$y_1$は[1,2]です。$y_0$を計算する場合を考えます。$S_1$はANDです。

$y_1=0$の場合$y_0$は0の組が2通り、1の組が1通りです。さらに$y_1=1$の場合1の組が1通りに決まるので、$y_0$の組み合わせは下のように計算することができます。

[2, 1] + [0, 1] = [3, 2]

つまり$y_2=1$となりうるような$y_i$の組み合わせは3+2=5通りあるので、1対１に対応する$x_i$の組み合わせも5通りあると考えることができます。

以上を一般化すると次のように書くことができます。

N = int(input())

branch = [0, 1]
l = []

for i in range(N):
    cond = input()
    l.append(cond)
l.reverse()

for cond in l:
    val0, val1 = branch[0], branch[1]
    if cond == "AND":
        branch[0] += val0
        branch[1] += val0
    elif cond == "OR":
        branch[0] += val1
        branch[1] += val1
print(branch[0]+branch[1])

最後に

回答は全て私のgitHubに載せてありますので必要があればご覧ください。