ABC328の解説記事 (PyPy3 ABCD)

はじめに

問題はこちら
初心者（灰色〜茶色）向けです。

A - Not Too Hard

考え方

問題の通り、配点リストのうち、X点以下のもののみを足せば良いです。
私はfilterを使用しました。

解答例

私の解答

n, x = map(int,input().split())
print(sum(filter(lambda s:s<=x,map(int, input().split()))))

B - 11/11

考え方

月が最大100か月、日数は1か月あたり最大100日のため、最大10000日分の日付しかありません。そのため、$i月j日$($i=1,2,\dots , N,\space j=1,2,\dots ,D_i$) が1種類の文字で構成されているかを確認すればよいです。具体的には下記のように解答しました。

1. $i$と$j$を文字列として結合する
2. 結合した文字列を1文字ずつのリストにする
3. リストをセット化して、セットの長さが1になるかをチェックする

解答例

私の解答

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

考え方

まず、各クエリについて$O(N)$以上の計算をすると、計算量が$O(NQ)$になってしまうため、とても間に合いません。
そのため、事前に全部のパターンを算出できるようにしておき、各クエリについては$O(1)$などで計算できるようにしておく必要があります。
また、$L$番目〜$R$番目の個数などを計算する際には、累積和がしばしば有効であることが多いです。
考え方としては、下記のようなイメージです。

\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番目の合計$とすれば、

L〜R番目の合計 
     =  累積和[R] - 累積和[L-1]   

と表せます。

$A_i \space\space(i = 0,1,2,\dots,n)$ を下記のような数列とします。

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)$を下記で表すと、

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)$です。

解答例

私の解答

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

考え方

Pythonのリストは後ろの要素の削除を$O(1)$で実行可能ですから、

1. 出力する文字を格納する配列用意する
2. 文字列を最初から順番に格納して行く
3. 後ろから3文字が「ABC」なら、pop()を3回実行して'ABC'を削除する
4. 2.に戻る

を最後まで実行すれば十分に間に合います。

解答例

私の解答

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を利用してもギリギリ間に合いました。

別解

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)

参考文献

感想

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

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