はじめに
前回
今日は、AGC-Aを3問解きます。
#52
考えたこと
考え方は分かったのですが、実装ができませんでした。$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))
考えたこと
$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)
考えたこと
$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で茶色になります。ではまた、おやすみなさい。