作成日 : 2022-02-15
更新日 : 2022-02-15
11 min readAtCoder

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 238」

コンテスト情報

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

配点

ルール

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

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

A -> Exponential or Quadratic

問題文

2のn乗 > nの2乗ですか？

制約

• nは1以上10の9乗以下の整数

入力

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

1n

出力

2のn乗 > nの2乗ならYesを、そうでないならNoを出力せよ。

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

解答

1# 標準入力を受け付ける。
2n = int(input())
3
4# pow関数とは? : https://himibrog.com/python-pow/
5if pow(2, n) > pow(n, 2):
6    print('Yes')
7else:
8    print('No')

B -> Pizza

問題文

ここに円形のピザが1枚あります。高橋くんは長さNの数列Aを使ってこのピザを以下の手順で切り分けます。

1. 最初に、円の中心から12時の方向に切れ込みをひとつ入れます。
2. 次に、以下の操作をN回繰り返します。i回目の操作では以下を行います。
   1. まず、ピザを時計回りにAi度回転させる。
   2. 次に、円の中心から12時の方向に切れ込みをひとつ入れる。

例えば、A = (90, 180, 45, 195)として手順を行うと、下図のようになります。

このとき、最も大きなピザの中心角が何度であるか求めてください。

制約

• 入力は全て整数
• 1 ≤ N ≤ 359
• 1 ≤ Ai ≤ 359
• 同じ場所に複数回切れ込みが入ることはない。

入力

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

1N
2A1 A2 … AN

出力

答えを整数として出力せよ。​

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

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4A = list(map(int, input().split()))
5
6# ピザの切れ込みを入れた角度一覧
7slice_list = [0, 360]
8# 最後にピザに切れ込みを入れた角度を記録する。
9last_slice_angle = 0
10for i in range(len(A)):
11    # ピザの切れ込みを入れる角度へ移動する。
12    last_slice_angle += A[i]
13    # 一回転することを考慮する。
14    if last_slice_angle > 360:
15        last_slice_angle -= 360
16
17    slice_list.append(last_slice_angle)
18
19slice_list.sort()
20
21ans = 0
22for i in range(1, len(slice_list)):
23    ans = max(ans, slice_list[i] - slice_list[i - 1])
24
25print(ans)

C -> digitnum

問題文

整数Nが与えられるので、以下の問題を解いてください。

• f(x) = (x以下の正整数で、xと桁数が同じものの数)とします。

f(1) + f(2) + ⋯ + f(N)を998244353で割った余りを求めてください。

制約

• Nは整数
• 1 ≤ N < 10の18乗

入力

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

1N

出力

答えを整数として出力せよ。

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

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4# Nの桁数を保存する。
5NLen = len(str(N))
6
7ans = 0
8DIVIDE_VALUE = 998244353
9
10# 数字Nの各桁ごとに処理を行う。
11for i in range(NLen):
12    # current_digit : 処理を行う現在の桁
13    current_digit = i + 1
14    # 処理を行う、現在の桁の中での下限の数字
15    # 1桁の場合1, 2桁の場合10, 3桁の場合100, ...
16    bottom_num = 10 ** (current_digit - 1)
17
18    # 処理を行う、現在の桁が数字Nの桁と等しい場合
19    if current_digit == NLen:
20        # 桁の上限の数字 + 1
21        top_num = N + 1
22    else:
23        # 桁の上限の数字 + 1
24        # 1桁の場合10, 2桁の場合100, 3桁の場合1000, ...
25        top_num = (10 ** current_digit)
26
27    middle = (top_num - bottom_num) // 2
28
29    # 桁の個数を数える。
30    ans += (top_num - bottom_num + 1) * middle
31
32    # 奇数の場合、真ん中の桁も数える。
33    if (top_num - bottom_num) % 2 == 1:
34        ans += middle + 1
35
36    ans %= DIVIDE_VALUE
37
38print(ans)

D -> AND and SUM

問題文

T個のテストケースについて、以下の問題を解いてください。

非負整数a, sが与えられます。以下の条件を両方とも満たす非負整数の組(x, y)は存在しますか？

• x AND y = a
• x + y = s

ANDとは? : 非負整数n, mのbitごとの論理積n AND mは、以下のように定義されます。n AND mを二進表記した際の2のk乗(k ≥ 0)の位の数は、n, mを二進表記した際の2のk乗の位の数のうち両方が1であれば1、そうでなければ0である。例えば、4 AND 6 = 4となります（二進表記すると: 100 AND 110 = 100）。

制約

• 1 ≤ T ≤ 10の5乗
• 0 ≤ a, s < 2の60乗
• 入力はすべて整数

入力

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

1T

その後、T個のテストケースが続く。各テストケースは以下の形式で与えられる。

1a s

出力

T行出力せよ。i(1 ≤ i ≤ T)行目には、i番目に与えられるテストケースについて問題文中の条件を両方とも満たす非負整数の組(x, y)が存在するならYesを、存在しないならNoを出力せよ。

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

解答

1# <方針>
2# x and y = a ⏩ aを2進数表記した時の、1となる桁は、x, yを2進数表記した場合に、同じ桁は1となる。 ⏩ x, yの値は必ずa以上になる。
3# x + y = s ⏩  a + x` + a + y` = s ⏩  x` + y` = s - 2aとなる。
4# またx` + y`の各桁に関して、x xor yが成り立つ。(2進数の各桁が1, 1の場合に0になっている必要があるため。)
5# よって、x xor y = s - 2aが成り立つ。(a = x and y)
6# s - 2aをs`とした場合、s` < 0は`No`となる。
7# x and y, x xor yが成り立つx, yの条件を考える。 ⏩ x, yの各桁が0, 0 0, 1, 1, 0の場合は、xor, andを含む等式が成り立つが、1, 1の場合には成り立たない。(1, 1の場合andは1になるが、xorは0になるため。)よって、aをandして0になる条件を組み込む必要がある。
8# 参考動画 : https://www.youtube.com/watch?v=Ckuo6w6s_ko
9
10# 標準入力を受け付ける。
11T = int(input())
12
13for _ in range(T):
14    a, s = map(int, input().split())
15
16    if (s - 2 * a) >= 0 and (s - 2 * a) & a == 0:
17        print('Yes')
18    else:
19        print('No')

参考文献

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