作成日 : 2022-01-16
更新日 : 2022-01-16
10 min readAtCoder

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 235」

コンテスト情報

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

配点

ルール

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

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

A -> Rotate

問題文

3つの数字x, y, zをこの順に並べてできる3桁の整数をxyzと表すことにします。どの桁も0でない3桁の整数abcが与えられるので、abc + bca + cabを求めてください。

制約

• abcはどの桁も0でない3桁の整数

入力

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

1abc

出力

答えを出力せよ。

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

Contest中に考えたこと

• abcはどの桁も0でない3桁の整数 = 0が先頭に来ることはないため、abc, bca, cabは必ず整数となる。
• abcの入力を文字列として考える。
• 1番目の文字列の値をa, 2番目の文字列の値をb, 3番目の文字列の値をcとする。
• 計算式の通りに出力する。

解答

1# 標準入力を受け付ける。
2# abcの入力値を文字列として考える。
3s = input()
4
5# 1番目の文字列の値をa, 2番目の文字列の値をb, 3番目の文字列の値をcとする。
6a = s[0]
7b = s[1]
8c = s[2]
9 
10# 計算式の通りに出力する。 
11# ※ 文字列連結と加算の違いに注意する。
12print(int(a + b + c) + int(b + c + a) + int(c + a + b))

B -> Climbing Takahashi

問題文

N個の台が一列に並んでおり、左からi番目の台の高さはH(i)です。

高橋君は最初、左端の台の上に立っています。高橋君は高い所が好きなので、次のルールで可能な限り移動を繰り返します。

• いま立っているのが右端の台ではなく、かつ、右隣にある台の高さが自分がいま立っている台より高いとき、右隣の台に移動する

最終的に高橋君が立っている台の高さを求めてください。

制約

• 2 ≤ N ≤ 10の5乗
• 1 ≤ H(i) ≤ 10の9乗
• 入力に含まれる値は全て整数である

入力

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

1N
2H(1) … H(N)

出力

答えを出力せよ。

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

Contest中に考えたこと

• 左から順番に台を見ていく。
• H(i)の台とH(i + 1)の台を比較する。
• H(i) >= H(i + 1)の場合、Hiの値を答えとして出力する。
• H(i) < H(i + 1)の場合、次の右の台を確認する。

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4h_list = list(map(int, input().split()))
5
6ans = 0
7# 左から順番に台を見ていく。
8for h in h_list:
9    # H(i)の台とH(i + 1)の台を比較する。
10    # H(i) < H(i + 1)の場合、次の右の台を確認する。
11    if ans < h:
12        ans = h
13    else:
14        break
15
16# H(i) >= H(i + 1)の場合、H(i)の値を答えとして出力する。
17print(ans)

C -> The Kth Time Query

問題文

長さNの数列A = (a1, a2, …, aN)があります。以下で説明されるQ個のクエリに答えてください。

• クエリi : 整数の組(xi, ki)が与えられます。Aの要素をa1, a2, …と前から順に見ていったときに、数xiがki回目に登場するのはAの前から何番目の要素を見たときかを出力してください。

ただし条件を満たす要素が存在しない場合は−1を出力してください。

制約

• 1 ≤ N ≤ 2 × 10の5乗
• 1 ≤ Q ≤ 2 × 10の5乗
• 0 ≤ ai ≤ 10の9乗(1 ≤ i ≤ N)
• 0 ≤ xi ≤ 10の9乗(1 ≤ i ≤ Q)
• 1 ≤ ki ≤ N(1 ≤ i ≤ Q)
• 入力はすべて整数である。

入力

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

1N Q
2a1 a2 … aN
3​x1 k1
4x2 k2 
5⋮
6xQ kQ

出力

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

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

Contest中に考えたこと

• dict型を用いて、数列を管理する。
• クエリのxが、数列に格納される数字を選択しなかった場合は、-1を出力する。
• k - 1 >= 数列の中にあるxの数だった場合、-1を出力する。

解答

