作成日 : 2021-11-08
更新日 : 2021-11-15
12 min readAtCoder

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 226」

コンテスト情報

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

配点

ルール

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

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

A -> Round decimals

問題文

小数第三位までで表すことのできる実数Xが、小数第三位まで入力されます。Xを小数第一位で四捨五入した結果として得られる整数を出力してください。

制約

• 0 ≤ X < 100
• Xは小数第三位までで表現可能である。
• Xは小数第三位まで与えられる。

入力

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

1X

出力

Xを小数第一位で四捨五入して得られる整数を出力せよ。

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

Contest中に考えたこと

• 小数点より前の数字と後ろの数字に分離する。
• 後ろの数字の先頭文字が0~4ならば、前の数字を出力する。そうでなければ前の数字+1を出力する。

解答

1# 標準入力を受け付ける。
2X = input()
3
4# 小数点より前の数字と後ろの数字に分離する。
5front, back = X.split('.')
6
7# 後ろの数字の先頭文字が0~4ならば、前の数字を出力する。そうでなければ前の数字+1を出力する。
8# 小数第三位まで標準入力されるので、配列のidxエラーに関して考える必要はない。
9if int(back[0]) >= 0 and int(back[0]) <= 4:
10    print(front)
11else:
12    print(int(front) + 1)

B -> Counting Arrays

問題文

1からNまでの番号がついたN個の数列が与えられます。数列iは、長さがLiでj(1 ≤ j ≤ Li)番目の要素がai, jであるような数列です。数列iと数列jは、Li = Ljかつすべてのk(1 ≤ k ≤ Li)に対してai, k = aj, kが成り立つ時に同じであるとみなします。

同じ数列は1種類として数えるとき、数列1から数列Nの中に全部で何種類の数列がありますか？

制約

• 1 ≤ N ≤ 2 × 10の5乗
• 1 ≤ Li ≤ 2 × 10の5乗(1 ≤ i ≤ N)
• 0 ≤ ai, j ≤ 10の9乗(1 ≤ i ≤ N, 1 ≤ j ≤ Li)
• すべての数列の要素の個数の和、すなわち(L0 + L1 + L2 + ... + LN)は2 × 10の5乗を超えない。
• 入力はすべて整数である。

入力

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

1N
2L1 a1,1 a1,2 … a1,L1
3​L2 a2,1 a2,2 … a2,L2
4​⋮
5LN aN,1 aN,2 … aN,LN

出力

数列の種類数を出力せよ。

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

Contest中に考えたこと

• list型でin句を用いて重複確認していると、TLEになる可能性が高い。
• set型を利用して、重複削除を行いつつ、数列の種類数を求める。

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4ans = set()
5for _ in range(N):
6    x = list(map(int, input().split()))
7    # set型を利用すると、自動的に重複削除される。
8    # list型で格納すると、エラーが発生するためstr型で格納する。
9    ans.add(str(x[1:]))
10
11print(len(ans))

C -> Martial artist

問題文

高橋君は武術家です。 武術家の覚えられる技はN個あり、技1, 2, …, Nと名前がついています。1 ≤ i ≤ Nについて、技iを習得するには時間Tiの修練が必要で、 さらに、修練の開始時点で技Ai,1, Ai,2, …, Ai,Kiをすでに習得している必要があります。

ここで、1 ≤ j ≤ Kiについて、Ai,j < iであることが保証されます。

高橋君は時刻0の時点で技を1つも覚えていません。 高橋君は同時に1つの技に対する修練しかできず、また、一度始めた修練を途中でやめることもできません。 高橋君が技Nを習得するのに必要な時間の最小値を求めてください。

制約

• 1 ≤ N ≤ 2 × 10の5乗
• 1 ≤ Ti ≤ 10の9乗
• 0 ≤ Ki < i
• 1 ≤ Ai,j < i
• (K1 + K2 + K3 + ... KN) ≤ 2 × 10の5乗
• Ai,1, Ai,2, …, Ai,Kiはすべて異なる。
• 入力は全て整数である。

入力

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

1N
2T1 K1 A1,1 A1,2 … A1,K1
3T2 K2 A2,1 A2,2 … A2,K2
4​⋮
5TN KN AN,1 AN,2 … AN,KN

出力

技Nを習得するのに必要な時間の最小値を出力せよ。

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

Contest中に考えたこと

• 技Nから順に必要な技情報を遡っていく。
• 新しい技を習得するために身につけておくべき技 < 新しい技の関係を利用する。

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4# 各技(1~N)を習得するために必要な時間を管理する。
5# T[0]は利用しない。
6T = [0] * (N + 1)
7# 各技(1~N)を習得するために、習得しておくべき技の情報を管理する。
8# A[0]は利用しない。
9A = [[]] * (N + 1)
10
11for i in range(1, N + 1):
12    X = list(map(int, input().split()))
13    T[i] = X[0]
14    A[i] = X[2:]
15
16# need_list : 技Nを習得するために、必要な技を管理する。
17# need_list[idx] = True : 技Nを習得するために、技idxを習得する必要がある。
18# need_list[idx] = False : 技Nを習得するために、技idxを習得する必要がない。
19# need_list[0]は利用しない。
20need_list = [False] * (N + 1)
21# 技Nは習得することが決まっているので、Trueと初期化する。
22need_list[len(need_list) - 1] = True
23
24# 新しい技の習得に紐づく、習得しておくべき技情報は、習得しておくべき技情報 < 新しい技の関係であるため、以下のようなfor文が実現できる。
25for n in range(N, 0, -1):
26    if not need_list[n]:
27        continue
28
29    # 技nを習得するために、習得しておくべき技に関してTrueに変更する。
30    for child in A[n]:
31        need_list[child] = True
32
33ans = 0
34for i in range(1, N + 1):
35    if need_list[i]:
36        ans += T[i]
37
38print(ans)

