作成日 : 2021-10-31
更新日 : 2021-11-01
12 min readAtCoder

【備忘録】AtCoder Beginner Contest 225 A~D問題

AtCoder Beginner Contest 225のA~D問題に関して、問題文からContest中に考えたこと、解答等を備忘録としてまとめました。是非最後までご一読ください。

そもそもAtCoderとは?

AtCoderを一言で表すと、オンラインで参加できるプログラミングコンテスト(競技プログラミング)サイトになります。リアルタイムのコンテストで競い合ったり、約3000問のコンテストの過去問に、いつでも挑戦出来ることが魅力です。

今回は 「AtCoder Beginner Contest 225」のプログラミングコンテストへ参加しました。

「AtCoder Beginner Contest 225」

コンテスト情報

• コンテスト時間 : 100分
• レーティング更新対象 : 0 - 1999

配点

ルール

1. コンテスト中に問題に正解すると点数を獲得できます。
2. 順位は総合得点で決定します。
3. 同点の場合は提出時間の早い人が上の順位になります。
4. 誤答を提出するたびにペナルティが加算されます。このコンテストのペナルティは5分です。(ルールに関して詳しくみる)

このコンテストは「コンテスト中に提出された結果」だけで順位が決定します。

A -> Distinct Strings

問題文

英小文字のみからなる長さ3の文字列Sが与えられます。

Sの各文字を並び替えて得られる文字列は、何種類ありますか？

制約

• Sは英小文字のみからなる長さ3の文字列

入力

入力は以下の形式で標準入力から与えられる。

1S

出力

Sの各文字を並び替えて得られる文字列の種類数を出力せよ。

本問題は、AtCoder株式会社で作成された、A - Distinct Strings問題を参照しております。

Contest中に考えたこと

• 長さ3の文字列を分割して考える。
• 3つの文字が全て等しい場合、1を出力する。
• 2つの文字が等しい場合、3を出力する。
• 全ての文字が異なる場合、6を出力する。

解答

1# 標準入力を受け付ける。
2s = input()
3
4# 3つの文字が全て等しい場合、1を出力する。
5if s[0] == s[1] == s[2]:
6    print(1)
7# 2つの文字が等しい場合、3を出力する。
8elif s[0] == s[1] or s[1] == s[2] or s[0] == s[2]:
9    print(3)
10# 全ての文字が異なる場合、6を出力する。
11else:
12    print(6)

B -> Star or Not

問題文

N頂点N − 1辺の木が与えられます。頂点には1, 2, …, Nの番号がついており、i本目の辺は頂点aiと頂点biを結んでいます。

この木がスターであるか判定してください。

ただしスターとは、1つの頂点から、他の全ての頂点に1本ずつ辺が出ている木のことです。

注記

「木」については、Wikipedia「木(数学)」 を参照してください。

制約

• 3 ≤ N ≤ 10の5乗
• 1 ≤ ai < bi ≤ N
• 与えられるグラフは木である

入力

入力は以下の形式で標準入力から与えられる。

1N
2a1 b1
3​⋮
4aN−1 bN−1

出力

与えられたグラフがスターであるならYesと、スターでないならNoと出力せよ。

本問題は、AtCoder株式会社で作成された、B - Star or Not問題を参照しております。

Contest中に考えたこと

• edges[各頂点] = [各頂点と辺で結ばれる頂点1, 各頂点と辺で結ばれる頂点2, ...]で管理する。
• 各頂点に対し、スターであるか確かめる。

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4# edges[各頂点] = [各頂点と辺で結ばれる頂点1, 各頂点と辺で結ばれる頂点2, ...]で管理する。
5# edges[0]は利用しない。
6edges = []
7for _ in range(N + 1):
8    edges.append([])
9 
10for _ in range(N - 1):
11    A, B = map(int, input().split())
12    # 辺の情報からedgesへ値を代入する。
13    edges[A].append(B)
14    edges[B].append(A)
15 
16for edge in edges:
17    # 各頂点に対し、スターであるか確かめる。
18    if len(edge) == N - 1:
19        print('Yes')
20        exit()
21 
22print('No')

