ABC397(A~C)の解説動画とか見た

下記Youtube動画 A~C の解説をPythonに置き換えたもの。D以降はでき次第順次更新する予定。

• AtCoder Beginner Contest 397
• ABC397 解説動画

A - Thermometer

• 方針:
  • if - else 問題。
  • 与えられるX少数第一位までなので計算誤差とかはあまり気にしなくてもいいが、気になるんだったら eps を足して揺らぎを解決してもいい。

x = float(input())
eps = 1e-9

if 38.0 <= x + eps:
    print(1)
elif 37.5 <= x + eps:
    print(2)
else:
    print(3)

B - Ticket Gate Log

• 方針1: 貪欲法
  • 戦闘から順に挿入する必要があるかを判定する
  • $S$ が $100$ 以下なので可能

s = input()
ans = 0
expect = 'i'

for c in s:
    if c != expect:
        ans += 1
    else:
        expect = 'o' if expect=='i' else 'i'
if s[-1] == 'i':
    ans += 1

print(ans)

• 方針2:
  • io と連なっている部分は正常な部分なので、 io を除外した時に残っているのが壊れている箇所が連なった文字列。
  • もとの形は io で、残るのは i か o なので、残った文字列の長さだけ足し合わせれば良い。

s = input().replace('io', '')
print(len(s))

C - Variety Split Easy

• 方針0: TLE コード
  • 目安は 10^8
  • set(a[:i]) の作成に O(N) で、それを n-1 回繰り返すので計算量としては O(N^2) になる。
  • N^2 ~ 10^10 で目安の桁をオーバーしている。

n = int(input())
a = [x for x in input().split()]
ans = 0

for i in range(1, n):
    x = len(set(a[:i])) + len(set(a[i:]))
    if x > ans:
        ans = x

print(ans)

• 方針1:
  • for 文の中で set(配列) をやったらTLEになるので、対策として、set.add(x) で計算数を減らす。
  • numl: [0, 1, 2, 3, ..., 10]
  • numr: [10, ..., 2, 2, 1, 0]
  • numl と numr の同じ箇所を足すと種類数の和を求められる
    • 0 は None | a で分けられた場合

n = int(input())
a = [int(x) for x in input().split()]

numl = [0] * (n + 1)
numr = [0] * (n + 1)

st = set()
for i in range(n):
    st.add(a[i])
    numl[i + 1] = len(st)

st = set()
for i in range(n - 1, -1, -1):
    st.add(a[i])
    numr[i] = len(st)

ans = max(numl[i] + numr[i] for i in range(1, n))
print(ans)