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

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 206」

コンテスト情報

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

配点

ルール

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

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

A -> Maxi-Buying

問題文

ABC国の消費税率は8パーセントです。ABC国にはエナジードリンク屋さんがあります。ここでは、エナジードリンク1本を、税抜きN円で販売しています。

ここに消費税を加算した後の金額は⌊1.08 × N⌋円となります。ただし、実数xに対し、⌊x⌋はx以下の最大の整数を表します。

この金額が定価の206円より安いならYay!、定価と等しいならso-so、定価より高いなら:(と出力して下さい。

制約

• 1 ≤ N ≤ 300
• Nは整数

入力

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

1N

出力

答えを出力せよ。

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

Contest中に考えたこと

• ⌊x⌋はx以下の最大の整数 ⏩ 小数点以下は切り捨てる。
• if文を用いて、Yay!, so-so, :(を出し分ける。

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4# ⌊x⌋はx以下の最大の整数 ⏩ 小数点以下は切り捨てる。
5# 参考 : https://note.nkmk.me/python-math-floor-ceil-int/
6price = int(1.08 * N)
7
8if price < 206:
9    print('Yay!')
10elif price == 206:
11    print('so-so')
12else:
13    print(':(')

B -> Savings

問題文

シカのAtCoDeerくんは、空の貯金箱を持っています。AtCoDeerくんは、その貯金箱に、1日目の朝に1円、2日目の朝に2円 …というように、i日目の朝にi円を貯金箱に入れます。

また、AtCoDeerくんは、毎日夜に貯金箱にいくら入っているかを確認します。AtCoDeerくんが貯金箱にN円以上入っていることを初めて確認するのは、何日目の夜でしょうか?

制約

• 1 ≤ N ≤ 10の9乗
• Nは整数

入力

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

1N

出力

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

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

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4# 貯金日数を管理する変数
5day_cnt = 0
6# 貯金額を管理する変数
7sum_money = 0
8
9# 貯金額がN以上になるまでwhile文を回す。
10while sum_money < N:
11    # 貯金日数を+1する。
12    day_cnt += 1
13    # 貯金額を貯金日数分、足し合わせる。
14    sum_money += day_cnt
15
16print(day_cnt)

C -> Swappable

問題文

N個の整数からなる配列A = (A1, A2, ..., AN)が与えられるので、次の条件を全て満たす整数組(i, j)の数を求めてください。

• 1 ≤ i < j ≤ N
• Ai ≠ Aj

制約

• 入力は全て整数
• 2 ≤ N ≤ 3 × 10の5乗
• 1 ≤ Ai ≤ 10の9乗

入力

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

1N
2A1 A2 … AN

出力

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

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

解答

1# 参考 : https://note.nkmk.me/python-collections-counter/
2import collections
3
4# 標準入力を受け付ける。
5N = int(input())
6A = list(map(int, input().split()))
7
8# 配列内に含まれる整数の重複数を、各整数ごとにカウントする。
9# 参考 : https://note.nkmk.me/python-collections-counter/
10c = collections.Counter(A)
11
12i = N
13ans = 0
14# 参考 : https://note.nkmk.me/python-collections-counter/
15for item in c.items():
16    # 整数
17    num = item[0]
18    # 整数の重複数
19    duplicate_num = item[1]
20
21    # 整数(num変数)と重複していない、残りの配列の数を洗い出す。
22    i -= duplicate_num
23    # 整数(num変数)に関する整数組の数を演算する。
24    ans += duplicate_num * i
25
26print(ans)

D -> KAIBUNsyo

問題文

N項からなる正整数列A = (A1, A2, …AN)が与えられます。以下の操作を0回以上何度でも行える時、操作を最小何回行えば、Aを回文にすることができますか？

• ある正整数の組(x, y)を選ぶ。その後、現在Aに含まれるxをすべてyに置き換える。

なお、この問題では、全ての整数i(1 ≤ i ≤ N)について、Ai = AN + 1 − iが成り立つとき、またその時に限って、Aが回文であると言います。

制約

• 入力は全て整数
• 1 ≤ N ≤ 2 × 10の5乗
• 1 ≤ Ai ≤ 2 × 10の5乗

入力

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

1N
2A1 A2 … AN

出力

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

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

解答

1from collections import deque
2
3################################
4# <方針>
5# 回文とは何かについて考える。
6# 回文とは「前から読んでも後ろから読んでも同じ言葉、数字であるもの」を意味する。
7# 例えば`13531`, `あいういあ`, `93244239`などが回文にあたる。
8# 今回、回文を生成するために、組み合わせ(x, y)を選んで、現在Aに含まれるxをyに置換するが、まず置換しなくていい箇所を洗い出す。
9# <置換しないていい箇所>
10# ・奇数の場合、真ん中のA。(どんな値に置換されても回文になるため。)
11# ・A[i]番目の数字とA[N - i + 1]番目の数字が等しい箇所。
12# 上記の箇所以外を、最適に置換して回文を作ることを考える。
13# <どのように置換していくのか?>
14# ・A[i]番目の数字とA[N - i + 1]番目の数字どちらかを、もう片方の数字にすると最小の操作でうまくいく。 ⏩ A[i] 〜 A[N - i]間の無効グラフであると考える。
15# ・無向グラフに対してDFS(深さ優先探索)を行う。
16# ・DFS(深さ優先探索)とは? : https://qiita.com/drken/items/4a7869c5e304883f539b
17# ・参考 : https://www.youtube.com/watch?v=Nd31ytkNrgQ
18################################
19
20# 標準入力を受け付ける。
21N = int(input())
22A = list(map(int, input().split()))
23
24# 正整数列の最大値を格納する。
25max_val = max(A) + 1
26
27# 数値間情報(A[i]番目 〜 A[N - i])を格納する。
28edges = []
29for _ in range(max_val):
30    edges.append([])
31
32mid = N // 2
33for i in range(0, mid):
34    a = A[i]
35    b = A[N - i - 1]
36    # 異なる2数字の場合のみ、無向グラフの生成を行う。
37    if a != b:
38        edges[a].append(b)
39        edges[b].append(a)
40
41# A[i]番目へ訪れたかどうか表す、フラグ情報を格納する。
42visited = [False] * (max_val)
43ans = 0
44for i in range(1, max_val):
45    # 無向グラフがないA[i]番目に関しては考えない。
46    if edges[i] == []:
47        continue
48
49    # 一度訪れた無向グラフに関しては考えない。
50    if visited[i]:
51        continue
52
53    # 参考 : https://docs.python.org/ja/3/library/collections.html#collections.deque
54    dq = deque([i])
55    while len(dq) != 0:
56        now = dq.pop()
57        # 訪れたA[i]番目に関して、フラグをTrueへ変更する。
58        visited[now] = True
59        for to in edges[now]:
60            if visited[to] == 1:
61                continue
62            visited[to] = True
63            ans += 1
64            dq.append(to)
65
66print(ans)

参考文献

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