AtCoder Beginner Contest 347の解説記事です。
ABC347 A – Divisible
問題
問題文の要約は以下の通りです。
問題の要約
正整数 \(N\), \(K\) 及び長さ \(N\) の数列 \(A = (A_1, A_2, \cdots , A_N)\) が与えられます。\(A\) に含まれる要素のうち、\(K\) の倍数であるもののみを全て取り出し、それらを \(K\) で割って出力せよ。
解説
与えられた整数列の各要素について、その要素がKで割り切れるかどうかを確認し、割り切れる場合、その要素をKで割った商を出力する。
解説
まず入力を受け取ります。
# 入力
N,K=map(int,input().split())
A=list(map(int,input().split()))リストAの各要素がKで割り切れるとき、Kで割った商を末尾に空白をつけて出力します。
# リストAの各要素に対して処理を行う
for i in range(N):
# 要素がKで割り切れるとき、Kで割った商を出力し、末尾に空白をつける
if A[i] % K == 0:
print(A[i] // K, end=' ')解答
# 入力
N,K=map(int,input().split())
A=list(map(int,input().split()))
# リストAの各要素に対して処理を行う
for i in range(N):
# 要素がKで割り切れるとき、Kで割った商を出力し、末尾に空白をつける
if A[i] % K == 0:
print(A[i] // K, end=' ')ABC347 B – Substring
問題
問題文の要約は以下の通りです。
問題の要約
英小文字からなる文字列 \(S\) が与えられます。 \(S\) の空でない部分文字列は何種類存在するか求めよ。
解説
与えられた文字列の全ての部分文字列を生成し、セットに追加することでユニークなものだけを保持し、それらの総数を求める。
解説
入力を受け取ります。
# 入力
S = input()部分文字列を格納するためのセットansを用意します。
i文字目からj文字目の部分文字列はS[i:j]で求められるのでこれをansに追加ans.add(S[i:j])して総数を求めます。
# 部分文字列を格納するためのセット
ans = set()
# i文字目からj文字目の部分文字列をセットに追加する
for i in range(len(S)):
for j in range(i + 1, len(S) + 1):
ans.add(S[i:j])
# ユニークな部分文字列の数を出力する
print(len(ans))解答
# 入力
S = input()
# 部分文字列を格納するためのセット
ans = set()
# i文字目からj文字目の部分文字列をセットに追加する
for i in range(len(S)):
for j in range(i + 1, len(S) + 1):
ans.add(S[i:j])
# ユニークな部分文字列の数を出力する
print(len(ans))ABC347 C – Ideal Holidays
問題
問題文の要約は以下の通りです。
問題の要約
1週間が \(A+B\) 日からなり、1 日目から \(A\) 日目が休日で、 \(A+1\) 日目から \(A+B\) 日目が平日とします。また、\(N\) 個の予定があり、 \(i\) 番目の予定は今日から \(D_i\) 日後です。今日が1週間の何日目かわからないとき、\(N\) 個の予定が全て休日である可能性があるかを判定せよ。
解説
予定をソートし、隣接する予定の間隔が \(B\) よりも大きいかどうかを確認する。 \(B\) より大きければ、その予定は平日をまたがっており、予定は全て休日になる。
解説
入力を受け取ります。
# 入力
N, A, B = map(int, input().split())入力を \(A+B\) で割った余りに変換して、リストに格納、ソートを行います。
また、最後の日付と最初の日付の差を求めるために、最初の日付に \(A+B\) を足してリストの最後に追加します。
# 入力
N, A, B = map(int, input().split())
# 入力をA+B で割った余りに変換して、リストに格納
D = list(map(lambda d: int(d) % (A + B), input().split()))
# 日付をソート
D.sort()
# 最後の日付と最初の日付の差を求めるために、最初の日付に A+B を足してリストの最後に追加
D.append(D[0] + A + B)隣接する予定の間隔が \(B\) よりも大きいかどうかを確認する。 \(B\) より大きければ、その予定は平日をまたがっており、予定は全て休日になる。
# 隣接する予定の間隔が B よりも大きいかどうかを確認する。
# B より大きければ、その予定は平日をまたがっており、全て休日になる。
for i in range(N):
if D[i + 1] - D[i] > B:
print("Yes")
exit()
print("No")解答
# 入力
N, A, B = map(int, input().split())
# 入力をA+B で割った余りに変換して、リストに格納
D = list(map(lambda d: int(d) % (A + B), input().split()))
# 日付をソート
D.sort()
# 最後の日付と最初の日付の差を求めるために、最初の日付に A+B を足してリストの最後に追加
D.append(D[0] + A + B)
# 隣接する予定の間隔が B よりも大きいかどうかを確認する。
# B より大きければ、その予定は平日にまたがっており、全て休日にはならない。
for i in range(N):
if D[i + 1] - D[i] > B:
print("Yes")
exit()
print("No")ABC347 D – Popcount and XOR
問題
解説
\(X, Y, C\) を2進法で表したときの各ビットが0になるか、１になるかを考える。
解説
\(X, Y, C\) を2進法で表したときの各ビットが0になるか、１になるかを考えるために変数を用意します。
# n00: Cのビット：0 Xのビット：0 Yのビット：0
# n01: Cのビット：1 Xのビット：0 Yのビット：1
# n10: Cのビット：1 Xのビット：1 Yのビット：0
# n11: Cのビット：0 Xのビット：1 Yのビット：1解答
# 入力
a, b, C = map(int, input().split())
# Cを2進法で表したときの1の数
c = bin(C).count('1')
# n00: Cのビット：0 Xのビット：0 Yのビット：0
# n01: Cのビット：1 Xのビット：0 Yのビット：1
# n10: Cのビット：1 Xのビット：1 Yのビット：0
# n11: Cのビット：0 Xのビット：1 Yのビット：1
for n00 in range(60 - c + 1):
for n01 in range(c + 1):
n10 = c - n01
n11 = 60 - c - n00
# XとYが問題の条件を満たしているか
if n10 + n11 != a or n01 + n11 != b:
continue
# 条件を満たすX, Yを求める
X, Y = 0, 0
for i in range(60):
# Cのi番目のビットが1かどうか
bit = (C >> i) & 1
# Cのi番目のビットが1の場合
if bit:
if n10 > 0:
# Xのi番目を1に設定
X |= 1 << i
n10 -= 1
else:
# Yのi番目を1に設定
Y |= 1 << i
# Cのi番目のビットが0の場合
else:
if n11 > 0:
# XとYのi番目を1に設定
X |= 1 << i
Y |= 1 << i
n11 -= 1
# 条件を満たすXとYを見つけた場合、X, Yを出力
print(X, Y)
exit()
# 条件を満たすペアが見つからなかった場合、-1を出力
print(-1)ABC347 E – Set Add Query
問題
問題文の要約は以下の通りです。
問題の要約
全ての要素が0で初期化された長さ \(N\) の整数列 \(A = (A_1, A_2, \cdots , A_N)\) があります。また、はじめは空である集合 \(S\) があります。
以下の \(Q\) 個のクエリを順に行います。全てのクエリを処理した後の数列 \(A\) の各要素の値を求めよ。
\(i\) 番目のクエリは以下の形式です。
整数 \(x_i\) が与えられる。整数 \(x_i\) が \(S\) に含まれる場合、 \(S\) から \(x_i\) を削除する。そうでない場合、\(S\) に \(x_i\) を追加する。次に、\(j = 1, 2, \cdots , N\) について、\(j \in S\) ならば \(A_j\) に \(|S|\) を加算する。
解説
要素数に対す累積和を用いる。
解説
- 各クエリに対して、次の操作を行います：
- クエリで指定された要素
xがsetSに既に存在する場合、xをsetSから削除し、xの値（ans[x]）に、その時点までのsetの累積和を加算します。 - クエリで指定された要素
xがsetSに存在しない場合、xをsetSに追加し、xの値（ans[x]）から、その時点までの累積和を減算します。 - 各クエリの処理後、set
Sの要素数を累積和に加えます。
- クエリで指定された要素
- 全てのクエリを処理した後、setに残っている各要素に対して最終的な値を更新します。
- 最後に、
1からNまでの各要素について計算された結果を出力します。
解答
from collections import defaultdict
# 入力
N, Q = map(int, input().split())
x=list(map(int,input().split()))
# 現在の要素を保持するセット
S = set()
# 累積和
sum = 0
# 各要素に対する答え
ans = defaultdict(int)
for i in range(Q):
# 要素がセットに含まれているかどうかを確認
if x[i] in S:
S.remove(x[i]) # 要素があれば削除
ans[x[i]] += sum # それまでの総和を加算
else:
S.add(x[i]) # 要素がなければ追加
ans[x[i]] -= sum # それまでの総和を減算
sum += len(S) # セットのサイズ分だけ総和を増やす
# 残っている要素について最終的な値を更新
for x[i] in S:
ans[x[i]] += sum
# 結果を出力
for i in range(1, N + 1):
print(ans[i], end=' ' if i != N else '\n')