Pythonで毎日AtCoder #33

はじめに

前回
今日はAtCoder ProblemsのBoot camp for Beginnersを埋めていきます。難易度はMediumです。

#33

AGC029-A
1TLE

考えたこと
難しい。操作を行なうとBとWが入れかわります。最終的に、左にWが右にBが集まることになります。$W_i(1\leq i\leq N)$が左に行くためには、そのWよりも左にある全てのBに対して操作をしなければなりません。ですので、$W_i(1\leq i\leq N)$の左にあるBの数を足していけば正解です。

s = list(input())

ans = 0
count_b = 0
n = len(s)
for i in range(n):
    if s[i] == 'B':
        count_b += 1
    if s[i] == 'W':
        ans += count_b

print(ans)

ABC139-D
1WA

考えたこと
余りに関する問題です。$N$までの整数を並びかえた数列$P$に対して、$i(1\leq i \leq N$を$P_i$で割ったときの余りの合計の最大値を求めます。$P$は$N$までの整数が昇順で並んでいると考えます。そのまま操作を行うと余りの合計は0になります。$P$を右に一つずらすと$N-1$になります。$i$に対して$P_i$が1だけ小さいからです。ということは左にずらした時に余りの合計が最大になることが分かります。なぜなら、左にずらすと$i$に対して$P_i$が1だけ大きくなります。すると$i \% P_i = i$になります。$P_i=1$にだけ余りが0になることに注意すると、余りの合計は$\frac{N(N-1)}{2}$になります。詳しい証明は解説に載っています。

n = int(input())

print(n*(n-1)//2)

まとめ

最近、精進不足なので明日のABCが不安です。ではまた、おやすみなさい。