ABC226の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や拡散していただけると喜びます！

ABC226 まとめ

全提出人数: 6612人

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	A-------	100	3分	5064(4840)位
400	AB------	300	37分	4213(3989)位
600	A-C-----	400	85分	3502(3278)位
800	AB-D----	700	77分	2760(2544)位
1000	ABCD----	1000	72分	2079(1865)位
1200	ABCD----	1000	41分	1523(1309)位
1400	ABCDE---	1500	101分	1080(882)位
1600	ABCDE---	1500	71分	752(565)位
1800	ABCDE---	1500	51分	508(337)位
2000	ABCDE---	1500	25分	322(184)位
2200	ABCDEF--	2000	77分	194(93)位
2400	ABCDE-G-	2100	62分	95(45)位

色別の正解率

色	人数	A	B	C	D	E	F	G	H
灰	2616	95.0 %	52.2 %	18.2 %	10.6 %	1.3 %	0.2 %	0.1 %	0.0 %
茶	1222	98.8 %	85.3 %	63.3 %	45.8 %	3.9 %	0.2 %	0.2 %	0.0 %
緑	960	98.8 %	93.2 %	89.4 %	82.1 %	23.4 %	0.8 %	1.2 %	0.0 %
水	549	99.5 %	96.2 %	97.5 %	94.9 %	66.1 %	5.8 %	3.5 %	0.2 %
青	383	99.7 %	98.4 %	99.0 %	98.7 %	89.8 %	27.1 %	9.7 %	0.3 %
黄	179	92.7 %	92.7 %	93.3 %	93.8 %	89.9 %	50.8 %	17.3 %	7.8 %
橙	32	93.8 %	93.8 %	93.8 %	93.8 %	93.8 %	78.1 %	53.1 %	31.2 %
赤	14	92.9 %	92.9 %	92.9 %	92.9 %	92.9 %	92.9 %	57.1 %	57.1 %

※表示レート、灰に初参加者は含めず

A問題『Round decimals』

問題ページ：A - Round decimals
灰コーダー正解率：95.0 %
茶コーダー正解率：98.8 %
緑コーダー正解率：98.8 %

入力

$X$ : 小数第三位までで表すことのできる実数（$0\le{X}\lt{100}$）

考察

Pythonには四捨五入するround関数がありますが、これを使うとWAになります。

X = float(input())
print(round(X))

Pythonのround関数は小数部分が0.5のとき、偶数に近い方に丸められるからです。例えば、round(1.5) == 2、round(0.5) == 0 です。

整数部分と小数部分を分けて受け取って、小数部分が $0.5$ 以上かどうかで場合分け
十分小さい整数（$0.00005$ など）を加えてからround関数を使う

コード

if文

a, b = map(int, input().split('.'))
ans = a
if b >= 500:
    ans += 1
print(ans)

小さい実数を加える

X = float(input())
print(round(X + 0.00005))

B問題『Counting Arrays』

問題ページ：B - Counting Arrays
灰コーダー正解率：52.2 %
茶コーダー正解率：85.3 %
緑コーダー正解率：93.2 %

入力

$N$ : 数列の個数
$L_i$ : 数列 $i$ の長さ
$a_{i,j}$ : 数列 $i$ の $j$ 番目の要素

考察

数列そのものをset型に入れて、重複を省いた数をlenで求めればいいです。

実装

数列をリストで受け取ってsetに入れようとすると、以下のエラーが出ます。

    S.add(A)
TypeError: unhashable type: 'list'

これは、「set型にはunhashable（ハッシュ化できない）な型、リストは入れられません」というエラーです。

mutable（ミュータブル）なコンテナはunhashableです。mutableとは、要素が変更可能という意味です。ミュータブルなコンテナは、list、dict、setが該当して、これらはsetに入れることができません。

一方、immutable（イミュータブル）なコンテナはhashableですから、setに入れることができます。immutableは、要素が変更不能という意味です。イミュータブルなコンテナは、tuple、frozensetが該当します。

よって、数列はタプルにしてsetに追加する必要があります。

コード

N = int(input())
S = set()

for _ in range(N):
    l, *A = map(int, input().split())  # lはどうでもいいです
    A = tuple(A)  # タプルにしないと、setに追加できません
    S.add(A)

print(len(S))

C問題『Martial artist』

問題ページ：C - Martial artist
灰コーダー正解率：18.2 %
茶コーダー正解率：63.3 %
緑コーダー正解率：89.4 %

入力

$N$ : 技の数
$T_i$ : 技 $i$ を覚えるのに必要な時間
$K_i$ : 技 $i$ を覚えるため前に覚える必要がある技の数（$K_i$ の合計は $2\times{10^5}$ 以下）
$A_{i,j}$ : 技 $i$ を覚えるのに必要な技の $j$ 番目（$A_{i,j}<i$ ）

考察

答えは『技 $N$ を覚えるために必要な技すべてを覚えるのにかかる時間の合計』です。

『技 $N$ を覚えるために必要な技すべて』がわかればいいです。求めるためには、技の前提条件を辺としたグラフを作って、技 $N$ からDFSかBFSをすればいいです。

