12
Help us understand the problem. What are the problem?

posted at

updated at

【AtCoder解説】PythonでABC254のA,B,C,D,E問題を制する!

ABC254A,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))

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
12
Help us understand the problem. What are the problem?