ABC347のA~E問題をpythonで解説していきます。個人的にはC問題が難しかったです。
A - Divisible
問題
正整数 $N,K$ 及び長さ $N$ の数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。
$A$ に含まれる要素のうち、$K$ の倍数であるもののみを全て取り出し、それらを $K$ で割って出力してください。
考察
問題文の通り実装するだけ。
コード
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = []
for a in A:
if a % K == 0:
ans.append(a // K)
print(*ans)
B - Substring
問題
英小文字からなる文字列 $S$ が与えられます。$S$ の空でない部分文字列は何種類ありますか？
ただし、部分文字列とは連続する部分列のことを指します。例えば、xxx は yxxxy の部分文字列ですが、xxyxx の部分文字列ではありません。
考察
制約が緩いため、部分文字列を全列挙してset(重複を含まない性質あり)へ代入、その長さを表示すればよい。
コード
S = input()
candi = set()
LS = len(S)
for L in range(1, LS + 1): # 部分文字列の長さ
for i in range(LS - L + 1): # 部分文字列の開始位置
candi.add(S[i : i + L])
print(len(candi))
C - Ideal Holidays
問題
AtCoder 王国の $1$ 週間は $A+B$ 日からなり、$1$ 日目から $A$ 日目が休日で、$A+1$ 日目から $A+B$ 日目が平日です。
高橋くんは $N$ 個の予定があり、$i$ 番目の予定は今日から $D_i$ 日後です。
高橋くんは今日が $1$ 週間の何日目かを忘れてしまいました。高橋くんの $N$ 個の予定が全て休日である可能性があるかを判定してください。
考察
まず、1週間単位で見ればよいので、$D_i$すべてについて$A+B$で割ったあまりに変換する。その後、条件を満たすような場合は、下図の2パターンしか考えられない。よって、これを実装する。
コード
N, A, B = map(int, input().split())
D = list(map(int, input().split()))
D = [d % (A + B) for d in D]
D.sort()
for i in range(N - 1):
if D[i + 1] - D[i] + 1 - 2 >= B:
print("Yes")
exit()
if D[-1] - D[0] + 1 <= A:
print("Yes")
else:
print("No")
D - Popcount and XOR
問題
非負整数 $a,b,C$ が与えられます。 次の $5$ つの条件をすべて満たす非負整数の組 $(X,Y)$ が存在するか判定し、存在するならひとつ出力してください。
- $0 \leq X < 2^{60}$
- $0 \leq Y < 2^{60}$
- $\operatorname{popcount}(X)=a$
- $\operatorname{popcount}(Y)=b$
- $X\oplus Y=C$
ただし、$\oplus$ はビットごとの排他的論理和を表します。
条件を満たす $(X,Y)$ が複数存在する場合、どれを出力しても構いません。
popcount とは？
非負整数 $x$ について $x$ の popcount とは、$x$ を $2$ 進法で表記したときの $1$ の個数です。 より厳密には、非負整数 $x$ について $x=\sum_{i=0}^\infty b_i2^i\ (b_i\in\lbrace0,1\rbrace)$ が成り立っているとき $\operatorname{popcount}(x)=\sum_{i=0}^\infty b_i$ です。
例えば、$13$ を $2$ 進法で表記すると $1101$ なので、 $\operatorname{popcount}(13)=3$ となります。
考察
$\operatorname{popcount}(C)=c$とする。
まず、排他的論理和の性質から、$C$でビットが1となっているときは、$X$,$Y$のどちらかのビットが1、もう一方が0となっていなければならない。また、ビットが0となっているときは、$X$,$Y$のどちらのビットも1か0になっていなければならない。したがって、a+b<cとなっていたり、(a+b-c)%2!=0であったりする場合は、条件を満たす$X$,$Y$が存在しない。また、$X$と$Y$がどちらのビットも1となるようなペアの個数をdとすると、c+d>60となる場合も条件を満たすものは存在しないことがわかる。
よって、$C$のビットを一つずつ見ていき、1だったならaとbどちらか大きい方のビットを1にする、0だったならa+b>cかつaもbも0でない場合に両方のビットを1とする、という風に実装すればよい。最後に、a>0だったりb>0のように、使い切れなかった場合は条件を満たせないことに注意。
コード
a, b, C = map(int, input().split())
c = 0
for i in range(60):
if (C >> i) & 1:
c += 1
d = (a + b - c) // 2
if a + b - c < 0 or (a + b - c) % 2 != 0 or c + d > 60:
print(-1)
exit()
X = 0
Y = 0
for i in range(60):
if (C >> i) & 1:
if a > b:
a -= 1
X += 1 << i
else:
b -= 1
Y += 1 << i
c -= 1
else:
if a + b > c and a * b != 0:
a -= 1
b -= 1
X += 1 << i
Y += 1 << i
if a > 0 or b > 0:
print(-1)
exit()
print(X, Y)
E - Set Add Query
問題
全ての要素が $0$ で初期化された長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ があります。また、集合 $S$ があります。はじめ $S$ は空です。
以下の $Q$ 個のクエリを順に行います。$Q$ 個のクエリを全て処理した後の数列 $A$ の各要素の値を求めてください。 $i$ 番目のクエリは以下の形式です。
- 整数 $x_i$ が与えられる。整数 $x_i$ が $S$ に含まれる場合、$S$ から $x_i$ を削除する。そうでない場合、$S$ に $x_i$ を追加する。次に、$j=1,2,\ldots,N$ について、$j\in S$ ならば $A_j$ に $|S|$ を加算する。
なお、$|S|$ は集合 $S$ の要素数を意味します。例えば $S=\lbrace 3,4,7\rbrace$ のとき、$|S|=3$ です。
考察
$|S|$の各ターンの値がわかっていれば、例えば3~10ターンの間$x$が$S$に含まれていた場合、累積和を用いて$O(1)$でこの間に$x$に加算された数が計算できる(今回の実装だとacc[11]-acc[3]で計算できる)。
よって、各ターンの$|S|$の長さをset等で求めることと、ある数$x$がどのターンで$S$に追加され、どのターンで$S$から削除されるかを記録することをすればよい。
コード
N, Q = map(int, input().split())
X = list(map(int, input().split()))
LS = []
L = [[] for _ in range(N + 1)]
R = [[] for _ in range(N + 1)]
S = set()
for turn in range(Q):
x = X[turn]
if x in S:
S.remove(x)
R[x].append(turn)
else:
S.add(x)
L[x].append(turn)
LS.append(len(S))
acc = [0]
for ls in LS:
acc.append(acc[-1] + ls)
ans = [0] * (N + 1)
for x in range(1, N + 1):
for i in range(len(R[x])):
l, r = L[x][i], R[x][i]
ans[x] += acc[r] - acc[l]
if len(R[x]) < len(L[x]):
l = L[x][-1]
ans[x] += acc[-1] - acc[l]
print(*ans[1:])