12 min readAtCoder
【備忘録】AtCoder Beginner Contest 228 A~D問題
AtCoder Beginner Contest 228のA~D問題に関して、問題文からContest中に考えたこと、解答等を備忘録としてまとめました。是非最後までご一読ください。
- そもそもAtCoderとは?
- 「AtCoder Beginner Contest 228」
- A -> On and Off
- B -> Takahashi's Secret
- C -> Final Day
- D -> Linear Probing
- 参考文献
執筆者 - おすすめの記事3選
そもそもAtCoderとは?
AtCoderを一言で表すと、オンラインで参加できるプログラミングコンテスト(競技プログラミング)サイトになります。リアルタイムのコンテストで競い合ったり、約3000問のコンテストの過去問に、いつでも挑戦出来ることが魅力です。
今回は 「AtCoder Beginner Contest 228」のプログラミングコンテストへ参加しました。
「AtCoder Beginner Contest 228」
コンテスト情報
- コンテスト時間 : 100分
- レーティング更新対象 : 0 - 1999
配点
| 問題 | 点数 |
|---|---|
| A | ??? |
| B | ??? |
| C | ??? |
| D | ??? |
| E | ??? |
| F | ??? |
| G | ??? |
| H | ??? |
ルール
- コンテスト中に問題に正解すると点数を獲得できます。
- 順位は総合得点で決定します。
- 同点の場合は提出時間の早い人が上の順位になります。
- 誤答を提出するたびにペナルティが加算されます。このコンテストのペナルティは5分です。(ルールに関して詳しくみる)
このコンテストは「コンテスト中に提出された結果」だけで順位が決定します。
A -> On and Off
問題文
高橋君は、毎日S時0分に部屋の電気をつけ、毎日T時0分に消します。電気をつけている間に日付が変わることもあります。X時30分に部屋の電気がついているかどうか判定してください。
制約
- 0 ≤ S, T, X ≤ 23
- S ≠ T
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
1S T X出力
X時30分に部屋の電気がついているならばYesと、そうでなければNoと出力せよ。
本問題は、AtCoder株式会社で作成された、A - On and Off問題を参照しております。
Contest中に考えたこと
- 部屋の電気をつけている間の、1時間単位の値を記録する。
- 上記を情報を用いて、X時30分の時間帯に電気はついているのか確認する。
解答
1# 標準入力を受け付ける。
2S, T, X = map(int, input().split())
3
4# 部屋の電気をつけている間の、1時間単位の値を格納する。
5time_list = []
6while True:
7 time_list.append(S)
8 # 部屋の電気を消すタイミングでwhile文を終了する。
9 if S == T:
10 break
11 # 日付が変わる場合、S = 0となる。
12 if S == 24:
13 S = 0
14 else:
15 S += 1
16
17for i in range(0, len(time_list) - 1):
18 # X時30分の時間帯に電気はついているのか確認する
19 if time_list[i] <= X < time_list[i + 1]:
20 print('Yes')
21 exit()
22
23print('No')B -> Takahashi's Secret
問題文
高橋君にはN人の友達がいます。N人の友達はそれぞれ、友達1、友達2、…、友達Nというあだ名で呼ばれています。ある日、高橋君はある恥ずかしい秘密を、友達の一人である友達Xに知られてしまいました。
i = 1, 2, …, Nについて、友達iが高橋君の秘密を知ったとき、友達Aiがまだ高橋君の秘密を知らなければ、友達iは高橋君の秘密を友達Aiにも教えてしまいます。
高橋君の秘密は最終的に何人の友達に知られることになるでしょうか？
制約
- 2 ≤ N ≤ 10の5乗
- 1 ≤ X ≤ N
- 1 ≤ Ai ≤ N
- Ai ≠ i
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
1N X
2A1 A2 ⋯ AN
出力
答えを出力せよ。
本問題は、AtCoder株式会社で作成された、B - Takahashi's Secret問題を参照しております。
Contest中に考えたこと
- 友達が秘密を知っているかどうかを表すフラグを用意する。
- 友達A[i]が高橋くんの秘密を知らなくて、友達iがA[i]へ秘密を話した場合、フラグを更新する。
- 反対に友達A[i]が高橋くんの秘密を知っていて、友達iがA[i]へ秘密を話した場合、秘密の伝言ゲームを終了する。
解答
1# 標準入力を受け付ける。
2N, i = map(int, input().split())
3
4A = list(map(int, input().split()))
5
6# 友達が秘密を知っているかどうかを表すフラグを用意する。
7# temp[0]は利用しない。
8temp = [False] * (N + 1)
9
10# 友達A[i]が秘密を知らない間、秘密の伝言ゲームを続ける。
11while True:
12 # 友達A[i]が秘密を知っていたならば、秘密の伝言ゲームを終了する。
13 if temp[i]:
14 break
15 # 友達A[i]が高橋くんの秘密を知らなくて、友達iがA[i]へ秘密を話した場合、フラグを更新する。
16 temp[i] = True
17 # 次に秘密を伝えるA[i]を指定する。
18 # -1しているのは、配列のidx調整のため。
19 i = A[i - 1]
20
21# 秘密を知っている人数を出力する。
22print(sum(temp))C -> Final Day
問題文
N人の生徒が4日間にわたる試験を受けています。それぞれの日に行われる試験は300点満点です。すなわち、4日間を通した試験の満点は1200点です。
現在3日目までの試験が終わり、これから4日目の試験が行われようとしています。i(1 ≤ i ≤ N)番目の生徒はj(1 ≤ j ≤ 3)日目の試験でPi, j点獲得しました。
それぞれの生徒について、4日目の試験後に上位K位以内に入っていることがあり得るかどうか判定してください。ただし、4日目の試験後の生徒の順位は、その生徒よりも4日間の合計点が高い生徒の人数に1を加えた値として定めます。
制約
- 1 ≤ K ≤ N ≤ 10の5乗
- 0 ≤ Pi, j ≤ 300(1 ≤ i ≤ N, 1 ≤ j ≤ 3)
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
1N K
2P1,1 P1,2 P1,3
3⋮
4PN,1 PN,2 PN,3出力
N行出力せよ。i(1 ≤ i ≤ N)行目には、i番目の生徒が4日目の試験後に上位K位以内に入っていることがあり得るならばYesと、そうでないならばNoと出力せよ。
本問題は、AtCoder株式会社で作成された、C - Final Day問題を参照しております。
Contest中に考えたこと
- 3日目までの各生徒の合計点数をまとめる。
- 4日目の試験でi番目の生徒が満点(300点)を取り、その他の生徒が0点の場合に、一番順位が上がるため、その場合のみを検討する。
- 二分探索を用いて、4日目までのi番目の生徒の合計点数がどの順位に位置するのか算出する。
解答
1import bisect
2
3# 標準入力を受け付ける。
4N, K = map(int, input().split())
5
6# 3日目までの各生徒の合計点数をまとめる。
7# score_list[0]は利用しない。
8score_list = []
9for _ in range(N + 1):
10 score_list.append([])
11
12# 3日目までの各生徒の合計点数を格納する。
13sum_score_list = []
14for i in range(N):
15 score = list(map(int, input().split()))
16 # 3日目までの合計点数を算出する。
17 sum_score = sum(score)
18 # score_list[1] : 1番目の生徒の3日目までの合計点数。
19 # score_list[2] : 2番目の生徒の3日目までの合計点数。
20 # ...
21 score_list[i + 1] = sum_score
22 sum_score_list.append(sum_score)
23
24# 合計点数をソートする。
25sum_score_list.sort()
26
27# score_list[0]を利用しないため、range(1, N + 1)とする。
28for i in range(1, N + 1):
29 # 4日目の試験でi番目の生徒が満点(300点)を取り、その他の生徒が0点の場合に、一番順位が上がるため、その場合のみを検討する。
30 # よって+300されている。
31 best_score = score_list[i] + 300
32
33 # 二分探索を用いて、4日目までのi番目の生徒の合計点数がどの順位に位置するのか算出する。
34 # 二分探索とは? : https://codezine.jp/article/detail/12243
35 # 参考 : https://qiita.com/ta7uw/items/d6d8f0ddb215c3677cd3
36 idx = bisect.bisect_right(sum_score_list, best_score)
37
38 # K以内に入る場合、`Yes`を返す。
39 if N - K + 1 <= idx:
40 print('Yes')
41 # K以内に入らない場合、`No`を返す。
42 else:
43 print('No')D -> Linear Probing
問題文
N = 2の20乗項からなる数列A = (A0, A1, …, AN−1)があります。はじめ、全ての要素は−1です。Q個のクエリを順番に処理してください。i(1 ≤ i ≤ Q)個目のクエリはti = 1またはti = 2を満たす整数tiおよび整数xiで表され、内容は以下の通りです。
- ti = 1のとき、以下の処理を順番に行う。
- 整数hをh = xiで定める。
- Ah mod N ≠ −1である間、hの値を1増やすことを繰り返す。この問題の制約下でこの操作が有限回で終了することは証明できる。
- Ah mod Nの値をxiで書き換える。
- ti = 2のとき、その時点でのAxi mod Nの値を出力する。
なお、整数a, bに対し、aをbで割った余りをa mod bと表します。
制約
- 1 ≤ Q ≤ 2 × 10の5乗
- ti ∈ {1, 2}(1 ≤ i ≤ Q)
- 0 ≤ xi ≤ 10の18乗(1 ≤ i ≤ Q)
- ti = 2であるようなi(1 ≤ i ≤ Q)が1つ以上存在する。
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
1Q
2t1 x1
3⋮
4tQ xQ
出力
ti = 2であるようなクエリに対し、それぞれ答えを1行に出力せよ。そのようなクエリが1つ以上存在することは保証される。
本問題は、AtCoder株式会社で作成された、D - Linear Probing問題を参照しております。
Contest中に考えたこと
- 「hの値を1増やすことを繰り返す」作業が、時間がかかるので工夫してhの値を算出する必要がある。 ⏩ 一度modされたA[h % N]は-1ではなくなるので、一度hになったものとそうでないものを区別して、hを算出するとうまくいきそう。 ⏩ 良いアイディアが浮かばず、ここで終了しました。。
解答
1# 標準入力を受け付ける。
2Q = int(input())
3
4N = 1048576
5A = [-1] * N
6
7# あるhを代入した時に、次のA[h] == -1を早期に発見するために利用する。
8nx = list(range(1, N)) + [0]
9
10def update(h, x):
11 if A[h] == -1:
12 A[h] = x
13 return h
14
15 # A[h] == -1が見つかるまで、hの探索を行う。
16 #
17 # <入力ケース>
18 # 6
19 # 1 1048577
20 # 1 1048577
21 # 1 1048577
22 # 1 1048577
23 # 1 1048577
24 # 2 1
25 # を考えるとわかりやすい。
26 #
27 # nxの値は以下のようになっていく。hを+1するよりもスムーズにA[h] == -1を探せるようになる。
28 # [1, 2, 3, 4, 5, ..., 0]
29 # [1, 3, 3, 4, 5, ..., 0]
30 # [1, 4, 3, 4, 5, ..., 0]
31 # [1, 5, 3, 4, 5, ..., 0]
32 nx[h] = update(nx[h], x)
33
34 return nx[h]
35
36for _ in range(Q):
37 t, x = map(int, input().split())
38 if t == 1:
39 update(x % N, x)
40 if t == 2:
41 print(A[x % N])2021年11月20日時点のレート画像
