8 min readAtCoder
【備忘録】AtCoder Beginner Contest 234 A~D問題
AtCoder Beginner Contest 234のA~D問題に関して、問題文からContest中に考えたこと、解答等を備忘録としてまとめました。是非最後までご一読ください。
- そもそもAtCoderとは?
- 「AtCoder Beginner Contest 234」
- A -> Weird Function
- B -> Longest Segment
- C -> Happy New Year!
- D -> Prefix K-th Max
- 参考文献
執筆者 - おすすめの記事3選
そもそもAtCoderとは?
AtCoderを一言で表すと、オンラインで参加できるプログラミングコンテスト(競技プログラミング)サイトになります。リアルタイムのコンテストで競い合ったり、約3000問のコンテストの過去問に、いつでも挑戦出来ることが魅力です。
今回は 「AtCoder Beginner Contest 234」のプログラミングコンテストへ参加しました。
「AtCoder Beginner Contest 234」
コンテスト情報
- コンテスト時間 : 100分
- レーティング更新対象 : 0 - 1999
配点
| 問題 | 点数 |
|---|---|
| A | 100 |
| B | 200 |
| C | 300 |
| D | 400 |
| E | 500 |
| F | 500 |
| G | 600 |
| H | 600 |
ルール
- コンテスト中に問題に正解すると点数を獲得できます。
- 順位は総合得点で決定します。
- 同点の場合は提出時間の早い人が上の順位になります。
- 誤答を提出するたびにペナルティが加算されます。このコンテストのペナルティは5分です。(ルールに関して詳しくみる)
このコンテストは「コンテスト中に提出された結果」だけで順位が決定します。
A -> Weird Function
問題文
関数fをf(x) = xの2乗 + 2x + 3と定義します。整数tが入力されるので、f(f(f(t) + t) + f(f(t)))を求めてください。ただし、答えは2 × 10の9乗以下の整数であることが保証されます。
制約
- tは0以上10以下の整数である
入力
入力は以下の形式で標準入力から与えられる。
1t出力
答えを整数として出力せよ。
本問題は、AtCoder株式会社で作成された、A - Weird Function問題を参照しております。
Contest中に考えたこと
- f(x) = xの2乗 + 2x + 3を求める関数を用意する。
- f(f(f(t) + t) + f(f(t)))の結果を出力する。
解答
1# f(x) = xの2乗 + 2x + 3を求める関数を用意する。
2def func(x):
3 return x * x + 2 * x + 3
4
5# 標準入力を受け付ける。
6t = int(input())
7# f(f(f(t) + t) + f(f(t)))の結果を出力する。
8print(func(func(func(t) + t) + func(func(t))))B -> Longest Segment
問題文
二次元平面上にN個の点があります。i個目の点の座標は(xi, yi)です。この中から2個の点を選ぶとき、それらを結ぶ線分の長さの最大値を求めてください。
制約
- 2 ≤ N ≤ 100
- −1000 ≤ xi, yi ≤ 1000
- (xi, yi) != (xj, yj) (i != j)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
1N
2x1 y1
3x2 y2
4⋮
5xN yN
出力
2点を結ぶ線分の長さの最大値を出力せよ。想定解との絶対誤差または相対誤差が10の−6乗以下であれば正解とみなされる。
本問題は、AtCoder株式会社で作成された、B - Longest Segment問題を参照しております。
Contest中に考えたこと
- 2点の選び方を全通り試して問題ないか考える。 ⏩ Nを100として、2点の選び方を全通り試すと99, 98, 97, ... , 2, 1通りの足し算となる。(100 * 49 + 50) = 4950通りとなる = 全通り試しても問題ない。
- ある2点間の距離を求めて、最大値を出力する。
解答
1import math
2
3# 標準入力を受け付ける。
4N = int(input())
5
6position_list = []
7for _ in range(N):
8 x, y = map(int, input().split())
9 position_list.append((x, y))
10
11ans = 0
12for i in range(N - 1):
13 for j in range(i + 1, N):
14 x1, y1 = position_list[i]
15 x2, y2 = position_list[j]
16 # ある2点間の距離を求める。
17 ans = max(ans, math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2))
18
19# 最大値を出力する。
20print(ans)C -> Happy New Year!
問題文
10進法で表記したときに0, 2のみからなる正整数のうち、K番目に小さいものを求めてください。
制約
- Kは1以上10の18乗以下の整数
入力
入力は以下の形式で標準入力から与えられる。
1K出力
答えを整数として出力せよ。ただし、たとえ答えが大きな整数であっても、求める答えを正確に整数として出力する必要がある。たとえば、 2.34e+22のような指数表記や、0523のような先頭に不要な0を付けたような表記は許されない。
本問題は、AtCoder株式会社で作成された、C - Happy New Year!問題を参照しております。
Contest中に考えたこと
- Kを2進数表記にする。
- 2進数表記したKの値の、1の部分を2に変更する。
解答
1# 標準入力を受け付ける。
2K = int(input())
3
4# Kを2進数表記にする。
5# 2進数表記したKの値の、1の部分を2に変更する。
6# 参考 : https://note.nkmk.me/python-bin-oct-hex-int-format/
7print(str(bin(K)[2:]).replace('1', '2'))D -> Prefix K-th Max
問題文
(1, 2, …, N)の順列P = (P1, P2, …, PN)、および正整数Kが与えられます。i = K, K + 1, …, Nについて、以下を求めてください。
- Pの先頭i項のうち、K番目に大きい値
制約
- 1 ≤ K ≤ N ≤ 5 × 10の5乗
- (P1, P2, …, PN)は(1, 2, …, N)の並び替えによって得られる
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
1N K
2P1 P2 … PN
出力
i = K, K + 1, …, Nについてこの順に、問題文中で問われている値を改行区切りで出力せよ。
本問題は、AtCoder株式会社で作成された、D - Prefix K-th Max問題を参照しております。
Contest中に考えたこと
- 問題文を読んで終了しました。。
解答
1import heapq
2
3# 標準入力を受け付ける。
4N, K = map(int, input().split())
5
6P = list(map(int, input().split()))
7
8H = []
9for i in range(K):
10 heapq.heappush(H, P[i])
11
12# P0~PK項のうち、K番目に大きい値を格納する。
13ans = [str(H[0])]
14for i in range(K, N):
15 heapq.heappush(H, P[i])
16 # 配列の個数を毎度K個にする。
17 # K番目より小さい値を取り除く。
18 heapq.heappop(H)
19 # P0~Pi項のうち、K番目に大きい値を格納する。
20 ans.append(str(H[0]))
21
22print("\n".join(ans))2022年1月8日時点のレート画像
