ABC250のA,B,C,D,E問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッター、マシュマロ、Discordサーバーまでお気軽にどうぞ！
Twitter: u2dayo
マシュマロ： https://marshmallow-qa.com/u2dayo
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
Discordサーバー（質問や記事の感想・リクエストなどどうぞ！） : https://discord.gg/jZ8pkPRRMT
よかったらLGTMや拡散していただけると喜びます！
目次
ABC250 まとめ
A問題『Adjacent Squares』
B問題『Enlarged Checker Board』
C問題『Adjacent Swaps』
D問題『250-like Number』
E問題『Prefix Equality』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC250 まとめ
全提出人数: 8842人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | A------- | 100 | 22分 | 5990(5788)位 |
| 400 | AB------ | 300 | 50分 | 4850(4648)位 |
| 600 | AB------ | 300 | 20分 | 3966(3764)位 |
| 800 | ABC----- | 600 | 53分 | 3011(2819)位 |
| 1000 | ABCD---- | 1000 | 89分 | 2188(2001)位 |
| 1200 | ABCD---- | 1000 | 53分 | 1546(1359)位 |
| 1400 | ABCDE--- | 1500 | 118分 | 1048(880)位 |
| 1600 | ABCDE--- | 1500 | 76分 | 702(544)位 |
| 1800 | ABCDE--- | 1500 | 47分 | 449(306)位 |
| 2000 | ABCDEF-- | 2000 | 91分 | 270(163)位 |
| 2200 | ABCDE-G- | 2100 | 95分 | 134(81)位 |
| 2400 | ABCDEFG- | 2600 | 113分 | 85(36)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F | G | Ex |
|---|---|---|---|---|---|---|---|---|---|
| 灰 | 2558 | 92.9 % | 69.0 % | 23.8 % | 8.6 % | 1.2 % | 0.0 % | 0.5 % | 0.0 % |
| 茶 | 1272 | 98.4 % | 92.8 % | 65.4 % | 36.1 % | 4.2 % | 0.2 % | 0.7 % | 0.0 % |
| 緑 | 995 | 97.1 % | 94.5 % | 88.3 % | 76.1 % | 15.7 % | 0.7 % | 1.6 % | 0.0 % |
| 水 | 641 | 97.2 % | 96.3 % | 95.6 % | 93.9 % | 53.5 % | 6.1 % | 4.1 % | 0.5 % |
| 青 | 373 | 97.3 % | 96.5 % | 96.8 % | 96.0 % | 80.7 % | 31.1 % | 15.8 % | 2.1 % |
| 黄 | 156 | 85.9 % | 83.3 % | 84.0 % | 86.5 % | 84.0 % | 60.9 % | 26.9 % | 6.4 % |
| 橙 | 30 | 80.0 % | 80.0 % | 80.0 % | 76.7 % | 66.7 % | 73.3 % | 46.7 % | 23.3 % |
| 赤 | 20 | 100.0 % | 95.0 % | 95.0 % | 95.0 % | 100.0 % | 95.0 % | 80.0 % | 70.0 % |
※表示レート、灰に初参加者は含めず
A問題『Adjacent Squares』
問題ページ：A - Adjacent Squares
灰コーダー正解率：92.9 %
茶コーダー正解率：98.4 %
緑コーダー正解率：97.1 %
入力
$H,W$ : 縦 $H$ 行 横 $W$ 列のマス目がある
$R,C$ : $(R,C)$ に辺で隣接するマスの個数を求める
考察
サンプルが親切でわかりやすいです。
$(R,C)$ に辺で隣接するマスは、基本的には上下左右の $4$ つですが、マス目の外にはマスがないので、辺がマス目の外側と接していると隣接するマスの数が減ります。
$(R,C)$ に辺で隣接する座標は、$(R+1,C),(R-1,C),(R,C+1),(R,C-1)$ の $4$ 箇所です。これらの座標が、マス目内であれば答えに $1$ 足して、マス目の外ならば足さなければいいです。
マス $(r,c)$ がマス目内である条件は、$1\le{r}\le{H}$ かつ $1\le{c}\le{W}$ であることです。
コード
H, W = map(int, input().split())
R, C = map(int, input().split())
ans = 0
for r, c in ((R + 1, C), (R - 1, C), (R, C + 1), (R, C - 1)):
if 1 <= r <= H and 1 <= c <= W:
ans += 1
print(ans)
B問題『Enlarged Checker Board』
問題ページ：B - Enlarged Checker Board
灰コーダー正解率：69.0 %
茶コーダー正解率：92.8 %
緑コーダー正解率：94.5 %
入力
$A,B$ : タイル $1$ つの大きさは 縦 $A$ 行 横 $B$ 列
$N$ : このタイルを縦 $N$ 行、横 $N$ 列、白黒交互に敷き詰める
考察
出力は $N\times{A}$ 行 $N\times{B}$ 列になります。
$N$ は最大で $10$ です。$N$ にかかわらず最初にタイルを $10\times{10}$ マスに敷き詰める場合の答えを作ったあと、必要な タイル $N\times{N}$ マスの部分だけを出力すればいいです。
手順
$10\times{10}$ の答えを作るのは、以下の方法が簡単です。
- 左のタイルが白ではじまる、タイル $1\times10$ マスを並べる
- その下に、左のタイルが黒ではじまる $1\times{10}$ マスをくっつけて、$2\times{10}$ マスにする
- $2\times{10}$ マスを $5$ 個縦に並べて $10\times{10}$ にする
コード
N, A, B = map(int, input().split())
grid = []
for _ in range(5):
for row in range(A): # 1,3,5,7,9行目のタイル、タイルは縦A行なのでA回ループ
grid.append(("." * B + "#" * B) * 5) # 白から始まる
for row in range(A): # 2,4,6,8,10行目のタイル
grid.append(("#" * B + "." * B) * 5)
# 答えはA * N行 B * N列です
for row in range(A * N):
print(grid[row][:B * N])
C問題『Adjacent Swaps』
問題ページ：C - Adjacent Swaps
灰コーダー正解率：23.8 %
茶コーダー正解率：65.4 %
緑コーダー正解率：88.3 %
入力
$N$ : $1$ から $N$ の数字が書かれた $N$ 個のボールが左右一列に並んでいて、はじめ左から $i$ 番目のボールには $i$ が書いてある
$Q$ : 操作の回数
$x_i$ : $i$ 回目の操作では、整数 $x_i$ が書かれたボールを右隣のボールと入れ替える。ただし、$x_i$ が書かれたボールが列の右端であれば、代わりに左隣のボールと入れ替える
考察
操作自体は簡単ですが、整数 $x_i$ の書かれたボールがどこにあるかわからないと、操作を行えません。毎回 index()メソッドや、forループなどを使って、どこに $x_i$ が書かれたボールがあるか探すと、一度の探索の計算量が $O(N)$ なので、全体では $O(NQ)$ となりTLEです。
そこで、$1$ から $N$ の整数 $x$ それぞれについて、『$x$ が書かれたボールがリストの何番目にあるか？』を記録したリストも別途用意します。こうすることで、整数 $x_i$ が書かれた場所を $O(1)$ で特定できます。操作では、ボールの並び方とともに、入れ替えたボールが何番目にあるかも一緒に更新します。
コード
def main():
N, Q = map(int, input().split())
A = list(range(N + 1)) # 1はじまりにするためにN+1の長さで作る、A[0]は使わない
idx = list(range(N + 1)) # iの書かれたボールははじめi番目にある
for _ in range(Q):
x = int(input())
fi = idx[x] # xの位置
si = fi + 1 if fi != N else fi - 1 # 通常は右隣のボールと入れ替えるが、右端なら左隣と入れ替える
y = A[si] # 入れ替えるボールに書かれた数
A[fi], A[si] = A[si], A[fi] # 入れ替える
idx[x] = si # xはsi、yはfiに移動
idx[y] = fi
print(*A[1:]) # A[0]を出力しないよう注意
if __name__ == '__main__':
main()
D問題『250-like Number』
問題ページ：D - 250-like Number
灰コーダー正解率：8.6 %
茶コーダー正解率：36.1 %
緑コーダー正解率：76.1 %
入力
$N$ : $1$ 以上 $10^{18}$ 以下の整数
考察
素数 $p\lt{q}$ を用いて、$k=p\times{q^3}$ となる $N$ 以下の整数がいくつあるか答える問題です。$p,q$ は素数なので、異なる $p,q$ の組で、同じ $k$ になることはありません。（素因数分解の一意性）
$q$ を $3$ 乗しますから、$q$ は大きくても $\sqrt[3]{10^{18}}=10^6$ よりは小さくなります。
$q$ を固定して考えます。ある素数 $p$ で $p\times{q^3}\gt{N}$ となった場合、それより大きいすべての素数 $r$ で $r\times{q^3}\gt{N}$ です。したがって、$p$ を 小さい順に $2$ から調べていって、 $p\times{q^3}\gt{N}$ となったら、その $q$ での探索を打ち切っていいです。
素数列挙
$2$ 以上 $10^6$ 以下の素数のリストが必要なので、素数列挙を行います。$K$ 以下の素数を全列挙するのは、『エラトステネスのふるい』というアルゴリズムを使って、$O(K\log\log{K})$ で高速に行えます。
答えは全探索できるほど小さい
サンプル $3$ を見ると、入力 $123456789012345$ （$10^{14}$ 程度）に対して、答えは $226863$ しかありません。$N=10^{18}$ でも全探索が可能な気がするので、試しに二重ループの全探索コードを書いてみます。（$q$ を固定し、$p$ を小さい順に調べ、条件を満たさなくなったら打ち切る）
すると、答えは $11871859$ しかなく、全探索でも間に合うことがわかりました。
コード
from collections import deque
def enum_primes(n):
prime_flag = [1] * (n + 1)
prime_flag[0] = 0
prime_flag[1] = 0
i = 2
while i * i <= n:
if prime_flag[i]:
for j in range(2 * i, n + 1, i):
prime_flag[j] = 0
i += 1
return [i for i in range(n + 1) if prime_flag[i]]
def main():
N = int(input())
ans = 0
primes = enum_primes(10 ** 6 + 5) # 素数が小さい順に入っています
M = len(primes)
for i in range(M):
t = primes[i] ** 3 # 重い t = q ** 3を先に計算します
for j in range(i): # primes[i]未満の素数を小さい順に全探索
if t * primes[j] > N:
break
ans += 1
print(ans)
if __name__ == '__main__':
main()
E問題『Prefix Equality』
問題ページ：E - Prefix Equality
灰コーダー正解率：1.2 %
茶コーダー正解率：4.2 %
緑コーダー正解率：15.7 %
考察
公式ユーザ解説の方法です
この問題の解説は、こちらのhamaruさんの解法を解説したものです。
余りにも賢くて感動してしまいました。私が考えた解法ではありません。
解説
各数字を、$A$ ではじめて登場する順に数字を振り替えます。 ただし、$A$ に出現せず $B$ に出現する数字は適当に巨大な数字を割り当てておきます。
$A$ の先頭 $x_i$ 項に含まれる要素の種類数が $k_{x_i}$ のとき、集合は $\{1,2,\dots,k_t\}$ となります。この集合と $B$ の先頭 $y_i$ 項が一致するのは
- $B$ の先頭 $y_i$ 項に含まれる要素の種類数が $k_{x_i}$
- $B$ の先頭 $y_i$ 項に含まれる要素の最大値が $k_{x_i}$
であるときです。
したがって、数字を $A$ での登場順に振り替えたあと、以下の $3$ つを事前に計算すれば、各クエリに $O(1)$ で答えられます。
- $A$ の先頭 $i$ 項に含まれる要素の種類数
- $B$ の先頭 $i$ 項に含まれる要素の種類数
- $B$ の先頭 $i$ 項に含まれる要素の最大値
コード
from collections import defaultdict
def main():
def calc_cnt():
A_cnt = [0] * N
D = defaultdict(lambda: 1 << 60)
n = 0
for i, x in enumerate(A):
if not x in D:
n += 1
D[x] = n
A_cnt[i] = n
B_cnt = [0] * N
B_max = [0] * N
m = 0
S = set()
for i, x in enumerate(B):
S.add(x)
m = max(m, D[x])
B_cnt[i] = len(S)
B_max[i] = m
return A_cnt, B_cnt, B_max
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A_cnt, B_cnt, B_max = calc_cnt()
Q = int(input())
for _ in range(Q):
x, y = map(int, input().split())
x -= 1
y -= 1
print("Yes" if A_cnt[x] == B_cnt[y] == B_max[y] else "No")
if __name__ == '__main__':
main()
おまけ: ハッシュを使う確率的アルゴリズム
Zobrist Hashingという、ハッシュで集合の状態を表現する手法でも、この問題を解くことができます。
ただし、確実に正しい答えを求められるアルゴリズムではなく、高確率で正しい答えを求められる確率的アルゴリズムです。
とはいえ、適切にアルゴリズムを設計すれば、誤った答えを返す確率は無視できるほど小さくなります。 実質的には確実に正しい答えを返すアルゴリズムとみなして構いません。
やり方
各整数に、$1$ 以上 $2^{63}$ 未満 の整数をランダムに割り当てます。これがハッシュです。
異なる整数に重複するハッシュが割り当てられると困りますが、ハッシュの種類 $2^{63}-1$ 種類に対し、この問題で出る整数は最大 $2\times{10^5}$ 種類しかありません。特別配慮せずとも、重複することはまずありえません。
次に、配列 $A,B$ それぞれ先頭から累積xorを取ります。ただし、各リストで $2$ 回目以降に登場する整数は $0$ に置き換えます。（集合に含まれていることを表したいので、xorは一度だけ取ります、二回取ると $0$ に戻ってしまいます）
集合が一致する場合、累積xorの値は必ず一致します。同じ集合であれば、累積xorの値は同じになるからです。
逆に、累積xorの値が一致しない場合、集合は必ず一致しません。
集合が一致しないのに累積xorが一致する誤判定は起こりえます。ただし、これは無視できるほど小さい確率です。（詳しい確率は私にはわかりません、ハッシュのbit長を小さくすると確率は高くなります）
下のコードでは、念のためランダムに割り当てるハッシュ値を変えて判定を $2$ 回行っていますが、$1$ 回でも現実的には失敗しないと思います。
from collections import defaultdict
from itertools import accumulate
from operator import xor
from random import randint
JUDGE_NUM = 2 # 判定回数（1回でもいいと思う）
def main():
def gen_hash():
hash_dict = defaultdict(lambda: randint(1, (1 << 63) - 1))
Ax, Bx = [0] * N, [0] * N
AS, BS = set(), set() # 既に出た値を管理
for i, (a, b) in enumerate(zip(A, B)):
if a not in AS: # はじめて出るときだけxorをとる
Ax[i] = hash_dict[a]
AS.add(a)
if b not in BS:
Bx[i] = hash_dict[b]
BS.add(b)
A_acc = list(accumulate(Ax, xor)) # 累積和と同じ要領で累積xorをとる
B_acc = list(accumulate(Bx, xor))
return A_acc, B_acc
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
Q = int(input())
query = [list(map(int, input().split())) for _ in range(Q)]
ans = [0] * Q # 判定を2回行い、2回とも一致するならYesにする
for _ in range(JUDGE_NUM):
A_acc, B_acc = gen_hash()
for i, (x, y) in enumerate(query):
ans[i] += 1 if A_acc[x - 1] == B_acc[y - 1] else 0 # Aの先頭x項、Bの先頭y項の累積xorが一致するか
for x in ans:
print("Yes" if x == JUDGE_NUM else "No")
if __name__ == '__main__':
main()