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

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 230」

コンテスト情報

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

配点

ルール

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

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

A -> AtCoder Quiz 3

問題文

AtCoderで定期的に開催されている、国際的な権威があるコンテストであるAtCoder Grand Contest(以下、AGC)は今までに54回開催されてきました。

みなさんがちょうど参加している230回目のABCであるABC230と同様に、 当初はN回目のAGCのコンテスト名にはNを3桁になるようにゼロ埋めした数が割り振られていました。(1回目のAGCはAGC001, 2回目のAGCはAGC002, ...)

ところが、最新の54回目のAGCのコンテスト名はAGC055で、回数より1大きい数が割り振られています。これは、AGC042が社会情勢の影響で中止されて欠番となったため、42回目以降に開催されたコンテストでは開催された回数より1大きい数が割り振られているからです。(入出力例にある説明も参考にしてください。)

さて、ここで問題です。整数Nが与えられるので、N回目に開催されたAGCのコンテスト名をAGCXXXの形式で出力してください。ここで、XXXにはゼロ埋めがなされた3桁の数が入ります。

制約

• 1 ≤ N ≤ 54
• Nは整数である。

入力

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

1N

出力

N回目に開催されたAGCのコンテスト名を所定の形式で出力せよ。

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

Contest中に考えたこと

• 42回目以降のコンテストに関して、+1して出力を行う。
• ゼロ埋めを行う。

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4if N >= 42:
5    N += 1
6
7# zfill参考 : https://note.nkmk.me/python-zero-padding/
8print('AGC' + str(N).zfill(3))

B -> Triple Metre

問題文

文字列Sが文字列Tの部分文字列であるとは、次の条件を満たすような整数i, j(1 ≤ i ≤ j ≤ ∣T∣)が存在することを言います。

• Tのi文字目からj文字目までを順番を変えずに抜き出してできる文字列がSと一致する。

文字列Tをoxxを10の5乗個結合した文字列として定めます。文字列Sが与えられるので、SがTの部分文字列である場合はYesを、そうでない場合はNoを出力してください。

制約

• Sはoとxのみからなる文字列である。
• Sの長さは1以上10以下である。

入力

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

1S

出力

Sが条件を満たす場合はYesを、そうでない場合はNoを出力せよ。

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

Contest中に考えたこと

• Sの文字列の長さが1の場合を考える。xが出てもoが出てもTの部分文字列になるので、Yesと出力する。
• Sの文字列の長さが2の場合を考える。Sの1文字目, 2文字目にoが出た場合に、Tの部分文字列にならないので、Noと出力する。それ以外の場合は、Yesと出力する。
• Sの文字列の長さが3以上の場合を考える。Sの1文字目の値に応じて、Sの2文字目, Sの3文字目が正しいかどうか検証する。

解答

1# 標準入力を受け付ける。
2S = input()
3
4N = len(S)
5
6# Sの文字列の長さが1の場合を考える。`x`が出ても`o`が出てもTの部分文字列になるので、`Yes`と出力する。
7if N == 1:
8    print('Yes')
9    exit()
10
11# Sの文字列の長さが2の場合を考える。Sの1文字目, 2文字目に`o`が出た場合に、Tの部分文字列にならないので、`No`と出力する。それ以外の場合は、`Yes`と出力する。
12if N == 2:
13    if S[0] == 'o' and S[1] == 'o':
14        print('No')
15        exit()
16    else:
17        print('Yes')
18        exit()
19
20# Sの文字列の長さが3以上の場合を考える。Sの1文字目の値に応じて、Sの2文字目, Sの3文字目が正しいかどうか検証する。
21first = S[0]
22second = S[1]
23third = S[2]
24
25# Sの1文字目が`o`の時、Sの2文字目, 3文字目のどちらかで`o`が出るとTの部分文字列にならないので、`No`と出力する。
26if first == 'o' and (second == 'o' or third == 'o'):
27    print('No')
28    exit()
29
30# Sの1文字目が`x`の時、Sの2文字目, 3文字目がどちらも`o`の場合、もしくはSの2文字目, 3文字目がどちらも`x`の場合に、Tの部分文字列にならないので、`No`と出力する。
31if first == 'x' and ((second == 'o' and third == 'o') or (second == 'x' and third == 'x')):
32    print('No')
33    exit()
34
35# Sの4文字目以降について考える。Sの1~3文字目の繰り返しになっているか確かめる。
36for i in range(3, N):
37    if i % 3 == 0 and first != S[i]:
38        print('No')
39        exit()
40
41    if i % 3 == 1 and second != S[i]:
42        print('No')
43        exit()
44
45    if i % 3 == 2 and third != S[i]:
46        print('No')
47        exit()
48
49print('Yes')

C -> X drawing

問題文

上下左右に広がるN × Nのマス目があり、最初全てのマスは白く塗られています。このマス目の上からi 行目、左からj列目のマスを(i, j)で表します。

高橋君は1以上N以下の整数A, Bを持っており、次のような操作を行います。

