12 min readAtCoder
【備忘録】AtCoder Beginner Contest 227 A~D問題
AtCoder Beginner Contest 227のA~D問題に関して、問題文からContest中に考えたこと、解答等を備忘録としてまとめました。是非最後までご一読ください。
- そもそもAtCoderとは?
- 「AtCoder Beginner Contest 227」
- A -> Last Card
- B -> KEYENCE building
- C -> ABC conjecture
- D -> Project Planning
- 参考文献
執筆者 - おすすめの記事3選
そもそもAtCoderとは?
AtCoderを一言で表すと、オンラインで参加できるプログラミングコンテスト(競技プログラミング)サイトになります。リアルタイムのコンテストで競い合ったり、約3000問のコンテストの過去問に、いつでも挑戦出来ることが魅力です。
今回は 「AtCoder Beginner Contest 227」のプログラミングコンテストへ参加しました。
「AtCoder Beginner Contest 227」
コンテスト情報
- 開催日時 : 2021年11月13日(土) 21:00~22:40
- 参加資格 : AtCoderのアカウントをお持ちの方であれば、どなたでもご参加いただけます。
配点
| 問題 | 点数 |
|---|---|
| A | ??? |
| B | ??? |
| C | ??? |
| D | ??? |
| E | ??? |
| F | ??? |
| G | ??? |
| H | ??? |
ルール
- 競技開始と同時に8問の問題が提示されます。解く順序は自由です。
- AtCoderで使用できるすべてのプログラミング言語を使用可能です。
- 問題ごとに得点が設定され、合計得点を競います。得点が同じ場合は早く解いた人が上の順位になります。
- 誤答ペナルティは5分です。合計ペナルティは、最後に点数が増えた提出の時間から算出されます。
- 詳細は、「ルール」からご確認ください。
A -> Last Card
問題文
1, 2, …, Nの番号のついたN人の人に合計K枚のカードを配ります。人Aから始めて人A, A+1, A+2, …, N, 1, 2, …の順に1枚ずつカードを配るとき、最後のカードは誰に配られるでしょうか？
厳密には、人x(1 ≤ x < N)の次には人x+1にカードを配り、人Nの次には人1にカードを配ります。
制約
- 1 ≤ N, K ≤ 1000
- 1 ≤ A ≤ N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
1N K A出力
最後のカードが配られた人の番号を出力せよ。
本問題は、AtCoder株式会社で作成された、A - Last Card問題を参照しております。
Contest中に考えたこと
- Kの最大値が1000であるため、1重ループしても問題ないことを確認する。
- 問題文の通りに、実際にカードを配ってみて、最後にカードが誰に配られるのか求める。
解答
1# 標準入力を受け付ける。
2N, K, A = map(int, input().split())
3
4# 最初Aの方へカードを配る。よって、カードが1枚減少する。
5K = K - 1
6
7# カードを配る処理を行う。
8# カード枚数が0になった場合に終了する。
9while K != 0:
10 # 人へカードを配る。よって、カードが1枚減少する。
11 K -= 1
12
13 # カードを配る人を選定する。
14 # A == Nの場合、1の人に配る。
15 # A != Nの場合、A + 1の人に配る。
16 if A == N:
17 A = 1
18 else:
19 A += 1
20
21print(A)B -> KEYENCE building
問題文
1からNの番号がついたN人の人がいます。人iはキーエンス本社ビルの建築面積をSi平方メートルであると予想しました。
キーエンス本社ビルは下図のような形をしています。ただし、a, bはある正の整数です。つまり、キーエンス本社ビルの建築面積は4ab + 3a + 3b平方メートルと表されます。
N人のうち、この情報のみによって、予想した面積が確実に誤りであるとわかる人数を求めてください。
制約
- 1 ≤ N ≤ 20
- 1 ≤ Si ≤ 1000
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
1N
2S1 … SN
出力
答えを出力せよ。
本問題は、AtCoder株式会社で作成された、B - KEYENCE building問題を参照しております。
Contest中に考えたこと
- NやSiの値が小さいため、問題を解くに際してループ数を気にする必要はない。
- a, bへ正の整数(a, b) = (1, 1), (1, 2), ... (1, n), (2, 1), (2, 2) ...を与えて、各人が予想する建築面積が正しいかどうか、検査する。
- 各人が予想する建築面積より「4ab+3a+3b」の値が大きくなった場合、検査を終了する。
解答
1# 標準入力を受け付ける。
2N = int(input())
3
4S = list(map(int, input().split()))
5
6# 実際の建築面積になりうる値を演算する関数。
7def calc_area(a, b):
8 return 4 * a * b + 3 * a + 3 * b
9
10# 予想した面積が確実に誤りであるとわかる人数
11error_cnt = 0
12for i in range(N):
13 # 各人が予想した建築面積が正しいかどうか、検査する。
14 # a, bは正の整数。正の整数の初期化を行う。
15 a = 1
16 b = 1
17 # 各人が予想した建築面積が正しいか判定するためのフラグを用意する。
18 is_correct = False
19 # 各人が予想した建築面積。
20 expected = S[i]
21 # a, bの値へ正の整数を与えて、各人が予想した建築面積が正しいかどうか検査する。
22 # 各人が予想する建築面積より「4ab+3a+3b」の値が大きくなった場合、ループを終了する。
23 while True:
24 while True:
25 actual = calc_area(a, b)
26
27 # 各人が予想した建築面積が正しければループを終了する。
28 if actual == expected:
29 is_correct = True
30 break
31
32 # 各人が予想する建築面積より「4ab+3a+3b」の値が大きくなった場合、ループを終了する。
33 if actual > expected:
34 break
35
36 b += 1
37
38 # 各人が予想した建築面積が正しければループを終了する。
39 if is_correct == True:
40 break
41
42 a += 1
43 b = 1
44
45 actual = calc_area(a, b)
46
47 # 各人が予想する建築面積より「4ab+3a+3b」の値が大きくなった場合、ループを終了する。
48 if actual > expected:
49 break
50
51 if is_correct == False:
52 error_cnt += 1
53
54print(error_cnt)C -> ABC conjecture
問題文
正の整数Nが与えられます。A ≤ B ≤ CかつABC ≤ Nであるような正の整数の組(A, B, C)の個数を求めてください。
なお、制約の条件下で答えは2の63乗未満であることが保証されます。
制約
- 1 ≤ N ≤ 10の11乗
- Nは整数である
入力
入力は以下の形式で標準入力から与えられる。
1N出力
答えを出力せよ。
本問題は、AtCoder株式会社で作成された、C - ABC conjecture問題を参照しております。
Contest中に考えたこと
- Aの最大値は何になるのか考える。 ⏩ A * A * A <= Nが成り立つ、Aの最大値であると気づく。ここで終了しました。。
解答
1# 標準入力を受け付ける。
2N = int(input())
3ans = 0
4
5for a in range(1, N + 1):
6 # aの値をとりうる範囲を考える。
7 # aは正の整数なので、aの最小値は1である。
8 # aの最大値は、a, b, cの値がaの時である。よってa * a * a <= Nが成り立つ、aの最大値が最大になる。
9 # 反対にa * a * a > Nの時、aの値をとることができないので、そのタイミングでbreakする。
10 if a * a * a > N:break
11 for b in range(a, N + 1):
12 # bの値をとりうる範囲を考える。
13 # bは正の整数かつa以上なので、bの最小値はaである。
14 # bの最大値は、aの値がa, bの値がb, cの値がbの時である。よってa * b * b <= Nが成り立つ、bの最大値が最大になる。
15 # 反対にa * b * b > Nの時、bの値をとることができないので、そのタイミングでbreakする。
16 if a * b * b > N:break
17 # cの値をとりうる範囲を考える。
18 # a * b * c <= N ⏩ c <= N / a / b かつ b <= c ⏩ b <= c <= N / a / b
19 # よってcの個数は、(N / a / b) - b + 1
20 # +1しているのは、b=cの場合を含めるため。
21 ans += int(N / a / b) - b + 1
22print(ans)D -> Project Planning
問題文
キーエンスにはN個の部署があり、i(1 ≤ i ≤ N)番目の部署にはAi人の社員が所属しています。異なる部署に同じ社員が所属していることはありません。
キーエンスは、部署をまたいだ全社横断プロジェクトを計画しています。1つのプロジェクトはK個の相異なる部署から1人ずつ選出して作り、ちょうどK人から構成されるようにします。
プロジェクトは最大でいくつ作れますか？ただし、1人が複数のプロジェクトに参加することはできません。
制約
- 1 ≤ K ≤ N ≤ 2 × 10の5乗
- 1 ≤ Ai ≤ 10の12乗
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
1N K
2A1 A2 … AN
出力
プロジェクトの個数の最大値を出力せよ。
本問題は、AtCoder株式会社で作成された、D - Project Planning問題を参照しております。
解答
1################################
2# <方針>
3# プロジェクトの最大数を二分探索を用いて算出する。
4# 二分探索のleft値をプロジェクトの最大数と考える。
5# 参考 : https://zenn.dev/fjnkt98/articles/5bef9f4cf2af60
6################################
7
8# 標準入力を受け付ける。
9N, K = map(int, input().split())
10
11A = list(map(int, input().split()))
12
13# left: 実現可能なプロジェクトの最大数
14left = 0
15right = 100000000000000000000
16
17# left >= rightになった場合に、プロジェクト数の探索を終了する。
18while right - left > 1:
19 # mid : 仮のプロジェクトの最大数
20 mid = left + (right - left) // 2
21 # count : プロジェクトの最大数がmidの時の、各部署から排出すべき人数の合計。
22 count = 0
23
24 for i in range(N):
25 # プロジェクトの最大数をmidとした場合に、各部署から排出すべき人数を算出する。
26 # mid(プロジェクトの最大数) > 各部署の人数(A[i])の場合、各部署の人数(A[i])分しか、排出できないため、A[i]とする。
27 # 反対にmid(プロジェクトの最大数) <= 各部署の人数(A[i])の場合、mid(プロジェクト数)分、各部署の人数(A[i])を排出する。
28 # 参考 : https://www.youtube.com/watch?v=9o4Lbxd3up4
29 count += min(A[i], mid)
30
31 # midのプロジェクト数を満たすためには、mid x K人必要である。
32 # プロジェクトの最大数がmidの時の、各部署から排出すべき人数の合計 >= mid x kの時、プロジェクト数(mid)を実現できる。
33 if count >= mid * K:
34 left = mid
35 # プロジェクトの最大数がmidの時の、各部署から排出すべき人数の合計 < mid x kの時、プロジェクト数(mid)を実現できない。
36 else:
37 right = mid
38
39print(left)2021年11月13日時点のレート画像
