KURORO BLOGのロゴ

このエントリーをはてなブックマークに追加
【備忘録】AtCoder Beginner Contest 234 A~D問題

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

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

目次
  1. そもそもAtCoderとは?
  2. 「AtCoder Beginner Contest 234」
    1. コンテスト情報
    2. 配点
    3. ルール
  3. A -> Weird Function
    1. 問題文
    2. 制約
    3. 入力
    4. 出力
    5. Contest中に考えたこと
    6. 解答
  4. B -> Longest Segment
    1. 問題文
    2. 制約
    3. 入力
    4. 出力
    5. Contest中に考えたこと
    6. 解答
  5. C -> Happy New Year!
    1. 問題文
    2. 制約
    3. 入力
    4. 出力
    5. Contest中に考えたこと
    6. 解答
  6. D -> Prefix K-th Max
    1. 問題文
    2. 制約
    3. 入力
    4. 出力
    5. Contest中に考えたこと
    6. 解答
  7. 参考文献
目次を開く⬇︎

執筆者 - おすすめの記事3選

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 234」

コンテスト情報

配点

問題点数
A                100                 
B200
C300
D400
E500
F500
G600
H600

ルール

  1. コンテスト中に問題に正解すると点数を獲得できます。
  2. 順位は総合得点で決定します。
  3. 同点の場合は提出時間の早い人が上の順位になります。
  4. 誤答を提出するたびにペナルティが加算されます。このコンテストのペナルティは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日時点のレート画像

プロフィールを確認する

参考文献

記事に関するお問い合わせ