• max(1 − A, 1 − B) ≤ k ≤ min(N − A, N − B)をみたす全ての整数kについて、(A + k, B + k)を黒く塗る。
• max(1 − A, B − N) ≤ k ≤ min(N − A, B − 1)をみたす全ての整数kについて、(A + k, B − k)を黒く塗る。

この操作を行った後のマス目について、P ≤ i ≤ QかつR ≤ j ≤ Sをみたす各マス(i, j)がそれぞれ何色で塗られているか求めてください。

制約

• 1 ≤ N ≤ 10の18乗
• 1 ≤ A ≤ N
• 1 ≤ B ≤ N
• 1 ≤ P ≤ Q ≤ N
• 1 ≤ R ≤ S ≤ N
• (Q − P + 1) × (S − R + 1) ≤ 3 × 10の5乗
• 入力は全て整数である。

入力

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

1N A B
2P Q R S

出力

Q − P + 1行出力せよ。各行は#と.のみからなる長さS − R + 1の文字列であり、i行目の文字列のj番目の文字が#であることは(P + i − 1, R + j − 1)が黒く塗られていることを、.であることは(P + i − 1, R + j − 1)が白く塗られていることをさす。

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

Contest中に考えたこと

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

解答

1# 標準入力を受け付ける。
2N, A, B = map(int, input().split())
3
4P, Q, R, S = map(int, input().split())
5
6for i in range(P, Q + 1):
7    text = ''
8    for j in range(R, S + 1):
9        # 黒になる場合を考える。
10        # <黒になる場合>
11        # (A + k, B + k)が(i, j)である。もしくは(A + k, B − k)が(i, j)である。
12        #
13        # 上記の条件のもと、式を作成する。
14        # A + k = i, B + k = j ⏩ k = i - A, k = j - B ⏩ i - A = j - B ⏩ i - j - A + B = 0の時、黒である。
15        # A + k = i, B - k = j ⏩ k = i - A, k = B - j ⏩ i - A = B - j ⏩ i - A - B + j = 0の時、黒である。
16        if (i - j - A + B == 0) or (i - A - B + j == 0):
17            text += '#'
18        else:
19            text += '.'
20    print(text)

D -> Destroyer Takahashi

問題文

N行10の9乗列の格子状の区画に区切られた街にN枚の壁があり、1からNまでの番号が割り振られています。壁iは上からi行目、左からLi列目からRi列目の範囲にあります。(入出力例1の図も参考にしてください。)

高橋君はN枚の壁をすべて破壊することにしました。超人的な腕力を持つ高橋君は、1回のパンチで連続するD列にまとめてダメージを与えることができます。

• より厳密に言い換えると、1以上10の9乗 − D + 1以下の整数xを選んで、x列目からx + D − 1列目に (一部でも)存在するすべての破壊されていない壁にパンチによるダメージを与えることができます。

壁は一部分でもダメージを受けると、パンチの衝撃波により全体が木っ端みじんに破壊されてしまいます。(入出力例1の説明も参考にしてください。)

高橋君がすべての壁を破壊するには、少なくとも何回のパンチを放つ必要がありますか？

制約

• 1 ≤ N ≤ 2 × 10の5乗
• 1 ≤ D ≤ 10の9乗
• 1 ≤ Li ≤ Ri ≤ 10の9乗
• 入力はすべて整数である。

入力

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

1N D
2L1 R1
3L2 R2
4⋮
5LN RN

出力

すべての壁を破壊するのに必要なパンチの最少回数を出力せよ。

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

解答

1################################
2# <方針>
3# なるべく1度のパンチで多くの壁を壊したい。 ⏩ どの列にパンチを加えるべきか考える。
4# 以下の処理を繰り返す。
5# 1. 左の列から見た場合に、壁の右端が最初に現れる壁に注目する。
6# 2. 上記の壁の右端へパンチを加える。 ⏩ 上記の壁の右端以外にパンチするよりも、右端へパンチした方が重複して壁を壊せる確率が上がるため。
7# 3. パンチにより、壊れた壁を除いた、残りの壁に対して、左の列から見た場合に、壁の右端が最初に現れる壁に注目する。2と3を繰り返す。
8#
9# 左の列から見た場合に、壁の右端が最初に現れる壁を容易に探索するために、どうすべきか? ⏩ 事前に壁の右端でソートしておく。
10#
11################################
12
13# 標準入力を受け付ける。
14N, D = map(int, input().split())
15
16wallList = []
17
18for _ in range(N):
19    L, R = map(int, input().split())
20    wallList.append((L, R))
21
22wallList.sort(key=lambda x: x[1])
23
24# パンチの数。
25punch_cnt = 1
26# パンチにより壁を壊すことのできる範囲。
27punch_right = wallList[0][1] + D - 1
28for i in range(1, N):
29    # パンチにより続けて壁を壊せる場合、continueを行う。
30    if wallList[i][0] <= punch_right:
31        continue
32
33    # パンチにより壁を壊すことのできる範囲。
34    punch_right = wallList[i][1] + D - 1
35    punch_cnt += 1
36
37print(punch_cnt)

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

プロフィールを確認する

参考文献

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