ABC225のA,B,C,D問題を、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や拡散していただけると喜びます！

ABC225 まとめ

全提出人数: 6585人

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	AB------	300	32分	4984(4739)位
400	ABC-----	600	124分	4109(3866)位
600	ABC-----	600	65分	3392(3150)位
800	ABC-----	600	19分	2668(2428)位
1000	ABCD----	1000	81分	2005(1774)位
1200	ABCD----	1000	55分	1465(1238)位
1400	ABCD----	1000	37分	1050(827)位
1600	ABCD----	1000	19分	730(521)位
1800	ABCDE---	1500	87分	481(303)位
2000	ABCDE---	1500	63分	317(160)位
2200	ABCDE---	1500	48分	212(78)位
2400	ABCDE---	1500	37分	148(35)位

色別の正解率

色	人数	A	B	C	D	E	F	G	H
灰	2699	96.4 %	76.9 %	33.8 %	8.3 %	0.3 %	0.0 %	0.0 %	0.0 %
茶	1281	99.2 %	98.4 %	80.4 %	38.2 %	0.6 %	0.1 %	0.0 %	0.0 %
緑	970	99.2 %	99.0 %	91.8 %	75.5 %	7.2 %	0.4 %	0.0 %	0.0 %
水	559	99.6 %	99.6 %	98.2 %	94.1 %	31.3 %	0.4 %	0.0 %	0.0 %
青	355	99.2 %	99.2 %	98.9 %	98.3 %	64.2 %	3.7 %	2.8 %	0.6 %
黄	189	93.1 %	92.6 %	93.1 %	92.6 %	68.8 %	12.2 %	18.0 %	1.6 %
橙	35	97.1 %	97.1 %	94.3 %	94.3 %	91.4 %	40.0 %	51.4 %	2.9 %
赤	28	100.0 %	100.0 %	100.0 %	96.4 %	92.9 %	64.3 %	82.1 %	50.0 %

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

A問題『Distinct Strings』

問題ページ：A - Distinct Strings
灰コーダー正解率：96.4 %
茶コーダー正解率：99.2 %
緑コーダー正解率：99.2 %

入力

$S$ : 英小文字のみからなる長さ $3$ の文字列

考察

$S$ に何種類の文字が出てくるかで答えが決まります。

文字の種類数で答えがいくつになるかは、すべてサンプルに答えがあります。

$1$ 種類 : 1 （①①①）
$2$ 種類 : 3 （②①①・①②①・①①②　${}{3} \mathrm{C}{1} = 3$ 通り）
$3$ 種類 : $6$ （①②③・①③②・②①③・②③①・③①②・③②①　$3!=3\times{2}\times{1}=6$ 通り）

実装

if文でがんばって文字の種類数を求めてもいいですが、len(set(S))と書くことで文字の種類数が簡単にわかります。setで重複を省いたあと、lenで重複なしの要素数＝種類数を求めています。

コード

S = input()
N = len(set(S))

if N == 1:
    print(1)
elif N == 2:
    print(3)
else:
    print(6)

B問題『Star or Not』

問題ページ：B - Star or Not
灰コーダー正解率：76.9 %
茶コーダー正解率：98.4 %
緑コーダー正解率：99.0 %

入力

$N$ : 木の頂点数
$a_i,b_i$ : $i$ 番目の辺は $a_i$ と $b_i$ を結んでいる

考察

『ある $1$ つの頂点から、他のすべての頂点に $1$ 本ずつ辺が出ている木』かどうか判定すればいいです。

言い換えると、『他の $N-1$ 個の頂点に $1$ 本ずつ辺が出ている頂点がある』かどうか判定すればいいです。

各頂点が何回辺に出現するかカウントして、$N-1$ 回出てくる頂点があれば Yes です。

コード

N = int(input())
counter = [0] * (N + 1)

for _ in range(N - 1):
    a, b = map(int, input().split())
    counter[a] += 1
    counter[b] += 1

