ABC328の解説記事 (PyPy3 ABCD)

# はじめに
問題は[こちら](https://atcoder.jp/contests/abc328/tasks)
初心者（灰色〜茶色）向けです。
# A - Not Too Hard
https://atcoder.jp/contests/abc328/tasks/abc328_a
## 考え方
問題の通り、配点リストのうち、X点以下のもののみを足せば良いです。
私はfilterを使用しました。

## 解答例
```Python3:私の解答
n, x = map(int,input().split())
print(sum(filter(lambda s:s<=x,map(int, input().split()))))
```
# B - 11/11
https://atcoder.jp/contests/abc328/tasks/abc328_b
## 考え方
月が最大100か月、日数は1か月あたり最大100日のため、最大10000日分の日付しかありません。そのため、$i月j日$($i=1,2,\dots , N,\space j=1,2,\dots ,D_i$) が1種類の文字で構成されているかを確認すればよいです。具体的には下記のように解答しました。
1. $i$と$j$を文字列として結合する
1. 結合した文字列を1文字ずつのリストにする
1. リストをセット化して、セットの長さが1になるかをチェックする
## 解答例
```Python3:私の解答
n = int(input())
d_n = list(map(int,input().split()))
ans = 0
for i in range(n) :
    month = str(i+1)
    for j in range(d_n[i]) :
        day = str(j+1)
        if len(set(list(month+day))) == 1 :
            ans += 1
print(ans)
```
# C - Consecutive
https://atcoder.jp/contests/abc328/tasks/abc328_c
## 考え方
まず、各クエリについて$O(N)$以上の計算をすると、計算量が$O(NQ)$になってしまうため、とても間に合いません。
そのため、事前に全部のパターンを算出できるようにしておき、各クエリについては$O(1)$などで計算できるようにしておく必要があります。
また、$L$番目〜$R$番目の個数などを計算する際には、*累積和*がしばしば有効であることが多いです。
考え方としては、下記のようなイメージです。
```math:
\begin{aligned}
L〜R番目の合計 
    & = L番目+(L+1)番目+\dots+R番目 \\
    & = (1番目+2番目+\dots+R番目) -  (1番目+2番目+\dots+(L-1)番目) \\
    & =  1〜R番目の合計 - 1〜(L-1)番目の合計 \\
\end{aligned}
```
$累積和[i] = 1〜i番目の合計$とすれば、
```math:
L〜R番目の合計 
     =  累積和[R] - 累積和[L-1]   
```
と表せます。


$A_i \space\space(i = 0,1,2,\dots,n)$ を下記のような数列とします。
```math:
A_i = \left\{ \,
    \begin{aligned}
    & 1 \space\space (Sのi-1文字目=Sのi文字目) \\
    & 0 \space\space (Sのi-1文字目\neq Sのi文字目) \\
    \end{aligned}
\right.
```
ここで、$A_0 = 0$としておく。
また、累積和の数列$B_i \space\space(i = 0,1,2,\dots,n-1)$を下記で表すと、
```math:
B_i = A_0 + A_1 + \dots + A_i 
```
です。
例えば、入力例1について考えると、

|$i$|0|1|2|3|4|5|6|7|8|9|10|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|S|m|i|s|s|i|s|s|i|p|p|i|
|$A_i$|0|0|0|1|0|0|1|0|0|1|0|
|$B_i$|0|0|0|1|1|1|2|2|2|3|3|

であり、この問題では、各クエリについて、$B_{R-1}-B_{L-1}$が求める値ですから、計算量$O(1)$で計算ができ、十分に間に合います。
累積和の計算量は$O(N)$ですから、全体の計算量は$O(N+Q)$です。
## 解答例
```Python3:私の解答
n, q = map(int,input().split())
s = input()
b_n = [0]*n
for i in range(1,n) :
    if s[i] == s[i-1] :
        b_n[i] = b_n[i-1]+1
    else :
        b_n[i] = b_n[i-1]
for _ in range(q) :
    l, r = map(int,input().split())
    print(b_n[r-1]-b_n[l-1])
```
# D - Take ABC
https://atcoder.jp/contests/abc328/tasks/abc328_d
## 考え方
Pythonのリストは後ろの要素の削除を$O(1)$で実行可能ですから、
1. 出力する文字を格納する配列用意する
1. 文字列を最初から順番に格納して行く
1. 後ろから3文字が「ABC」なら、pop()を3回実行して'ABC'を削除する
1. 2.に戻る

を最後まで実行すれば十分に間に合います。
## 解答例
```Python3:私の解答
s = input()
ans = []
for i in range(len(s)) :
    ans.append(s[i])
    if len(ans) > 2 and "".join(ans[-3:]) == 'ABC' :
        for _ in range(3) :
            ans.pop()
print("".join(ans))
```

また、下記のように、removesuffixを利用してもギリギリ間に合いました。

```Python3:別解
s = input()
ans = ''
for i in range(len(s)) :
    ans += s[i]
    if len(ans) > 2 and ans[-3:] == 'ABC' :
        ans = ans.removesuffix('ABC')
print(ans)
```

# 参考文献
https://qiita.com/snhrhdt/items/2e514d4d6af983fcf6f0

https://note.nkmk.me/python-str-remove-strip/#_1

https://qiita.com/Yarakashi_Kikohshi/items/dc8f983d24698119bf71

https://qiita.com/drken/items/56a6b68edef8fc605821

# 感想
今回もDが解けてよかったです。Eが辺7つで全探索と気づいたときには遅かったです、、、

https://atcoder.jp/contests/abc328/tasks/abc328_e

年内入緑目指して頑張ります。