作成日 : 2021-12-12
更新日 : 2021-12-12
10 min readAtCoder

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 231」

コンテスト情報

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

配点

ルール

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

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

A -> Water Pressure

問題文

水圧は水深のみに依存し、水深x[m]の場所ではx/100[MPa]になるものとします。

水深D[m]の場所の水圧は何[MPa]ですか？

制約

• 1 ≤ D ≤ 10000
• Dは整数である。

入力

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

1D

出力

答えを出力せよ。想定解答との絶対誤差または相対誤差が10の−3乗以下であれば(小数第３位まで正しければ)正解として扱われる。

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

Contest中に考えたこと

• D / 100の演算を行う。

解答

1# 標準入力を受け付ける。
2D = int(input())
3print(D / 100)

B -> Election

問題文

選挙が行われています。N人が投票を行い、i(1 ≤ i ≤ N)番目の人はSiという名前の候補者に投票しました。得票数が最大の候補者の名前を答えてください。なお、与えられる入力では得票数が最大の候補者は一意(一人に定める)に定まります。

制約

• 1 ≤ N ≤ 100
• Siは英小文字からなる長さ1以上10以下の文字列
• Nは整数
• 得票数が最大の候補者は一意に定まる

入力

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

1N
2S1
3S2
4​⋮
5SN

出力

得票数が最大の候補者の名前を出力せよ。

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

Contest中に考えたこと

• 候補者ごとに、得票数をまとめる。
• 得票数の多い順に候補者を並べる。
• 得票数の一番多い候補者を出力する。

解答

1import collections
2
3# 標準入力を受けつける。
4N = int(input())
5
6data = []
7for i in range(N):
8    S = input()
9    data.append(S)
10
11# 候補者ごとに、得票数をまとめる。
12# collections参考 : https://note.nkmk.me/python-collections-counter/
13c = collections.Counter(data)
14
15# 得票数の多い順に候補者を並べる。
16# 得票数の一番多い候補者を出力する。
17print(c.most_common()[0][0])

C -> Counting 2

問題文

N人の生徒からなるクラスがあり、i(1 ≤ i ≤ N)番目の生徒の身長はAiです。

j = 1, 2, …, Qについて、以下の質問に答えてください。

• N人のうち、身長がxj以上の生徒は何人か？

制約

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

入力

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

1N Q
2A1 ​A2 … AN 
3x1 
4x2
5⋮
6xQ

出力

Q行出力せよ。j(1 ≤ j ≤ Q)行目には身長がxj以上の生徒の数を出力せよ。​

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

Contest中に考えたこと

• 毎回A1とx1, A2とx1, ... ANとx1の身長を比較する、A1とx2, A2とx2, ... ANとx2の身長を比較する...とやっているとTLEになってしまう。
• A1〜ANを昇順ソートする。
• 二分探索を用いて、x1の身長が小さい順に並んだA1〜ANの身長の、何番目に位置するのか確かめる。x1の身長より大きいAx〜ANの人数を出力する。x2, x3, ...に関しても同様の処理を繰り返す。

解答

1# bisectについて : https://docs.python.org/ja/3/library/bisect.html
2import bisect
3 
4# 標準入力を受け付ける。
5N, Q = map(int, input().split())
6 
7A = list(map(int, input().split()))
8 
9# A1〜ANを昇順ソートする。
10A.sort()
11 
12for i in range(Q):
13    X = int(input())
14    # 二分探索を用いて、x1の身長が小さい順に並んだA1〜ANの身長の、何番目に位置するのか確かめる。x1の身長より大きいAx〜ANの人数を出力する。x2, x3, ...に関しても同様の処理を繰り返す。
15    idx = bisect.bisect_left(A, X)
16    print(len(A) - idx)

D -> Neighbors

問題文

1からNの番号がついたN人を横一列に並べる方法のうち、以下の形式のM個の条件全てを満たすものが存在するか判定してください。

• 条件：人Aiと人Biは隣り合っている

制約

• 2 ≤ N ≤ 10の5乗
• 0 ≤ M ≤ 10の5乗
• 1 ≤ Ai < Bi ≤ N
• (Ai, Bi)は相異なる

入力

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

1N M
2A1 B1
3​⋮
4AM BM

出力

条件を満たす並べ方が存在するならYes、存在しないならNoと出力せよ。

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

Contest中に考えたこと

• 隣り合っている = 同じ番号のついた人が3回以上登場してはならない。
• M = 0の時は、無条件でYesになる。
• ここで終了しました。。

解答

1import sys
2
3# 参考 : https://note.nkmk.me/python-sys-recursionlimit/
4sys.setrecursionlimit(10 ** 6)
5
6# 標準入力を受け付ける。
7N, M = map(int, input().split())
8
9# edges[0]は利用しない。
10edges = []
11for _ in range(N + 1):
12    edges.append([])
13
14for _ in range(M):
15    A, B = map(int, input().split())
16
17    edges[A].append(B)
18    edges[B].append(A)
19
20    # 同じ番号のついた人が3回以上登場してはならない。
21    if 3 <= max(len(edges[A]), len(edges[B])):
22        print('No')
23        exit()
24
25def dfs(now, pre=-1):
26    # 一度訪れたところに再度訪れようとしている場合は、`No`とする。
27    if visited[now] == True:
28        print('No')
29        exit()
30
31    visited[now] = True
32    for to in edges[now]:
33        if pre == to:
34            continue
35        dfs(to, now)
36
37# visited[0]は利用しない。
38visited = [False] * (N + 1)
39for i in range(1, N + 1):
40    # visited[i]がTrueの場合、探索を行わない。iから始まる探索を既に終えているため。
41    if not visited[i]:
42        dfs(i)
43
44print('Yes')

2021年12月11日時点のレート画像

プロフィールを確認する

参考文献

• レーティングとは?
• AtCoderのプログラミングコンテストのルール
• 絶対誤差, 相対誤差とは?
• AtCoder株式会社について
• TLEとは?
• 昇順とは?
• 二分探索とは?
• Atcoder 231に関するコードまとめ