コード

def solve():
    # スタックを使ったDFSです（dequeを使ってBFSにしてもいいです）
    seen = [False] * (N + 1)
    stack = [N]
    seen[N] = True

    ans = 0

    while stack:
        u = stack.pop()
        ans += T[u]

        for v in G[u]:
            if not seen[v]:
                seen[v] = True
                stack.append(v)
    return ans


N = int(input())
T = [0] * (N + 1)
G = [[] for _ in range(N + 1)]

for u in range(1, N + 1):
    T[u], k, *A = map(int, input().split())
    for v in A:
        G[u].append(v)
        G[v].append(u)  # この行は不要ですが、とりあえず入れておきます（uを覚えるのに必要な技vは、uより小さい番号のため）

print(solve())

D問題『Teleportation』

問題ページ：D - Teleportation
灰コーダー正解率：10.6 %
茶コーダー正解率：45.8 %
緑コーダー正解率：82.1 %

入力

$N$ : 街の数
$x_i, y_i$ : 街 $i$ の座標

考察

街 $i$ と街 $j$ の座標の差を $(x_d, y_d)=(x_j-x_i, y_j-y_i)$ とします。

街 $i$ から街 $j$ に移動できる魔法は、$x_d,y_d$ 両方を割り切れる数（公約数）を $k$ として、$(\frac{x_d}{k},\frac{y_d}{k})$ と表されます。この魔法を $k$ 回使うことで、$(x_d, y_d)$ ちょうど移動することができます。

例えば、$(x_d,y_d)=(6,36)$ とします。$6,36$ の公約数は、$1,2,3,6$ ですから、魔法 $(6,36),(3,18),(2,12),(1,6)$ のいずれかで移動できます。

使う魔法の数を最小にしたいので、魔法をできるだけ使いまわせるようにしたいです。そのためには、最大公約数（GCD）で割った魔法を使うのが最適です。上の例だと、最大公約数 $6$ で割った魔法 $(1,6)$ を使うべきです。

最大公約数で割った魔法を複数回使えば、他の公約数で割った魔法でいける街すべてに行くことができるからです。$(1,6)$を $2$ 回使えば $(2,12)$、$3$ 回使えば$(3,18)$、$6$ 回使えば $(6,36)$ 移動できます。逆は成り立たないので、最大公約数で割った魔法が最適になります。

コード

from math import gcd

N = int(input())
XY = []

for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))

S = set()

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        xi, yi = XY[i]
        xj, yj = XY[j]
        xd, yd = xi - xj, yi - yj
        g = gcd(xd, yd)
        S.add((xd // g, yd // g))

print(len(S))

E問題『Just one』

問題ページ：E - Just one
灰コーダー正解率：1.3 %
茶コーダー正解率：3.9 %
緑コーダー正解率：23.4 %

入力

$N$ : 頂点数
$M$ : 辺数
$U_i, V_i$ : $i$ 番目の辺がつなぐ頂点

考察

答えは、連結成分ごとの辺の向きの付け方をすべて掛け合わせたものです。

連結成分ごとの組み合わせ数を求めることを考えます。

ある連結成分に属する辺 $1$ つにつき、その連結成分の出次数（ある頂点から他の頂点に向かう辺の数）の合計は $1$ 増えます。『どの頂点についても、その頂点から他の頂点に向かう辺がちょうど $1$ 本ずつ存在する』とき、連結成分の頂点数と出次数の合計は一致します。ですから、連結成分の頂点数と辺数は一致している必要があります。もし異なるとき、答えは $0$ になります。

『連結成分の頂点数と辺数が一致している』ときの答えを考えます。このとき、グラフには閉路が $1$ つだけ存在します。辺の向き付け方は閉路の辺の向きをどちら周りにするかの $2$ 通りしかなく、閉路に属さない頂点につながる辺の向き付け方は一意に定まります。（絵を書いてみてね）

連結成分ごとに、頂点数と辺数をカウントします。すべての連結成分について頂点数と辺数が等しいなら、答えは $2^{(連結成分数)}$ を $998244353$ で割った余りです。頂点数と辺数が異なる連結成分が $1$ つでもあるなら、答えは $0$ です。

コード

from collections import deque

MOD = 998244353


def main():
    def bfs(start):
        que = deque((start,))
        vc = 0  # 頂点数のカウント
        ec = 0  # 使った辺数のカウント（同じ辺を2度カウントするので、最後に2で割ります）
        seen[start] = True

        while que:
            u = que.popleft()
            vc += 1
            for v in G[u]:
                ec += 1
                if not seen[v]:
                    que.append(v)
                    seen[v] = True

        return 2 if vc == ec // 2 else 0  # 同じ辺を2度カウントしているので、2で割ります

    N, M = map(int, input().split())

    G = [[] for _ in range(N + 1)]

    for i in range(M):
        u, v = map(int, input().split())
        G[u].append(v)
        G[v].append(u)

    seen = [False] * (N + 1)

    ans = 1
    for i in range(1, N + 1):
        if not seen[i]:
            ans *= bfs(i)
            ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

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

目次

アプリ AtCoderFacts を開発しています