作成日 : 2021-09-20
更新日 : 2021-11-01
12 min readAtCoder

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 219」

コンテスト情報

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

配点

ルール

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

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

A -> AtCoder Quiz 2

問題文

AtCoder王国では、競技プログラミングの実力を測る検定試験が実施されています。

試験は100点満点であり、点数が高ければ高いほど、高いランクが認定されます。

ランクは以下のように定められています。

• 0点以上40点未満のとき、初級
• 40点以上70点未満のとき、中級
• 70点以上90点未満のとき、上級
• 90点以上のとき、エキスパート

高橋君は、この検定試験を受験し、X点を取りました。

高橋君が認定されたランクより一つ高いランクとなるためには最低であと何点必要か求めてください。ただし、高橋君がエキスパートと認定された場合、それより高いランクは存在しないためexpertと出力してください。

制約

• 0 ≤ X ≤ 100
• Xは整数

入力

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

1X

出力

答えを出力せよ。

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

Contest中に考えたこと

• Xの値が90点以上の場合、expertを返す。
• Xの値が0点以上~39点以内の場合、40 - Xの値を返す。
• Xの値が40点以上~69点以内の場合、70 - Xの値を返す。
• Xの値が70点以上~89点以内の場合、90 - Xの値を返す。

解答

1# 標準入力を受け付ける。
2X = int(input())
3
4# Xの値が90点以上の場合、expertを返す。
5if X >= 90:
6    print('expert')
7    exit()
8 
9score = 0
10# Xの値が0点以上~39点以内の場合、40 - Xの値を返す。
11if X >= 0 and X <= 39:
12    score = 40 - X
13# Xの値が40点以上~69点以内の場合、70 - Xの値を返す。
14elif X >= 40 and X <= 69:
15    score = 70 - X
16# Xの値が70点以上~89点以内の場合、90 - Xの値を返す。
17elif X >= 70 and X <= 89:
18    score = 90 - X
19 
20print(score)

B -> Maritozzo

問題文

英小文字からなる3つの文字列S1, S2, S3と、1、2、3のみからなる文字列Tが与えられます。Tの各文字に対応する文字列を連結してできる文字列を出力してください。より厳密には、以下の指示にしたがって文字列を出力してください。

• 1 ≤ i ≤ ∣T∣を満たす整数iに対し、文字列siを次のように定める。
• Tのi文字目が1のとき、S1
• Tのi文字目が2のとき、S2
• Tのi文字目が3のとき、S3
• s1, s2, …, s∣T∣をこの順に連結してできる文字列を出力する。

制約

• 1 ≤ ∣S1∣, ∣S2∣, ∣S3∣ ≤ 10
• 1 ≤ ∣T∣ ≤ 1000
• S1, S2, S3は英小文字からなる。
• Tは1、2、3のみからなる。

入力

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

1S1
2​S2
3​S3
4​T

出力

答えを出力せよ。

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

Contest中に考えたこと

• Tの文字列を1文字単位に分解して、リストへ入れる。
• Tの文字数だけループを回す。
• Tのある文字が1の場合にS1, 2の場合にS2, 3の場合にS3を選択して、文字列連結する。

解答

1# 標準入力を受け付ける。
2s1 = input()
3s2 = input()
4s3 = input()
5# Tの文字列を1文字単位に分解して、リストへ入れる。
6T = list(input())
7 
8ans = ''
9
10# Tの文字数だけループを回す。
11for i in range(0, len(T)):
12    # Tのある文字が1の場合にS1, 2の場合にS2, 3の場合にS3を選択して、文字列連結する。
13    if T[i] == '1':
14        ans = ans + s1
15    elif T[i] == '2':
16        ans = ans + s2
17    elif T[i] == '3':
18        ans = ans + s3
19 
20print(ans)

C -> Neo-lexicographic Ordering

問題文

AtCoder王国を治める高橋君は、英小文字のアルファベット順を変更することにしました。

新たなアルファベット順はa, b, …, zを並べ替えて得られる文字列Xを用いて表されます。Xのi(1 ≤ i ≤ 26)文字目は、新たな順番においてi番目に小さい英小文字を表します。

AtCoder王国にはN人の国民がおり、それぞれの国民の名前はS1, S2, …, SNです。ここで、Si(1 ≤ i ≤ N)は英小文字からなります。

これらの名前を、高橋君の定めたアルファベット順に基づく辞書順に従って並べ替えてください。

辞書順とは? : 辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、英小文字からなる相異なる文字列S, Tの大小を判定するアルゴリズムを以下に説明します。以下では「Sのi文字目の文字」をSiのように表します。また、SがTより辞書順で小さい場合はS < T、大きい場合はS > Tと表します。S, Tのうち長さが大きくない方の文字列の長さをLとします。i = 1, 2, …, Lに対してSiとTiが一致するか調べます。Si ≠ Tiであるiが存在する場合、そのようなiのうち最小のものをjとします。そして、SjとTjを比較して、SjがTjよりアルファベット順で小さい場合は S < T 、そうでない場合はS > Tと決定して、アルゴリズムを終了します。Si ≠ Tiであるiが存在しない場合、S とTの長さを比較して、SがTより短い場合はS < T 、長い場合はS > Tと決定して、アルゴリズムを終了します。

