Pythonで毎日AtCoder #52

はじめに

前回
今日は、AGC-Aを3問解きます。

#52

AGC040-A

考えたこと
考え方は分かったのですが、実装ができませんでした。$a$を$[0]*(n+1)$のlistとします。私が実装でこけてたのは、'<'と'>'の両方をいっしょに処理しようとしていたからです。Nも$5 * 10^5$程度なので、$O(2N)(計算量は係数は無視)$くらいは通ります。まずは、'<'から処理します。$s[i]=='<'$なら$a[i+1]$は$a[i]+1$になります。
次に'>'について処理しますが、すこし工夫が必要です。'>'は不等号の関係より、後ろから計算しないといけません。ですので、range(n)にreversedをかけます。$s[i]=='>'$なら$a[i]=max(a[i+1]+1,a[i])$を取ります。最後に$sum(a)$を取ります。

s = list(input())
n = len(s)

a = [0] * (n+1)
for i in range(n):
    if s[i] == '<':
        a[i+1] = a[i]+1
for i in reversed(range(n)):
    if s[i] == '>':
        a[i] = max(a[i+1]+1,a[i])
print(sum(a))

AGC015-A

考えたこと
$N=10^9$なので$O(N)$は通りません。$n=1$ → $a=b$ならば1、$a \neq b$ならば0です。また、$a$>$b$のときは0、$a$ = $b$のときは、1になります。
それ以外の場合を考えます。総和の最小値は$a*n$のときではありません。なぜなら、全て$a$のときは最大値が$b$にならないからです。よって、$a(n-1)+b$になります。同様に、総和の最大値は$b(n-1)+a$です。$a(n-1)+b$以上$b(n-1)+a$以下は全て作ることができます。よって和の個数は$b(n-1)+a-{a(n-1)+b}+1$になります。これを計算すると、$(b-a)(n-2)+1$に変形できます。式変形しなくても、計算できますがキレイな方がいいので変形しました。

n, a, b = map(int,input().split())

if n == 1:
    if a == b:
        print(1)
    else:
        print(0)
elif a >= b:
    if a == b:
        print(1)
    else:
        print(0)
else:
    ans = (b-a)*(n-2)+1
    print(ans)

AGC006-A

考えたこと
$N$が十分に小さいので、$s,t$のどちらかのスライスを順に$N$個調べそれがもう片方に含まれている最大の値を探します。

n = int(input())
s = input()
t = input()

c = 0
for i in range(n):
    d = t[:i]
    if d in s:
        c = i
if s == t: #もっと前に書いてforの処理を飛ばしてもいい
    print(n)
else:
    print(2*n-c)

まとめ

AGC-Aに難しい印象があるのは何故だろうか。今週のABCで茶色になります。ではまた、おやすみなさい。