14 min readAtCoder
【備忘録】AtCoder Beginner Contest 223 A~D問題
AtCoder Beginner Contest 223のA~D問題に関して、問題文からContest中に考えたこと、解答等を備忘録としてまとめました。是非最後までご一読ください。
- そもそもAtCoderとは?
- 「AtCoder Beginner Contest 223」
- A -> Exact Price
- B -> String Shifting
- C -> Doukasen
- D -> Restricted Permutation
- 参考文献
執筆者 - おすすめの記事3選
そもそもAtCoderとは?
AtCoderを一言で表すと、オンラインで参加できるプログラミングコンテスト(競技プログラミング)サイトになります。リアルタイムのコンテストで競い合ったり、約3000問のコンテストの過去問に、いつでも挑戦出来ることが魅力です。
今回は 「AtCoder Beginner Contest 223」のプログラミングコンテストへ参加しました。
「AtCoder Beginner Contest 223」
コンテスト情報
- コンテスト時間 : 100分
- レーティング更新対象 : 0 - 1999
配点
| 問題 | 点数 |
|---|---|
| A | 100 |
| B | 200 |
| C | 300 |
| D | 400 |
| E | 500 |
| F | 500 |
| G | 600 |
| H | 600 |
ルール
- コンテスト中に問題に正解すると点数を獲得できます。
- 順位は総合得点で決定します。
- 同点の場合は提出時間の早い人が上の順位になります。
- 誤答を提出するたびにペナルティが加算されます。このコンテストのペナルティは5分です。(ルールに関して詳しくみる)
このコンテストは「コンテスト中に提出された結果」だけで順位が決定します。
A -> Exact Price
問題文
高橋君の財布の中には100円硬貨が1枚以上入っており、それ以外には何も入っていません。高橋君の財布の中の合計金額がX円である可能性はありますか？
制約
- 0 ≤ X ≤ 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
1X出力
高橋君の財布の中の合計金額がX円である可能性がある場合はYes、そうでない場合はNoと出力せよ。
本問題は、AtCoder株式会社で作成された、A - Exact Price問題を参照しております。
Contest中に考えたこと
- Xの値が100より小さいならば、
Noを出力する。 - Xの値を100で割った余りを取得する。
- 余りが0の場合、
Yes, そうでない場合Noと出力する。
解答
1# 標準入力を受け付ける。
2X = int(input())
3
4# Xの値が100より小さいならば、`No`にする。
5if X < 100:
6 print('No')
7 exit()
8
9# Xの値を100で割った余りを取得する。
10amari = X % 100
11
12# 余りが0の場合、`Yes`, そうでない場合`No`と出力する。
13if amari == 0:
14 print('Yes')
15else:
16 print('No')B -> String Shifting
問題文
空でない文字列に対し、先頭の文字を末尾に移動する操作を左シフト、末尾の文字を先頭に移動する操作を右シフトと呼びます。
例えば、abcdeに対して左シフトを1回行うとbcdeaとなり、右シフトを2回行うとdeabcとなります。
英小文字からなる空でない文字列Sが与えられます。Sに対し左シフトと右シフトをそれぞれ好きな回数(0回でもよい)行って得られる文字列のうち、辞書順で最小のものと最大のものを求めてください。
辞書順とは？ : 辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、英小文字からなる相異なる文字列S, Tの大小を判定するアルゴリズムを以下に説明します。以下では「Sのi文字目の文字」をSiのように表します。また、SがTより辞書順で小さい場合はS < T、大きい場合はS > Tと表します。S, Tのうち長さが大きくない方の文字列の長さをLとします。i = 1, 2, …, Lに対してSiとTiが一致するか調べます。Si ≠ Tiであるiが存在する場合、そのようなiのうち最小のものをjとします。そして、SjとTjを比較して、SjがTjよりアルファベット順で小さい場合は S < T 、そうでない場合はS > Tと決定して、アルゴリズムを終了します。Si ≠ Tiであるiが存在しない場合、SとTの長さを比較して、SがTより短い場合はS < T、長い場合はS > Tと決定して、アルゴリズムを終了します。
制約
- Sは英小文字からなる。
- Sの長さは1以上1000以下である。
入力
入力は以下の形式で標準入力から与えられる。
1S出力
2行にわたって出力せよ。Sに対し左シフトと右シフトをそれぞれ好きな回数(0回でもよい)行って得られる文字列のうち、辞書順で最小のものと最大のものをそれぞれSmin, Smaxとおいたとき、1行目にはSminを、2行目にはSmaxを出力せよ。
本問題は、AtCoder株式会社で作成された、B - String Shifting問題を参照しております。
Contest中に考えたこと
- 左シフトを1回して、右シフトを1回すると、元の文字列に戻る。 ⏩ 文字列パターンとして、左シフト or 右シフトのみを(0, 1, ..., N)回実行した場合に、生成される文字列を洗い出すだけで問題ない。
- 左シフトのみを(0, 1, ..., N)回実行した場合に、生成される文字列を洗い出す。
- 生成された文字列を、辞書順でソートする。
- 辞書順でソートした文字列の、最小の文字列と最大の文字列を取得する。
- Sの長さが最大1000文字であるので、計算量を考慮しなくてよい。
解答
1# 標準入力を受け付ける。
2S = input()
3
4# 左シフトすることで、生成される文字列を格納する。
5Slist = [S]
6tmp = ''
7
8# 左シフトのみを(0, 1, ..., N)回実行した場合に、生成される文字列を洗い出す。
9for i in range(0, len(S)):
10 tmp += S[i]
11 Slist.append(S[i + 1:] + tmp)
12
13# 生成された文字列を、辞書順でソートする。
14Slist.sort()
15
16# 辞書順でソートした文字列の、最小の文字列と最大の文字列を取得する。
17min = Slist[0]
18max = Slist[len(Slist) - 1]
19
20print(min)
21print(max)C -> Doukasen
問題文
N本の導火線を一直線に接着したものがあります。左からi本目の導火線は長さがAi cmで、1秒あたりBi cmの一定の速さで燃えます。この導火線の左端と右端から同時に火をつけるとき、 2つの火がぶつかる場所が着火前の導火線の左端から何cmの地点か求めてください。
制約
- 1 ≤ N ≤ 10の5乗
- 1 ≤ Ai, Bi ≤ 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
1N
2A1 B1
3A2 B2
4⋮
5AN BN
出力
2つの火がぶつかる場所が着火前の導火線の左端から何cmの地点か(単位を除いて)出力せよ。想定解答との絶対誤差または相対誤差が10の−5乗以下(小数点以下第5位まで正しいか)であれば正解として扱われる。
本問題は、AtCoder株式会社で作成された、C - Doukasen問題を参照しております。
Contest中に考えたこと
- 左から伸びる導火線を、何本まで燃やすことができるのか考える。
- 最後に残った導火線を左、右からどのくらいのスピードで消化できるのか考える。 ⏩ コーディング中に終了してしまいました。。ここで終了。
解答
1# 標準入力を受け付ける。
2N = int(input())
3
4lines = []
5endTime = 0
6for _ in range(N):
7 A, B = map(int, input().split())
8 lines.append((A, B))
9 endTime += A / B
10
11# 導火線が完全消滅する時間を記録する。
12# 片方(左 or 右)から火をつけて、導火線が完全消滅する時間 = ((A0 / B0) + (A1 / B1) + ... (AN / BN))
13# 左右から火をつけて導火線が完全消滅する時間 = ((A0 / B0) + (A1 / B1) + ... (AN / BN)) / 2
14endTime = endTime / 2
15
16# 左からどのくらいの導火線の長さで、導火線が完全消滅するのか記録する。
17leftLength = 0
18for a, b in lines:
19 # 導火線が完全消滅する時間よりも、a / bの時間が短い場合
20 if a / b <= endTime:
21 endTime -= a / b
22 leftLength += a
23 else:
24 # 最後に残った時間分の長さを足し合わせる。
25 # b * endTime : 導火線を燃やす速さ * 残り時間を足し合わせる。
26 leftLength += b * endTime
27 break
28
29# 結果を出力する。
30print(leftLength)D -> Restricted Permutation
問題文
(1, 2, …, N)を並び替えて得られる数列Pであって以下の条件を満たすもののうち、辞書順で最小のものを求めてください。
- i = 1, …, Mに対し、PにおいてAiはBiよりも先に現れる。
ただし、そのようなPが存在しない場合は-1と出力してください。
制約
- 2 ≤ N ≤ 2 × 10の5乗
- 1 ≤ M ≤ 2 × 10の5乗
- 1 ≤ Ai, Bi ≤ N
- Ai ≠ Bi
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
1N M
2A1 B1
3⋮
4AM BM
出力
答えを出力せよ。
本問題は、AtCoder株式会社で作成された、D - Restricted Permutation問題を参照しております。
学んだこと
- AiはBiよりも先に現れる。 ⏩ Ai → Biの有効グラフである。
- Ai → Bi → ... → Aiなど、Aiに→が戻る場合は、数列として生成できない。
- トポロジカルソートを利用して数列を並べ替える。
トポロジカルソートのイメージ画像
解答
1# 参考 ; https://docs.python.org/ja/3/library/heapq.html
2from heapq import heappush, heappop
3
4# 標準入力を受け付ける。
5N, M = map(int, input().split())
6
7# 有効グラフ情報を格納する。
8edges = []
9# →を指される数情報を格納する。
10pointed_arrow_cnt = []
11for i in range(0, N + 1):
12 edges.append([])
13 pointed_arrow_cnt.append(0)
14
15for _ in range(M):
16 a, b = map(int, input().split())
17
18 edges[a].append(b)
19 pointed_arrow_cnt[b] += 1
20
21q = []
22
23# 1からなのは、1~Nまでの値を利用しているため。
24for i in range(1, N + 1):
25 # →が指されていない番号を取り出して、ストックへ格納する。ストックの数列をソートする。
26 if pointed_arrow_cnt[i] == 0:
27 heappush(q, i)
28
29ans = []
30while len(q) != 0:
31 # ストックの一番上を答えに移動する。
32 p = heappop(q)
33 ans.append(p)
34 for to in edges[p]:
35 # 答えに入れた値から生成される→を削除する。
36 pointed_arrow_cnt[to] -= 1
37 if pointed_arrow_cnt[to] == 0:
38 # →が指されていない番号を取り出して、ストックへ格納する。ストックの数列をソートする。
39 heappush(q, to)
40
41if len(ans) == N:
42 print(*ans)
43else:
44 print(-1)2021年10月17日時点のレート画像
参考文献
- レーティングとは?
- AtCoderのプログラミングコンテストのルール
- AtCoder株式会社について
- 絶対誤差, 相対誤差について
- Atcoder 223に関するコードまとめ
- 有効グラフとは?
- トポロジカルソートとは?
- catupperさんの動画