制約

• Xはa, b, …, zを並べ替えて得られる
• 2 ≤ N ≤ 50000
• Nは整数
• 1 ≤ ∣Si∣ ≤ 10(1 ≤ i ≤ N)
• Siは英小文字からなる(1 ≤ i ≤ N)
• Si ≠ Sj(1 ≤ i < j ≤ N)

入力

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

1X
2N
3S1
4​S2
5​⋮
6SN

出力

N行出力せよ。i(1 ≤ i ≤ N)行目には、高橋君の定めたアルファベット順に基づく辞書順に従って国民の名前を並べ替えたとき、i番目に小さいものを出力すること。

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

Contest中に考えたこと

• 新たな辞書順を辞書型にまとめる。({x0 : 1, x1 : 2, ..., Xn : n})
• 国民の名前を、上記の辞書型を利用して、数値化する。
• 数値化した国民の名前をソートする。
• ソートされた順序で国民の名前を出力する。サンプルテストはうまく行ったが、その他のテストケースがうまくいかなかった。ここで終了。

学んだこと

• Pythonのsort関数は、多次元配列に対応している。
• Pythonのsort関数は、第一引数へリストを格納してもソートしてくれる。

解答

1# 標準入力を受け付ける。
2X = list(input())
3N = int(input())
4
5# 新しい辞書順を作成する。
6alphaDict = {}
7for i in range(0, len(X)):
8    alphaDict[X[i]] = i + 1
9
10SList = []
11for i in range(0, N):
12    name = input()
13    nameNum = []
14    for j in range(0, len(name)):
15        # 新しい辞書順を元に、名前の英小文字に対応する番号を格納する。
16        nameNum.append(alphaDict[name[j]])
17
18    SList.append([nameNum, name])
19
20# 名前の英小文字に対応する番号をソートする。
21SList.sort()
22
23for i in range(0, N):
24    print(SList[i][1])

D -> Strange Lunchbox

問題文

N種類の弁当が、それぞれ1個ずつ売られています。i = 1, 2, …, Nについて、i種類目の弁当にはAi個のたこ焼きとBi個のたい焼きが入っています。

高橋君は、X個以上のたこ焼きとY個以上のたい焼きを食べたいです。

高橋君がいくつかの弁当を選んで買うことで、X個以上のたこ焼きとY個以上のたい焼きを手に入れることが可能かどうか判定して下さい。また、可能な場合はそのために高橋君が購入しなければならない弁当の個数の最小値を求めて下さい。

各種類の弁当は1個しか売られていないため、同じ種類の弁当を2個以上購入することは出来ないことに注意して下さい。

制約

• 1 ≤ N ≤ 300
• 1 ≤ X, Y ≤ 300
• 1 ≤ Ai, Bi ≤ 300
• 入力はすべて整数

入力

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

1N
2X Y
3A1 B1
4​A2 B2
5​⋮
6AN BN

出力

高橋君がX個以上のたこ焼きとY個以上のたい焼きを手に入れることが不可能な場合は−1を出力し、可能な場合はそのために高橋君が購入しなければならない弁当の個数の最小値を出力せよ。

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

解答

1INF = 1000
2
3# 標準入力を受け付ける。
4N = int(input())
5X, Y = map(int, input().split())
6
7# i番目の弁当を食べた場合に、X, Yの目標に到達しているのか記録する。
8# 途中経過も取得できるように動的計画法を利用する。
9dp = [[[INF] * (Y + 1) for _ in range(X + 1)] for _ in range(N + 1)]
10
11bentoList = []
12for _ in range(N):
13    a, b = map(int, input().split())
14    bentoList.append((a, b))
15
16# 初期設定を行う。
17dp[0][0][0] = 0
18
19for i in range(N):
20    x, y = bentoList[i]
21    for j in range(X + 1):
22        # X以上の配列Indexを参照しないように、minを実行する。
23        jj = min(j + x, X)
24        for k in range(Y + 1):
25            # 弁当を食べない場合、i番目の状態をi + 1番目へ引き継ぐ。
26            # 下のコードにより、弁当を食べていて、i + 1番目が更新されている場合に、数値がずれないようにminをとる。
27            dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k])
28
29            # Y以上の配列Indexを参照しないように、minを実行する。
30            kk = min(k + y, Y)
31
32            dp[i + 1][jj][kk] = min(dp[i + 1][jj][kk], dp[i][j][k] + 1)
33
34print(dp[N][X][Y] if dp[N][X][Y] < INF else -1)

2021年9月18日時点のレート画像

プロフィールを確認する

参考文献

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