はじめに
これは Atcoder Beginners Constest372 の参加振り返り記事です。
自分の提出したコードと解説をもとに C 問題までの振り返りをしたいと思います。
個人の備忘録的なものです。以下、各問題ごとにまとめます。
A 問題
問題文
英小文字および . からなる文字列 $S$ が与えられます。$S$ から . を全て削除した文字列を求めてください。
制約
- $S$ は英小文字および . からなる長さ $1$ 以上 $100$ 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
$S$
出力
$S$ から . を全て削除した文字列を出力せよ。
解答
S = input()
ans = ""
for s in S:
if s == ".":
continue
else:
ans += s
print(ans)
ans というから文字列を用意します。$S$の文字列を 1 つずつ for 文で取り出して . 以外の文字の場合は ans の末尾に連結させます。
書いてから思いましたが、s が . の時の処理は結局何もしないので不要ですね。
解説にあるコードはまさにそんな感じでした。
S = input()
T = ""
for c in S:
if c != '.':
T += c
print(T)
B 問題
問題文
正整数 $M$ が与えられます。以下の条件を全て満たす正整数 $N$ と非負整数列 $A=(A_1,A_2,\ldots,A_N)$ を一つ求めてください。
- $1\le N\le 20$
- $0\le A_i\le 10$ $(1\le i\le N)$
- $\displaystyle \sum_{i=1}^N 3^{A_i}=M$
ただし、制約下では条件を満たす $N$ と $A$ の組が必ず存在することが証明できます。
制約
- $1\le M\le 10^5$
入力
入力は以下の形式で標準入力から与えられる。
$M$
出力
以下の形式で条件を満たす $N$ と $A$ を出力せよ。
$N$
$A_1$ $A_2$ $\ldots$ $A_N$
なお、条件を満たす $N$ と $A$ の組が複数存在する場合は、どれを出力しても正答となる。
解答
def pow(M, count):
if M-3**count < 0:
return count-1
else:
count += 1
return pow(M, count)
M = int(input())
A = []
while True:
if M <= 0:
break
a = pow(M, 0)
A.append(a)
M -= 3**a
print(len(A))
print(*A)
最初に pow という関数を定義し、これを利用して条件を満たす非負整数数列 A を作成するようにしました。
これもいろいろ考えてしまいましたが、よくよく考えてみると$M$を 3 進数表記にしてあげることで簡単に解けたようです。
与えられた 10 進数を 3 進数に変換するためには 3 で割った余りを逆順に並べればよいので解説のようなコードが簡潔ですね。
M = int(input())
A = []
for k in range(11):
A += [k] * (M % 3)
M //= 3
print(len(A))
print(*A)
自分はここまでで 20~30 分ほどかかってしまいました。。。
C 問題
問題文
長さ $N$ の文字列 $S$ が与えられます。クエリが $Q$ 個与えられるので、順番に処理してください。
$i$ 番目のクエリは以下の通りです。
- 整数 $X_i$ と文字 $C_i$ が与えられるので、 $S$ の $X_i$ 番目の文字を $C_i$ に置き換える。その後、 $S$ に文字列 ABC が部分文字列として何箇所含まれるかを出力する。
ここで、 $S$ の 部分文字列 とは、$S$ の先頭から $0$ 文字以上、末尾から $0$ 文字以上削除して得られる文字列のことをいいます。例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。
制約
- $3\le N\le 2\times 10^5$
- $1\le Q\le 2\times 10^5$
- $S$ は英大文字からなる長さ $N$ の文字列
- $1\le X_i\le N$
- $C_i$ は英大文字
入力
入力は以下の形式で標準入力から与えられる。
$N$ $Q$
$S$
$X_1$ $C_1$
$X_2$ $C_2$
$\vdots$
$X_Q$ $C_Q$
出力
$Q$ 行出力せよ。$i$ 行目 $(1\le i\le Q)$ には $i$ 番目のクエリに対する答えを出力せよ。
解答
最初は各クエリ実行後に S に含まれる A の index から 3 文字を確認して"ABC"に一致するかどうか確認するプログラムを書いたら TLE になりました。
クエリを回すための for 文の中で、さらに A の index を全て探索するための for 文を回していたのでそうりゃそうでしょうって感じですね。。。
N, Q = map(int, input().split())
S = list(input())
index_A = []
for i, s in enumerate(S):
if s == "A":
index_A.append(i)
for i in range(Q):
#print(index_A)
X, C = input().split()
X = int(X)
if S[X-1] == "A":
index_A.remove(X-1)
S[X-1] = C
if C == "A":
index_A.append(X-1)
ans = 0
for i in index_A:
if "".join(S[i:i+3]) == "ABC":
ans += 1
print(ans)
というわけで考え方を変更します。
実は、クエリが実行された確認しなければならない場所は X-2 番目から X 番目までの文字が先頭になる場合のみだということに気づきます。
それを踏まえてコードを書き直したものがこちらです。
N, Q = map(int, input().split())
S = list(input())
index_A = set()
index_abc = set()
for i, s in enumerate(S):
if s == "A":
index_A.add(i)
if "".join(S[i:i+3]) == "ABC":
index_abc.add(i)
for i in range(Q):
# print(index_A)
X, C = input().split()
X = int(X)
S[X-1] = C
for k in range(X-3, X+2):
if "".join(S[k:k+3]) == "ABC":
index_abc.add(k)
elif k in index_abc:
index_abc.remove(k)
print(len(index_abc))
このようにすることで C 問題を AC することができました。
この記事を夏期ながら思いましたが index_A は不要ですね。。。
他にもいろいろと団長なコードが多いのでもう少しスマートに書くことを意識したいと思います。。。
解説のコードはこちら。↓
N, Q = map(int, input().split())
S = list(input())
ans = 0
for i in range(N - 2):
if S[i] == "A" and S[i + 1] == "B" and S[i + 2] == "C":
ans += 1
for _ in range(Q):
t, c = input().split()
t = int(t) - 1
for k in range(3):
idx = t - k
if 0 <= idx and idx + 2 < N:
if S[idx] == "A" and S[idx + 1] == "B" and S[idx + 2] == "C":
ans -= 1
S[t] = c
for k in range(3):
idx = t - k
if 0 <= idx and idx + 2 < N:
if S[idx] == "A" and S[idx + 1] == "B" and S[idx + 2] == "C":
ans += 1
print(ans)
C 問題が解き終わった時点で残り 20 分ほどだったので解ける自信はありませんでしたが、D 問題へ行きました。
結局はが経たなくてタイムオーバーでしたが。
最後に
今回は ABC372 の振り返りでした。やはり、 C 問題まではもう少しスムーズに解答して D 問題以降の問題にもう少し時間を割きたいところです。特に、B、C 問題は回答することができてもコードに落としこむまでの時間が長かったり、もっと簡単に解決することができる問題だったと思うので改めて自分の中でも整理をしようと思いました。また来週以降の ABC 頑張ります！