C -> Calendar Validator

問題文

10の100乗行7列の行列Aがあり、任意の整数対(i, j)(1 ≤ i ≤ 10の100乗,1 ≤ j ≤ 7)についてその(i, j)成分は(i − 1) × 7 + jです。

N行M列の行列Bが与えられるので、BがAから一部の矩形領域を（向きを変えずに）切り出したものであるかを判定してください。

制約

• 1 ≤ N ≤ 10の4乗
• 1 ≤ M ≤ 7
• 1 ≤ Bi, j ≤ 10の9乗
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

1N M
2B1, 1 B1, 2 … B1, M
3​B2, 1 B2, 2 … B2, M
4​⋮
5BN, 1 BN, 2 … BN, M

出力

BがAから一部の矩形領域を切り出したものであればYesと、そうでないならNoと出力せよ。

本問題は、AtCoder株式会社で作成された、C - Calendar Validator問題を参照しております。

Contest中に考えたこと

• Bi, jの数字が行列Aのどこかに入っていることを確認する。
• ある行の先頭と次の行の先頭の数字に関して、確認する。((Bi, 0) + 7 == (Bi + 1, 0))
• 各行の先頭の数字をもとに、行の要素数の正しさを確認する。(各行の先頭の数字のidxを調べて、各行の要素数の長さと比較を行う。)
• 各行に関して規則通りに並んでいるのか、確認する。((Bi, j+1) = (Bi, j) + 1になっているのか)

解答

1# 標準入力を受け付ける。
2N, M = map(int, input().split())
3
4next = 0
5valid = True
6for _ in range(N):
7    B = list(map(int, input().split()))
8    first = B[0]
9
10    # ある行の先頭と次の行の先頭の数字に関して、確認する。((Bi, 0) + 7 == (Bi + 1, 0))
11    if next != 0 and next != first:
12        valid = False
13
14    # 各行の先頭の数字をもとに、行の要素数の正しさを確認する。(各行の先頭の数字のidxを調べて、各行の要素数の長さと比較を行う。)
15    idx = first % 7
16    if idx == 0:
17        row_len = 1
18    else:
19        row_len = 7 - idx + 1
20
21    if row_len < len(B):
22        valid = False
23
24    # 各行に関して規則通りに並んでいるのか、確認する。((Bi, j+1) = (Bi, j) + 1になっているのか)
25    row_check = first
26    for j in range(1, len(B)):
27        if row_check + 1 != B[j]:
28            valid = False
29
30        row_check = B[j]
31
32    next = first + 7
33
34if valid:
35    print('Yes')
36else:
37    print('No')

D -> Play Train

問題文

高橋君は電車のおもちゃを連結させたり分離させたりして遊んでいます。電車はN個あり、電車1、電車2、…、電車Nと名前がついています。はじめ電車どうしは連結しておらず全てバラバラです。

クエリがQ個与えられるので、与えられた順番に処理してください。クエリは次の3種類のいずれかです。

1 x y

• 電車xの後部と、電車yの前部を連結させる。以下のことが保証されます。
• x ≠ y
• クエリを処理する直前に、電車xの後部と連結している電車は存在しない
• クエリを処理する直前に、電車yの前部と連結している電車は存在しない
• クエリを処理する直前に、電車xと電車yは異なる連結成分に属する

2 x y

• 電車xの後部と、電車yの前部を分離させる。以下のことが保証されます。
• x ≠ y
• クエリを処理する直前に、電車xの後部と電車yの前部は直接連結している

3 x

• 電車xが含まれる連結成分に属する電車の番号を、先頭から順番に全て出力する。

制約

