作成日 : 2022-02-14
更新日 : 2022-02-15
10 min readAtCoder

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 237」

コンテスト情報

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

配点

ルール

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

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

A -> Not Overflow

問題文

整数Nが与えられます。 Nが−2の31乗以上かつ2の31乗未満ならばYesを、そうでないならばNoを出力してください。

制約

• −2の63乗 ≤ N < 2の63乗
• Nは整数である。

入力

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

1N

出力

Nが−2の31乗以上かつ2の31乗未満ならばYesを、そうでないならばNoを出力せよ。

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

Contest中に考えたこと

• -2の31乗, 2の31乗をpow関数を用いて表現する。
• if文を用いてYes, Noの判定を行う。
• 未満 = 自身の数を含まない。
• 以上 = 自身の数を含む。

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4# -2の31乗, 2の31乗をpow関数を用いて表現する。
5# pow関数とは? : https://himibrog.com/python-pow/
6# if文を用いて`Yes`, `No`の判定を行う。
7# 未満 = 自身の数を含まない。
8# 以上 = 自身の数を含む。
9if pow(-2, 31) <= N and N < pow(2, 31):
10    print('Yes')
11else:
12    print('No')

B -> Matrix Transposition

問題文

H行W列の行列Aが与えられます。Aの上からi行目、左からj列目の要素はAi, jです。ここで、W行H列の行列Bを、上からi行目、左からj列目の要素がAj, iと一致するような行列として定めます。すなわち、BはAの転置行列です。

Bを出力してください。

制約

• 1 ≤ H, W ≤ 10の5乗
• H × W ≤ 10の5乗
• 1 ≤ Ai, j ≤ 10の9乗
• 入力は全て整数である

入力

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

1H W
2A1,1 A1,2 … A1,W
3A2,1 A2,2 … A2,W
4⋮
5AH,1 AH,2 … AH,W

出力

Bを以下の形式で出力せよ。

1B1,1 B1,2 … B1,H
2B2,1 B2,2 … B2,H
3⋮
4BW,1 BW,2 … BW,H

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

Contest中に考えたこと

• D問題と勘違いして解答しませんでした。。

解答

1# 標準入力を受け付ける。
2H, W = map(int, input().split())
3
4A = []
5for _ in range(H):
6    A.append(list(map(int, input().split())))
7
8# 転置行列なので、行と列の長さを反転させる。 = ループの順序を反転させる。
9for i in range(W):
10    tmp = []
11    # 転置行列なので、行の探索ではなく列の探索を行う。
12    for j in range(H):
13        tmp.append(str(A[j][i]))
14
15    print(' '.join(tmp))

C -> kasaka

問題文

英小文字からなる文字列Sが与えられます。Sの先頭にaをいくつか（0個でも良い）つけ加えて回文にすることができるか判定してください。

ただし、長さNの文字列A = A1 A2 … ANが回文であるとは、すべての1 ≤ i ≤ NについてAi = AN + 1 − iが成り立っていることをいいます。

制約

• 1 ≤ ∣S∣ ≤ 10の6乗
• Sは英小文字のみからなる。

入力

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

1S

出力

Sの先頭にaをいくつかつけ加えて回文にすることができるならばYesを、そうでないならばNoを出力せよ。

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

解答

1# <回文になるための条件>
2# 文字列Sは、全て`a`である場合
3# 文字列Sは元から回文である場合
4# 文字列Sの左側と右側にある、連続するaの個数を等しくして、回文である場合
5
6# 標準入力を受け付ける。
7S = input()
8
9# 文字列Sは、全て`a`である場合
10if S.count('a') == len(S):
11    print('Yes')
12    exit()
13
14# 文字列Sは元から回文である場合
15# 回文の判定方法 : https://www.delftstack.com/ja/howto/python/python-palindrome/
16if S == S[::-1]:
17    print('Yes')
18    exit()
19
20SLen = len(S)
21
22# 文字列Sの右側から、何個連続してaが続いているか数える。
23right_a_count = 0
24while S[SLen - 1] == 'a':
25    SLen -= 1
26    right_a_count += 1
27
28# 文字列Sの左側から、何個連続してaが続いているか数える。
29left_a_count = 0
30while S[left_a_count] == 'a':
31    left_a_count += 1
32
33# 文字列Sの左側へ、連続するaを追加する。左側と右側にある、連続するaの個数を等しくする。
34# 同じ文字列を複数回繰り返す方法 : https://it-engineer-info.com/language/python/repeat-string
35S = ('a' * (right_a_count - left_a_count)) + S
36
37# 文字列Sの左側と右側にある、連続するaの個数を等しくして、回文である場合
38if S == S[::-1]:
39    print('Yes')
40else:
41    print('No')

D -> LR insertion

問題文

1個の0のみからなる数列A = (0)があります。また、LとRのみからなる長さNの文字列S = s1 s2 … sNが与えられます。

i = 1, 2, …, Nの順番で、次の操作を行います。

• siがLのとき、A内にあるi − 1のすぐ左にiを挿入する
• siがRのとき、A内にあるi − 1のすぐ右にiを挿入する

最終的なAを求めてください。

制約

• 1 ≤ N ≤ 5 × 10の5乗
• Nは整数である
• ∣S∣ = N
• siはLかRのいずれかである

入力

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

1N
2S

出力

最終的なAを空白区切りで出力せよ。

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

解答

1# <方針>
2# i − 1のすぐ左 or 右にiを挿入する。 ⏩ i − 1とiは隣り合っている。 ⏩ 両端キューを活用する。
3# 両端キューとは? : https://www.weblio.jp/content/%E4%B8%A1%E7%AB%AF%E3%82%AD%E3%83%A5%E3%83%BC#:~:text=%E4%B8%A1%E7%AB%AF%E3%82%AD%E3%83%A5%E3%83%BC%EF%BC%88%E3%82%8A%E3%82%87%E3%81%86%E3%81%9F%E3%82%93%E3%82%AD%E3%83%A5%E3%83%BC,%E5%89%8A%E9%99%A4%E3%81%A7%E3%81%8D%E3%82%8B%E3%82%AD%E3%83%A5%E3%83%BC%E3%81%A7%E3%81%82%E3%82%8B%E3%80%82
4
5from collections import deque
6
7# 標準入力を受け付ける。
8N = int(input())
9S = input()
10
11# deque参考 : https://note.nkmk.me/python-collections-deque/
12d = deque([str(N)])
13
14for i in range(N):
15    num = N - i - 1
16    if S[num] == 'L':
17        d.append(str(num))
18    else:
19        d.appendleft(str(num))
20
21print(' '.join(list(d)))

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

プロフィールを確認する

参考文献

• レーティングとは?
• AtCoderのプログラミングコンテストのルール
• AtCoder株式会社について
• pow関数とは?
• 転置行列とは?
• 回文とは?
• Atcoder 237に関するコードまとめ