ABC254の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や拡散していただけると喜びます!
目次
ABC254 まとめ
A問題『Last Two Digits』
B問題『Practical Computing』
C問題『K Swap』
D問題『Together Square』
E問題『Small d and k』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC254 まとめ
全提出人数: 10002人
パフォーマンス
パフォ | AC | 点数 | 時間 | 順位(Rated内) |
---|---|---|---|---|
200 | AB------ | 300 | 40分 | 6815(6608)位 |
400 | AB------ | 300 | 16分 | 5487(5280)位 |
600 | AB------ | 300 | 4分 | 4468(4261)位 |
800 | ABC----- | 600 | 49分 | 3383(3185)位 |
1000 | ABC----- | 600 | 20分 | 2444(2256)位 |
1200 | ABC-E--- | 1100 | 110分 | 1691(1506)位 |
1400 | ABCDE--- | 1500 | 95分 | 1150(972)位 |
1600 | ABCDE--- | 1500 | 55分 | 779(605)位 |
1800 | ABCDEF-- | 2000 | 97分 | 517(352)位 |
2000 | ABCDEF-- | 2000 | 67分 | 328(188)位 |
2200 | ABCDEF-- | 2000 | 49分 | 205(89)位 |
2400 | ABCDEF-- | 2000 | 34分 | 121(42)位 |
色別の正解率
色 | 人数 | A | B | C | D | E | F | G | Ex |
---|---|---|---|---|---|---|---|---|---|
灰 | 3577 | 98.0 % | 83.6 % | 20.6 % | 3.0 % | 2.1 % | 0.3 % | 0.0 % | 0.0 % |
茶 | 1622 | 98.7 % | 98.1 % | 64.9 % | 12.6 % | 8.5 % | 0.7 % | 0.1 % | 0.0 % |
緑 | 1268 | 98.1 % | 97.5 % | 88.1 % | 32.6 % | 33.7 % | 2.7 % | 0.0 % | 0.2 % |
水 | 687 | 97.8 % | 97.7 % | 96.1 % | 68.3 % | 74.4 % | 18.6 % | 0.0 % | 0.9 % |
青 | 418 | 96.4 % | 95.9 % | 95.7 % | 88.0 % | 90.9 % | 62.9 % | 1.0 % | 6.7 % |
黄 | 159 | 85.5 % | 85.5 % | 85.5 % | 83.7 % | 83.7 % | 76.1 % | 3.8 % | 18.2 % |
橙 | 35 | 82.9 % | 82.9 % | 82.9 % | 82.9 % | 82.9 % | 85.7 % | 22.9 % | 48.6 % |
赤 | 22 | 90.9 % | 90.9 % | 86.4 % | 90.9 % | 90.9 % | 90.9 % | 54.5 % | 72.7 % |
※表示レート、灰に初参加者は含めず
A問題『Last Two Digits』
問題ページ:A - Last Two Digits
灰コーダー正解率:98.0 %
茶コーダー正解率:98.7 %
緑コーダー正解率:98.1 %
入力
$N$ : $3$ 桁の整数
考察
$N$ を int(input())
で整数型として受け取るより、input()
で文字列型として受け取ったほうが楽です。
コード
N[0]
が 百の位、N[1]
が十の位、N[2]
が一の位ですから、N[1]
とN[2]
を出力すればいいです。
N = input() # 文字列で受け取りましょう
print(N[1:])
整数で受け取った場合
下二桁は $100$ で割った余りで得られますが、十の位が $0$ のとき困るので、結局文字列に戻して、$2$ 桁の $0$ 埋めをする羽目になります。
N = int(input())
print(f"{N % 100:02d}")
B問題『Practical Computing』
問題ページ:B - Practical Computing
灰コーダー正解率:83.6 %
茶コーダー正解率:98.1 %
緑コーダー正解率:97.5 %
入力
$N$ : $1$ 以上 $30$ 以下の整数
考察
深く考えずに、書いてあるとおりに丁寧に実装しましょう。
ちなみにこれは、 動的計画法(DP) である関数の値を求める問題です。
コード
N = int(input())
A = [[0] * (i + 1) for i in range(N)]
for i in range(N):
for j in range(i + 1):
if j == 0 or j == i:
A[i][j] = 1
else:
A[i][j] = A[i - 1][j - 1] + A[i - 1][j]
for i in range(N):
print(*A[i])
補足
この問題で求めた数列たちは、ある関数の値です。
サンプル $2$ の出力を眺めてみましょう。もしかしたら、見覚えのある方もいるかもしれません。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
これは『パスカルの三角形』と呼ばれるものです。$i$ 行目の $j$ 列目は、${}_i\mathrm{C}_j$ と等しいです。($i,j$ は $0$ から数え始めます)
問題では、$a_{i,j}=a_{i-1,j-1}+a_{i-1,j}$ という漸化式を計算させられました。
これをコンビネーションに置き換えると
${}_i\mathrm{C}_j={}_{i-1}\mathrm{C}_{j-1}+{}_{i-1}\mathrm{C}_{j}$
となります。この漸化式には様々な説明付けができるので、興味がある方は調べてみてください。
私は、 $i$ 人から $j$ 人を選ぶ場合の数は
『$i-1$ 人で $j-1$ 人グループを作っているところに、人 $i$ が入って $j$ 人グループになる』+『$i-1$ 人で $j$ 人グループを作っていて、人 $i$ が入る余地はない』
という説明が好きです。
その他、グリッドの経路数などでも説明ができます。
つまり、nCrを全部出力すれば……
この問題で求めた数列は、${}_i\mathrm{C}_j$ の表です。ということは、${}_i\mathrm{C}_j$ を直接計算して出力しても正解になるはずです。ということでやってみましょう。
from math import comb # combはPython3.8で追加された関数なので、Python3.8で提出してね
N = int(input())
for i in range(N):
print(*(comb(i, j) for j in range(i+1)))
適当に $N=6$で出力してみます。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
確かにパスカルの三角形です。この問題で一体何を求めていたのか、よくわかると思います。
C問題『K Swap』
問題ページ:C - K Swap
灰コーダー正解率:20.6 %
茶コーダー正解率:64.9 %
緑コーダー正解率:88.1 %
入力
$N$ : 数列の長さ
$K$ : 操作でスワップできる要素同士の距離
$a_i$ : 数列 $A$ の $i$ 番目の要素
考察
初項を $a_0$ として、$0$ 基準で考えます。
$0\le{i}\lt{K}$ として、添字を $i+jK$ の形で表します。すると、$i$ が同じ要素同士は、バブルソートの要領で操作を繰り返すことで、自由な順番に並び替えることができます。
- $a_{i+0K}$ は $a_{i+1K}$ とスワップできます。
- $a_{i+1K}$ は、$a_{i+2K}$ とスワップできます。
- $a_{i+2K}$ は、 $a_{i+3K}$ とスワップできます。
- 一般化すると、$a_{i+jK}$ は、$a_{i+(j+1)K}$ とスワップできます。
- 操作は何度でもできるので、左から順に並べたいものをバケツリレーのように渡していけば、好みの順番に並び替えることができます。
例えば $a_{i+3K}$ の要素を $i+0K$ 番目に持っていくためには、$i+3K$ 番目と$i+2K$ 番目をスワップ、$i+2K$ 番目を $i+1K$ 番目をスワップ、$i+1K$ 番目と $i+0K$ 番目をスワップすればいいです。同様のことを繰り返すと、他の要素も同じグループ内の好きな場所に持っていけます。
目的は $A$ を昇順に並び替えることです。そのためには少なくとも、$i$ が同じグループの中で、昇順になっていない要素の組があってはいけません。したがって、$i$ が同じグループの要素は昇順に並び替える必要があります。
すべての $0\le{i}\lt{K}$ について、グループを昇順にソートします。こうしてできた数列、、全体として昇順になっているか確認すればいいです。
コード
def judge():
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [[] for _ in range(K)] # i を Kで割った余りごとに管理
for i, x in enumerate(A):
B[i % K].append(x)
for i in range(K):
B[i].sort() # ソートする
SA = [0] * N
for i in range(N):
SA[i] = B[i % K][i // K]
return SA == sorted(A)
print("Yes" if judge() else "No")
D問題『Together Square』
問題ページ:D - Together Square
灰コーダー正解率:3.0 %
茶コーダー正解率:12.6 %
緑コーダー正解率:32.6 %
考察
平方数とは、すべての因数の次数が偶数である数のことです。
$i$ を固定して、$1\le{i}\le{N}$ で全探索します。
$a,b,c$ を正の整数とします。$i$ を平方数で割れるだけ割って、$i=a\times{b^2}$ の形で表します。$i\times{j}$ が平方数になるには、$j$ の因数に $a$ が含まれていなければなりません。そうでないと、次数が $1$ の素因数が存在することになり、$i\times{j}$ が平方数になりません。
つまり、$j=a\times{c^2}$ と表される必要があります。このとき、$i\times{j}=(abc)^2$ になり、たしかに平方数です。
$i$ を決めると、$a,b$ は一意に定まります。よって、$j=a\times{c^2}$ の $c$ を $1$ から全探索して、$j>N$ になったら打ち切ればいいです。
$c$ は最大でも $\sqrt{N}$ 程度にしかなりませんから、全体の計算量は $O(N\sqrt{N})$ です。
コード
from itertools import count
def calc_odd_factor_prod(n):
"""次数が奇数の素因数の積を得る(わかりづらかったら、普通に素因数分解して、次数が奇数のものをかけ合わせてください"""
for i2 in (i * i for i in count(2)):
if i2 > n: break
while n % i2 == 0: n //= i2
return n
def main():
N = int(input())
ans = 0
for i in range(1, N + 1):
odd = calc_odd_factor_prod(i)
for j in range(1, N + 1):
if odd * j * j > N:
break
ans += 1
print(ans)
if __name__ == '__main__':
main()
E問題『Small d and k』
問題ページ:E - Small d and k
灰コーダー正解率:2.1 %
茶コーダー正解率:8.5 %
緑コーダー正解率:33.7 %
考察
重要な制約があります。
- 各頂点の次数は $3$ 以下(つながっている辺は $3$ つまで)
- クエリで答える距離 $k_i$ は $3$ 以下
この制約より、距離 $k_i$ より大きい頂点には訪れないようにBFSをして、訪れた頂点番号を足し合わせるだけで解けます。$1$ クエリのBFSで見る頂点数は$O({k_i}^{3})$ で、これは非常に小さいです。
ですので、$Q$ 回のクエリごとにBFSで答えを求めるだけでこの問題は解けます。
実装
ただし、クエリごとに訪問済みかどうかを管理するのに、長さ $N$ のリストを作ってしまうと、リストの生成の計算量が $O(N)$ なので、全体で $O(NQ)$となりTLEになります。
set
, dict
, defaultdict
などで必要な部分だけを記録するようにしましょう。
コード
from collections import deque, defaultdict
def solve(x, k):
ret = 0
que = deque((x,))
dist = defaultdict(lambda: 4) # 距離が4なら未訪問です
dist[x] = 0
while que:
u = que.popleft()
ret += u
cost = dist[u]
if cost == k: continue # この先の距離k+1以上の頂点は見ません
for v in G[u]:
if cost + 1 < dist[v]:
que.append(v)
dist[v] = cost + 1
return ret
N, M = map(int, input().split())
G = [[] for _ in range(N + 1)]
for _ in range(M):
a, b = map(int, input().split())
G[a].append(b) # a <-> b
G[b].append(a)
Q = int(input())
for _ in range(Q):
x, k = map(int, input().split())
print(solve(x, k))