作成日 : 2021-12-02
更新日 : 2021-12-02
10 min readAtCoder

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 229」

コンテスト情報

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

配点

ルール

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

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

A -> First Grid

問題文

縦2行、横2列のグリッド(各マスが正方形のマス目)があります。このグリッドは、各マスが黒か白であり、少なくとも2つの黒マスを含みます。各マスの色の情報は文字列S1, S2として、以下の形式で与えられます。

• 文字列Siのj文字目が#であれば上からiマス目、左からjマス目は黒
• 文字列Siのj文字目が.であれば上からiマス目、左からjマス目は白

2つの異なる黒マス同士が辺で接している時、またその時に限りそれら2つの黒マスは直接行き来できます。黒マスのみをいくつか通ることによって、どの2つの黒マス同士も(直接または間接的に)行き来できるかどうか判定してください。

制約

• S1, S2は#または.からなる2文字の文字列
• S1, S2に#が合計で2つ以上含まれる

入力

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

1S1
2​S2

出力

どの2つの黒マス同士も行き来できるならYes、そうでないならNoと出力せよ。

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

Contest中に考えたこと

• 各マスの情報を変数に格納する。
• 各マスが黒の場合に、辺で繋がるマスが黒であるかどうか確認する。

解答

1# 標準入力を受け付ける。
2s1 = input()
3s2 = input()
4
5# 左上のマス
6s1_1 = s1[0]
7# 右上のマス
8s1_2 = s1[1]
9
10# 左下のマス
11s2_1 = s2[0]
12# 右下のマス
13s2_2 = s2[1]
14
15# 左上のマスが黒の場合に、左下のマスと右上のマスが黒かどうかを確認する。
16if s1_1 == '#' and (s1_2 != '#' and s2_1 != '#'):
17    print('No')
18    exit()
19
20# 右上のマスが黒の場合に、左上のマスと右下のマスが黒かどうかを確認する。
21if s1_2 == '#' and (s1_1 != '#' and s2_2 != '#'):
22    print('No')
23    exit()
24
25# 左下のマスが黒の場合に、左上のマスと右下のマスが黒かどうかを確認する。
26if s2_1 == '#' and (s1_1 != '#' and s2_2 != '#'):
27    print('No')
28    exit()
29
30# 右下のマスが黒の場合に、左下のマスと右上のマスが黒かどうかを確認する。
31if s2_2 == '#' and (s1_2 != '#' and s2_1 != '#'):
32    print('No')
33    exit()
34
35print('Yes')

B -> Hard Calculation

問題文

正整数A, Bが与えられます。A + Bを(十進法で)計算する時、繰り上がりが生じないならEasy、生じるならHardと出力してください。

制約

• A, Bは整数
• 1 ≤ A, B ≤ 10の18乗

入力

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

1A B

出力

繰り上がりが生じないならEasy、生じるならHardと出力せよ。

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

Contest中に考えたこと

• A, Bの数字を確認して、桁数の少ない数字に対して、0埋めを行う。
• A, Bの数字の各桁を足し合わせて10以上になるかどうか確認する。10以上になる場合、Hard, そうでない場合Easyと出力する。

解答

1# 標準入力を受けつける。
2A, B = map(str, input().split())
3
4# A, Bの数字を確認して、桁数の少ない数字に対して、0埋めを行う。
5# 参考 : https://note.nkmk.me/python-zero-padding/
6if len(A) > len(B):
7    B = B.zfill(len(A))
8
9# A, Bの数字を確認して、桁数の少ない数字に対して、0埋めを行う。
10# 参考 : https://note.nkmk.me/python-zero-padding/
11if len(B) > len(A):
12    A = A.zfill(len(B))
13
14N = len(A)
15for i in range(N):
16    a = int(A[N - i - 1])
17    b = int(B[N - i - 1])
18
19    # A, Bの数字の各桁を足し合わせて10以上になるかどうか確認する。10以上になる場合、Hard, そうでない場合Easyと出力する。
20    if a + b >= 10:
21        print('Hard')
22        exit()
23
24print('Easy')

C -> Cheese

問題文

ピザ屋で働く高橋くんは、まかないとして美味しいチーズピザを作ることにしました。今、高橋くんの目の前にN種類のチーズがあります。

i種類目のチーズは1[g]あたりのおいしさがAiで、Bi[g]あります。ピザのおいしさは、ピザに乗せたチーズのおいしさの総和で決まります。

但し、チーズを使いすぎると怒られてしまうため、乗せたチーズの重さは合計でW[g]以下である必要があります。

この条件のもとで、可能なピザのおいしさの最大値を求めてください。

制約

• 入力は全て整数
• 1 ≤ N ≤ 3 × 10の5乗
• 1 ≤ W ≤ 3 × 10の8乗
• 1 ≤ Ai ≤ 10の9乗
• 1 ≤ Bi ≤ 1000

入力

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

1N W
2A1 B1
3A2 B2
4⋮
5AN BN

出力

答えを整数として出力せよ。

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

Contest中に考えたこと

• 1[g]あたりのおいしさが大きい、チーズから乗せていく。
• チーズの重さの合計がWになるまで、チーズを乗せていく。

解答

1# 標準入力を受け付ける。
2N, W = map(int, input().split())
3
4data = []
5for _ in range(N):
6    A, B = map(int, input().split())
7    data.append((A, B))
8
9# N種類のチーズを、1[g]あたりのおいしさが、大きい順に並べ替える。
10data.sort(reverse=True)
11
12ans = 0
13for d in data:
14    # チーズの重さの合計を超える場合。
15    if W - d[1] < 0:
16        ans += (d[0] * W)
17        break
18    # チーズの重さの合計を超えていない場合。
19    else:
20        W -= d[1]
21        ans += (d[0] * d[1])
22
23print(ans)

D -> Longest X

問題文

Xと.からなる文字列Sが与えられます。

Sに対して、次の操作を0回以上K回以下行うことができます。

• .をXに置き換える

操作後に、Xを最大で何個連続させることができますか？

制約

• 1 ≤ | S | ≤ 2 × 10の5乗
• Sの各文字はXまたは.である
• 0 ≤ K ≤ 2 × 10の5乗
• Kは整数である

入力

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

1S
2K

出力

答えを出力せよ。

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

Contest中に考えたこと

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

解答

1# 標準入力を受け付ける。
2S = input()
3
4K = int(input())
5
6N = len(S)
7
8# Sのある番目の文字が登場した時に、左から.の文字が何回出現したのかメモする変数。
9cnt_dot = []
10for _ in range(N + 1):
11    cnt_dot.append(0)
12
13for i in range(N):
14    if S[i] == '.':
15        cnt_dot[i + 1] += cnt_dot[i] + 1
16    else:
17        cnt_dot[i + 1] += cnt_dot[i]
18
19ans = 0
20r = 0
21for l in range(N):
22    # .の数がKよりも少ない間まで、rの更新を行う。
23    while r < N and cnt_dot[r + 1] - cnt_dot[l] <= K:
24        r += 1
25    ans = max(ans, r - l)
26
27print(ans)

参考文献

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