print("Yes" if N - 1 in counter else "No")

C問題『Calendar Validator』

問題ページ：C - Calendar Validator
灰コーダー正解率：33.8 %
茶コーダー正解率：80.4 %
緑コーダー正解率：91.8 %

入力

$N,M$ : 矩形（長方形）領域の行数・列数
$B_{i,j}$ : 矩形領域の、$i$ 行目 $j$ 列目に書いてある数字

考察

行列 $B$ が、カレンダーから矩形領域を向きを変えずに切り出したものである条件は、以下の $3$ つです。

カレンダーの一番左上が $1$ で始まっている
左右に隣り合う要素の差は $1$
上下に隣り合う要素の差は $7$

要素の差はforループで確かめればいいです。

一番左上が $1$ になる条件は、要素を $7$ で割った余りが $0$ の要素が切り出した領域の一番右に来ていることです。（日曜日の右に月曜日があるカレンダーは、左上が月曜日になりません）

コード

def judge():
    # 左上が1になりうるか確認
    for col in range(M):
        if B[0][col] % 7 == 0 and col != M - 1:
            return False

    # 左右に隣り合う要素の差が1か確認
    for row in range(N):
        for col in range(M - 1):
            if B[row][col] + 1 != B[row][col + 1]:
                return False

    # 上下に隣り合う要素の差が7か確認
    for row in range(N - 1):
        if B[row][0] + 7 != B[row + 1][0]:
            return False
    return True


N, M = map(int, input().split())
B = []
for _ in range(N):
    _b = list(map(int, input().split()))
    B.append(_b)

print("Yes" if judge() else "No")

D問題『Play Train』

問題ページ：D - Play Train
灰コーダー正解率：8.3 %
茶コーダー正解率：38.2 %
緑コーダー正解率：75.5 %

入力

$N$ : 電車の数
$Q$ : クエリの数

クエリ $1$
$x,y$ : 電車 $x$ の後部と、電車 $y$ の前部を連結させる（電車 $x$ の後ろに電車 $y$ が来るように連結する）

クエリ $2$
$x,y$ : 電車 $x$ の後部と、電車 $y$ の前部を分離させる（分離したあと、電車 $x$ が最後尾で、電車 $y$ が先頭になる）

クエリ $3$
$x$ : 電車 $x$ が含まれる連結成分の電車の番号を、先頭から順番にすべて出力する

ただし、クエリ $3$ で出力する電車の番号の個数の合計は、$10^6$ 以下

考察

双方向連結リストというデータ構造を実装すればいいです。

各電車ごとに、『前にある電車の番号』『後ろにある電車の番号』を記録しておきます。先頭で前に電車がない、最後尾で後ろに電車がない場合は、それがわかるように -1 を入れておきます。

クエリ $3$ が来たら、『前にある電車の番号』をたどって、先頭の電車まで移動します。その後、『後ろにある電車の番号』をたどって、順番に出力していけばいいです。

コード

def main():
    N, Q = map(int, input().split())
    _next = [-1] * (N + 1)  # すぐ後ろの電車の番号
    _prev = [-1] * (N + 1)  # すぐ前の電車の番号

    for _ in range(Q):
        query = list(map(int, input().split()))
        q = query[0]
        if q == 1:
            x, y = query[1:]
            _next[x] = y  # xの後ろにyがくる
            _prev[y] = x  # yの前にxがくる
        elif q == 2:
            x, y = query[1:]
            _next[x] = -1  # xが新しい最後尾
            _prev[y] = -1  # yが新しい先頭
        else:
            x = query[1]
            ans = []

            curr = x

            # まず電車を先頭までたどります
            while _prev[curr] != -1:
                curr = _prev[curr]

            # 先頭から最後尾までたどっていきます
            while curr != -1:
                ans.append(curr)
                curr = _next[curr]

            print(len(ans), *ans)  # 連結成分の大きさも出力することに注意


if __name__ == '__main__':
    main()

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

目次

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