作成日 : 2021-11-19
更新日 : 2021-11-19
9 min readAtCoder

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 205」

コンテスト情報

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

配点

ルール

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

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

A -> kcal

問題文

100mLあたりAkcalのエネルギーを持つドリンクがあります。このドリンクBmLは何kcalのエネルギーを持つでしょうか？

制約

• 0 ≤ A, B ≤ 1000
• 入力は全て整数である。

入力

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

1A B

出力

答えを表す数値を出力せよ。なお、想定解答との絶対誤差または相対誤差が10の−6乗以下であれば正解として扱われる。

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

Contest中に考えたこと

• 比例式を考えて、演算する。
• 100 : B = A : X ⏩ B * A = 100 * X ⏩ X = (B * A) / 100。

解答

1# 標準入力を受け付ける。
2A, B = map(int, input().split())
3
4# 比例式を考えて、演算する。
5# 100 : B = A : X ⏩ B * A = 100 * X ⏩ X = (B * A) / 100。
6print((B * A) / 100)

B -> Permutation Check

問題文

1以上N以下の整数からなる長さNの数列A = (A1, A2, …, AN)が与えられます。Aが(1, 2, …, N)の並び替えによって得られるかどうか判定してください。

制約

• 1 ≤ N ≤ 10の3乗
• 1 ≤ Ai ≤ N
• 入力は全て整数である。

入力

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

1N
2A1 A2 … AN

出力

Aが(1, 2, …, N)の並び替えによって得られるならYes、そうでないならNoと出力せよ。

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

Contest中に考えたこと

• 1~Nまでの数字が1回だけ出現するかどうか考える。
• 数字の出現回数を配列でメモしておく。
• 一度でも2回以上同じ数字が出現したらNo, そうでなければYesを出力する。

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4A = list(map(int, input().split()))
5
6# 数字の出現回数を配列でメモしておく。
7# num_cnt_list[0]の要素は利用しない。
8num_cnt_list = []
9for _ in range(N + 1):
10    # 数字の出現回数の初期値を0としておく。
11    num_cnt_list.append(0)
12
13for i in range(N):
14    num_cnt_list[A[i]] += 1
15    # 一度でも2回以上同じ数字が出現したら`No`, そうでなければ`Yes`を出力する。
16    if num_cnt_list[A[i]] > 1:
17        print('No')
18        exit()
19
20print('Yes')

C -> POW

問題文

数XをY回掛けたものを「XのY乗」といい、pow(X, Y)で表します。例えばpow(2, 3) = 2 × 2 × 2 = 8です。3つの整数A, B, Cが与えられるので、pow(A, C)とpow(B, C)の大小を比較してください。

制約

• −10の9乗 ≤ A, B ≤ 10の9乗
• 1 ≤ C ≤ 10の9乗
• 入力は全て整数

入力

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

1A B C

出力

pow(A, C) < pow(B, C)なら<を、pow(A, C) > pow(B, C)なら>を、pow(A, C) = pow(B, C)なら=を出力せよ。

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

Contest中に考えたこと

• 乗数を+1することでA, Bの値はどのように変化するのか考える。
• 乗数が偶数の場合、A, Bともに正の値となる。 ⏩A, Bの絶対値を取得して、A, Bの大小比較をすると良い。
• 乗数が奇数の場合、正のA or 正のBのみ正の値となり、負のA or 負のBのみ負の値となる。 ⏩そのままA, Bの大小比較をすると良い。

解答

1# 標準入力を受け付ける。
2A, B, C = map(int, input().split())
3
4# 乗数が偶数の場合、A, Bともに正の値となる。 ⏩A, Bの絶対値を取得して、A, Bの大小比較をすると良い。
5# 乗数が奇数の場合、正のA or 正のBのみ正の値となり、負のA or 負のBのみ負の値となる。 ⏩そのままA, Bの大小比較をすると良い。
6if C % 2 == 0:
7    A = abs(A)
8    B = abs(B)
9
10# A, Bの大小比較。
11if A == B:
12    print('=')
13elif A > B:
14    print('>')
15else:
16    print('<')

D -> Kth Excluded

問題文

長さNの正整数列A = (A1, A2, …, AN)とQ個のクエリが与えられます。i(1 ≤ i ≤ Q)番目のクエリでは、正整数Kiが与えられるので、A1, A2, …, ANのいずれとも異なる正整数のうち、小さい方から数えてKi番目のものを求めてください。

制約

• 1 ≤ N, Q ≤ 10の5乗
• 1 ≤ A1 < A2 < ⋯ < AN ≤ 10の18乗
• 1 ≤ Ki ≤ 10の18乗
• 入力は全て整数である。

入力

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

1N Q
2A1 A2 … AN
3K1
4K2
5​⋮
6KQ

出力

Q行出力せよ。i行目にはi番目のクエリに対する答えを出力せよ。

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

解答

1import bisect
2
3# 標準入力を受け付ける。
4N, Q = map(int, input().split())
5
6# 問題文より、A[0] < A[1] < A[2] ... < A[N - 1]なので、ソートする必要はない。
7A = list(map(int, input().split()))
8
9for _ in range(Q):
10    # <方針> ###################################
11    # 1. A[x - 1] <= q(x) < A[x + 1]のx値を算出する。
12    # 2. qの値より前のAの配列の要素数をlとする。
13    # 3. qの値より前のAの配列の要素数(l)分、数字を進めないといけないため、qの値をq + lにする。
14    # 4. 1~3を繰り返す。
15    ###########################################
16    q = int(input())
17
18    l = 0
19
20    # 二分探索を用いて、A[x - 1] <= q(x) < A[x + 1]のx値を算出する。
21    while True:
22        # 1つ前のlの値。
23        l_prev = l
24
25        # bisect_right ###################
26        # 参考 : https://qiita.com/ta7uw/items/d6d8f0ddb215c3677cd3
27        # 配列内にq + lに等しい値があれば、その値の右のidxを返す。
28        # A[0]より小さいq + lが入力された場合、0を返す。
29        # A[N - 1]より大きいq + l値が入力された場合、Nの値を返す。
30        ##################################
31        l = bisect.bisect_right(A, q + l)
32
33        if l_prev == l:
34            break
35    print(q + l)

参考文献

• レーティングとは?
• AtCoderのプログラミングコンテストのルール
• 絶対誤差, 相対誤差とは?
• AtCoder株式会社について
• 比例式とは?
• Atcoder 205に関するコードまとめ