D -> Teleportation

問題文

AtCoder国は無限に広がる直交座標の上にあります。AtCoder国にはN個の街があり、1, 2, …, Nと番号が付けられています。街iは地点(xi ,yi)にあり、2つの異なる番号の街が同じ座標にあることはありません。

AtCoder国には転移魔法(以下、魔法と表記)があります。魔法は整数の組(a, b)によって識別されていて、地点(x, y)にいるときに魔法(a, b)を使うと(x + a, y + b)にワープすることができます。

すぬけ君は、任意の整数の組(a, b)を選んで魔法(a, b)を覚えることができる大魔術師です。また、すぬけ君は何種類でも魔法を覚えることができます。

魔法を使って街と街の間を移動したくなったすぬけ君は、全ての相異なる街の組(i, j)について次の行動を取れるようにいくつかの魔法を覚えることにしました。

• 覚えた魔法のうち1種類の魔法のみを選ぶ。その後、選んだ魔法のみを繰り返し使って街iから街jに移動する。

すぬけ君が上の条件を満たすように魔法を覚えるとき、少なくとも何種類の魔法を覚えればよいですか？

制約

• 2 ≤ N ≤ 500
• 0 ≤ xi ≤ 10の9乗(1 ≤ i ≤ N)
• 0 ≤ yi ≤ 10の9乗(1 ≤ i ≤ N)
• i ≠ jならば(xi, yi) ≠ (xj, yj)である。

入力

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

1N
2x1 y1
3x2 y2
4⋮
5xN yN

出力

すぬけ君が覚える必要がある魔法の個数の最小値を出力せよ。

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

Contest中に考えたこと

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

解答

1################################
2# <方針>
3# N ** 2を実行しても、250000回だから2重ループは大丈夫。
4# 異なる2点を選ぶ。
5# 異なる2点のx1座標とx2座標が等しい場合、y1座標とy2座標が等しい場合、x1座標とx2座標, y1座標とy2座標が異なる場合を考える。
6# ※ x1座標とx2座標, y1座標とy2座標が共に等しい場合は、問題文より考える必要はない。
7# 異なる2点を選んだ時に、x1座標とx2座標が等しい場合、(0, 1) or (0, -1)の移動の繰り返しで片方の街に到着できる。よって、x1座標とx2座標が等しい場合が存在するのか判定して、存在する場合に+2すると良い。
8# 異なる2点を選んだ時に、y1座標とy2座標が等しい場合、(1, 0) or (-1, 0)の移動の繰り返しで片方の街に到着できる。よって、y1座標とy2座標が等しい場合が存在するのか判定して、存在する場合に+2すると良い。
9# 異なる2点を選んだ時に、x1座標とx2座標, y1座標とy2座標が異なる場合、傾きを求める。傾きが等しい街どおしは、2種類の魔法で完結するので、重複を除いた傾きを洗い出して、x2すると問題を解くことが可能になる。
10# 傾きとは? : https://ja.wikipedia.org/wiki/%E5%82%BE%E3%81%8D_(%E6%95%B0%E5%AD%A6)
11################################
12
13# 標準入力を受け付ける。
14N = int(input())
15
16xy = []
17for i in range(N):
18    x, y = map(int, input().split())
19    xy.append((x, y))
20
21# x1座標とx2座標が等しい街があるかどうかを判定するためのフラグ。
22vertical_flag = False
23# y1座標とy2座標が等しい街があるかどうかを判定するためのフラグ。
24beside_flag = False
25# 重複を除いた、傾き情報
26tilt_list = set()
27for i in range(N):
28    for j in range(i + 1, N):
29        # 異なる2点を取得する。
30        x1, y1 = xy[i]
31        x2, y2 = xy[j]
32
33        # x1座標とx2座標が等しい街であるかどうか確かめる。
34        if x1 == x2:
35            vertical_flag = True
36            continue
37
38        # y1座標とy2座標が等しい街であるかどうか確かめる。
39        if y1 == y2:
40            beside_flag = True
41            continue
42
43        # 傾きを求める。
44        tilt = (y2 - y1) / (x2 - x1)
45
46        # 傾きを格納する。自動的に重複削除される。
47        tilt_list.add(tilt)
48
49cnt = 0
50if vertical_flag:
51    cnt += 2
52if beside_flag:
53    cnt += 2
54
55print(cnt + (len(tilt_list) * 2))

2021年11月7日時点のレート画像

プロフィールを確認する

参考文献

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