1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

はじめに

前回
今日は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が不安です。ではまた、おやすみなさい。

1
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?