• 2 ≤ N ≤ 10の5乗
• 1 ≤ Q ≤ 10の5乗
• 1 ≤ x ≤ N
• 1 ≤ y ≤ N
• 入力は全て整数
• クエリは全て問題文の条件を満たす
• 3 xの形式のクエリで出力する電車の番号の個数の合計は10の6乗以下

入力

入力は以下の形式で標準入力から与えられる。

1N Q
2query1
3​query2
4​⋮
5queryQ

i番目のクエリqueryiでは、まずクエリの種類ci(1, 2, 3のいずれか)が与えられる。ci = 1, 2の場合はx, yが追加で与えられ、ci = 3の場合はxが追加で与えられる。

すなわち、各クエリは以下に示す3つの形式のいずれかである。

11 x y

12 x y

13 x

出力

あるci = 3のタイプのクエリにおいて、出力すべき値がj1, j2, …, jMであるとする。このとき以下の形式で1行に出力せよ。

1M j1 j2 … jM

ci = 3のタイプのクエリの数をqとして、q行出力せよ。k(1 ≤ k ≤ q)行目ではk番目のそのようなクエリに対する答えを出力せよ。

本問題は、AtCoder株式会社で作成された、D - Play Train問題を参照しております。

Contest中に考えたこと

• 本文を読んで終了しました。。

解答

1################################
2# <方針>
3# 電車の連結状態を前部(front)と後部(back)に分ける。
4# `1 x y`のクエリを実行する場合、
5# クエリを処理する直前に、電車xの後部と連結している電車は存在しないと書かれているので、
6# back[x] = yとなる。
7# クエリを処理する直前に、電車yの前部と連結している電車は存在しないと書かれているので、
8# front[y] = xとなる。
9# それ以外の場合は電車通しが連結していないため、-1などの値を入れておく。
10
11# `2 x y`のクエリを実行する場合、電車の連結を外すために
12# back[x] = -1とする。
13# front[y] = -1とする。
14
15# `3 x`のクエリを実行する場合、
16# front[x] != -1を繰り返し(一番前の電車番号を探す)、back[x] != -1の場合の値を出力していく。(順に電車の番号を辿っていく。)
17################################
18
19# 標準入力を受け付ける。
20N, Q = map(int, input().split())
21
22front = []
23back = []
24for i in range(N + 1):
25    # それ以外の場合は電車通しが連結していないため、-1などの値を入れておく。
26    front.append(-1)
27    back.append(-1)
28
29for _ in range(Q):
30    q = list(map(int, input().split()))
31
32    # `1 x y`のクエリを実行する場合、
33    # クエリを処理する直前に、電車xの後部と連結している電車は存在しないと書かれているので、
34    # back[x] = yとなる。
35    # クエリを処理する直前に、電車yの前部と連結している電車は存在しないと書かれているので、
36    # front[y] = xとなる。
37    if q[0] == 1:
38        x = q[1]
39        y = q[2]
40        front[y] = x
41        back[x] = y
42
43    # `2 x y`のクエリを実行する場合、電車の連結を外すために
44    # back[x] = -1とする。
45    # front[y] = -1とする。
46    if q[0] == 2:
47        x = q[1]
48        y = q[2]
49        front[y] = -1
50        back[x] = -1
51
52    if q[0] == 3:
53        x = q[1]
54
55        # `3 x`のクエリを実行する場合、
56        # front[x] != -1を繰り返し(一番前の電車番号を探す)、back[x] != -1の場合の値を出力していく。(順に電車の番号を辿っていく。)
57        ret = []
58        while front[x] != -1:
59            x = front[x]
60        ret = [x]
61        while back[x] != -1:
62            ret.append(back[x])
63            x = back[x]
64
65        print(len(ret), *ret)

2021年10月30日時点のレート画像

プロフィールを確認する

参考文献

• レーティングとは?
• AtCoderのプログラミングコンテストのルール
• AtCoder株式会社について
• 木とは?
• Atcoder 225に関するコードまとめ