1# 標準入力を受け付ける。
2N, Q = map(int, input().split())
3
4A = list(map(int, input().split()))
5
6# dict型を用いて、数列を管理する。
7# key : [num1, num2, ...]でデータ格納する。
8# keyには、数列に格納される数字が入る。
9# [num1, num2, ...]には、keyが数列内で登場する、位置を格納する。
10number_list = {}
11
12for i in range(len(A)):
13    if number_list.get(A[i]) is None:
14        # i + 1は配列のidxを考慮するため。
15        number_list[A[i]] = [i + 1]
16    else:
17        # i + 1は配列のidxを考慮するため。
18        number_list[A[i]].append(i + 1)
19
20for _ in range(Q):
21    x, k = map(int, input().split())
22
23    # クエリのxが、数列に格納される数字を選択しなかった場合は、-1を出力する。
24    if number_list.get(x) is None:
25        print(-1)
26        continue
27
28    # k - 1 >= 数列の中にあるxの数だった場合、-1を出力する。
29    # k - 1なのは、配列のidxを考慮するため。
30    if k - 1 >= len(number_list[x]):
31        print(-1)
32        continue
33
34    print(number_list[x][k - 1])

D -> Multiply and Rotate

問題文

正の整数aがあります。また、黒板に1個の数が10進表記で書かれています。黒板に現在書かれている数をxとしたとき、高橋君は次のいずれかの操作を行い、黒板に書かれている数を変化させることができます。

• xを消し、xをa倍した数を10進表記で新たに書きこむ。
• xを文字列とみなして、列の末尾の数字を文字列の先頭に移動させる。ただし、この操作はx ≥ 10かつxが10で割り切れないときにしか行えない。

たとえばa = 2, x = 123であるとき、高橋君は次のいずれかの操作を行うことができます。

• xを消して、x × a = 123 × 2 = 246を新たに書きこむ。
• xを文字列とみなして、123の末尾の数字である3を先頭に移動させる。黒板に書かれている数は123から312に変化する。

はじめ、黒板には1が書かれています。書かれている数をNに変化させるには最小で何回の操作が必要ですか？ただし、どのように操作しても書かれている数をNに変化させられない場合は−1を出力してください。

制約

• 2 ≤ a < 10の6乗
• 2 ≤ N < 10の6乗
• 入力はすべて整数である。

入力

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

1a N

出力

答えを出力せよ。

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

Contest中に考えたこと

• 問題文を読んで終了しました。。

解答

1from collections import deque
2
3# 標準入力を受け付ける。
4a, N = map(int, input().split())
5
6# <方針> #####################
7# どちらかの操作をしてもxの桁数は減少しない。 ⏩ Nの最大値(10の6乗)を超えるまで、操作1, 操作2のどちらかを行い、Nに該当する操作手順が見つかるか考える。
8
9q = deque()
10
11MAX_N = 10 ** 6
12
13dist = [-1] * MAX_N
14
15# 操作をせずに1に訪れたので、0を代入する。
16dist[1] = 0
17
18# 1からスタートするのでキューにその値を格納する。
19q.append(1)
20
21while len(q) > 0:
22    x = q.popleft()
23    tmp = x * a
24
25    # Nの最大値を超えないかつ初めてtmpの値を訪れた場合。
26    # 初めてtmpの値を訪れた場合にするのは、最小の操作回数を求めるため。
27    if tmp < MAX_N and dist[tmp] == -1:
28        dist[tmp] = dist[x] + 1
29        q.append(tmp)
30
31    if x % 10 == 0 or x < 10:
32        continue
33
34    # x >= 10かつxが10で割り切れないときのみ以下の処理を行う。
35
36    tmp = str(x)
37    tmp = int(tmp[-1] + tmp[:-1])
38
39    # Nの最大値を超えないかつ初めてtmpの値を訪れた場合。
40    # 初めてtmpの値を訪れた場合にするのは、最小の操作回数を求めるため。
41    if tmp < MAX_N and dist[tmp] == -1:
42        dist[tmp] = dist[x] + 1
43        q.append(tmp)
44
45print(dist[N])

2022年1月15日時点のレート画像

プロフィールを確認する

参考文献

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