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

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 222」

コンテスト情報

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

配点

ルール

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

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

A -> Four Digits

問題文

0以上9999以下の整数Nが与えられます。Nの先頭に必要なだけ0をつけ、4桁の文字列にしたものを出力してください。

制約

• 0 ≤ N ≤ 9999
• Nは整数

入力

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

1N

出力

答えを出力せよ。

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

Contest中に考えたこと

• 入力されるNの文字の長さを調べる。
• Nの文字の長さに応じて、先頭へ0を付与する。

解答

1# 標準入力を受け付ける。
2N = input()
3
4# 入力されるNの文字の長さを調べる。
5nLen = len(N)
6# Nの文字の長さに応じて、先頭へ0を付与する。
7if nLen == 1:
8    print('000' + N)
9elif nLen == 2:
10    print('00' + N)
11elif nLen == 3:
12    print('0' + N)
13else:
14    print(N)

B -> Failing Grade

問題文

N人の学生が試験を受けました。学生には学生1, 学生2, …, 学生Nと番号がついていて、学生iはai点を取りました。P点未満の点数を取った学生は不可となり単位を取得できません。不可となった学生の人数を答えてください。

制約

• 1 ≤ N ≤ 10の5乗
• 1 ≤ P ≤ 100
• 0 ≤ ai ≤100(1 ≤ i ≤ N)
• 入力はすべて整数である。

入力

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

1N P
2a1 a2 … aN

出力

不可となった学生の人数を出力せよ。

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

Contest中に考えたこと

• 学生1人1人の点数が、P点未満であるかどうか確認する。
• ある学生の点数がP点未満だった場合に、不可の人数を+1カウントする。

解答

1# 標準入力を受け付ける。
2N, P = map(int, input().split())
3 
4A = list(map(int, input().split()))
5 
6ans = 0
7# 学生1人1人の点数が、P点未満であるかどうか確認する。
8for i in range(len(A)):
9    # ある学生の点数がP点未満だった場合に、不可の人数を+1カウントする。
10    if P > A[i]:
11        ans += 1
12 
13print(ans)

C -> Swiss-System Tournament

問題文

1から2Nの番号がついた2N人でじゃんけん大会をします。大会はMラウンドからなり、各ラウンドは、全ての人が1度ずつ参加するような1対1のN試合からなります。

i = 0, 1, …, Mについて、iラウンド目の終了時点での順位を次のように決めます。

• iラウンド目までの勝数が多い方が上位
• iラウンド目までの勝数が同じときは、番号が小さい方が上位

また、i = 1, …, Mについて、iラウンド目の各試合の組み合わせを次のように決めます。

• 各k = 1, 2, …, Nについて、i − 1ラウンド目終了時点の順位が2k − 1位の人と2k位の人が試合をする

各試合では、対戦する2人がそれぞれ1度だけ手を出し、勝ち・負け・引き分けのいずれかの結果が発生します。

未来予知ができる高橋君は、人iがjラウンド目の試合で出す手がAi, jであることを知っています。

Ai, jはG, C, Pのいずれかであり、それぞれグー、チョキ、パーを表します。

Mラウンド目終了時点の順位を求めてください。

じゃんけんのルール

じゃんけんの結果は、2人の出した手に応じて次のように決まります。

• 一方がグーで他方がチョキのとき、グーを出した人が勝ち、チョキを出した人は負け
• 一方がチョキで他方がパーのとき、チョキを出した人が勝ち、パーを出した人は負け
• 一方がパーで他方がグーのとき、パーを出した人が勝ち、グーを出した人は負け
• 両者が同じ手を出したとき、引き分け

制約

• 1 ≤ N ≤ 50
• 1 ≤ M ≤ 100
• Ai, jはG, C, Pのいずれか

入力

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

1N M
2A1,1 A1,2 … A1,M
3​A2,1 A2,2 … A2,M
4​⋮
5A2N,1 A2N,2 … A2N,M

出力

2N行出力せよ。

i行目には、Mラウンド目終了時点での順位がi位である人の番号を出力せよ。

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

Contest中に考えたこと

• 制約のN, Mの数の上限が小さいので、純粋に問題を解くことにする。
• [[じゃんけんに勝利した数, 番号1], [じゃんけんに勝利した数, 番号2], ...]で情報管理を行う。
• 実際にじゃんけんを行い、じゃんけんに勝利した番号の、じゃんけんに勝利した数へ+1カウントする。
• じゃんけんに勝利した数を降順でソートしつつ、番号を昇順でソートする。

解答

1# 標準入力を受け付ける。
2N, M = map(int, input().split())
3
4A = []
5users = []
6for i in range(2 * N):
7    A.append(list(input()))
8    # [[じゃんけんに勝利した数, 番号1], [じゃんけんに勝利した数, 番号2], ...]で情報管理を行う。
9    users.append([0, i + 1])
10
11for i in range(M):
12    for j in range(N):
13        # 2 * j + 1に該当する番号と2 * jに該当する番号を取得する。
14        numA = users[2 * j + 1][1]
15        numB = users[2 * j][1]
16
17        # 実際にじゃんけんを行い、じゃんけんに勝利した番号の、じゃんけんに勝利した数へ+1カウントする。
18        if A[numA - 1][i] == 'G' and A[numB - 1][i] == 'C':
19            users[2 * j + 1][0] += 1
20
21        if A[numA - 1][i] == 'C' and A[numB - 1][i] == 'P':
22            users[2 * j + 1][0] += 1
23
24        if A[numA - 1][i] == 'P' and A[numB - 1][i] == 'G':
25            users[2 * j + 1][0] += 1
26
27        if A[numB - 1][i] == 'G' and A[numA - 1][i] == 'C':
28            users[2 * j][0] += 1
29
30        if A[numB - 1][i] == 'C' and A[numA - 1][i] == 'P':
31            users[2 * j][0] += 1
32
33        if A[numB - 1][i] == 'P' and A[numA - 1][i] == 'G':
34            users[2 * j][0] += 1
35
36    # じゃんけんに勝利した数を降順でソートしつつ、番号を昇順でソートする。
37    # 参考 : https://yshystsj.com/2019/05/28/post-182/
38    users = sorted(users, key=lambda k: (-k[0], k[1]))
39
40# 結果を出力する。
41for user in users:
42    print(user[1])

D -> Between Two Arrays

問題文

長さnの数列S=(s1, s2, …, sn)がすべてのi(1 ≤ i ≤ n − 1)に対してsi ≤ si + 1を満たすとき、かつそのときに限り「数列Sは広義単調増加である」と呼びます。

広義単調増加な長さNの整数列A=(a1, a2, …, aN), B=(b1, b2, …, bN)が与えられます。このとき、次の条件を満たす広義単調増加な長さNの整数列C=(c1, c2, …, cN)を考えます。

• すべてのi(1 ≤ i ≤ N)に対してai ≤ ci ≤ biが成り立つ。

整数列Cとしてあり得る数列の個数を998244353で割ったあまりを求めてください。

制約

• 1 ≤ N ≤ 3000
• 0 ≤ ai ≤ bi ≤ 3000(1 ≤ i ≤ N)
• 整数列A, Bは広義単調増加である。
• 入力はすべて整数である。

入力

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

1N
2a1 a2 … aN
3b1 b2 … bN

出力

Cとしてあり得る数列の個数を998244353で割ったあまりを出力せよ。

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

Contest中に考えたこと

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

解答

1MOD = 998244353
2
3N = int(input())
4A = list(map(int, input().split()))
5B = list(map(int, input().split()))
6
7MAX_N = 3001
8
9# dp[i][c] : i番目の状態の場合に、cの値を固定して、(ai ≤ c ≤ bi)を満たす場合の数が、どれくらい存在するのか数え上げる。
10# 例) dp[0][1] : 0番目の状態の場合にcの値を1に固定する。(a0 ≤ 1 ≤ b0)を満たす、場合の数がどれくらい存在するのか数え上げる。
11# 例) dp[2][3] : 2番目の状態の場合にcの値を3に固定する。(a2 ≤ 3 ≤ b2)を満たす、場合の数がどれくらい存在するのか数え上げる。
12dp = [[0] * MAX_N for _ in range(N + 1)]
13
14# 初期化を行う。
15# 0番目の状態の場合に、cの値を0とする。確実に(a0 ≤ 0 ≤ b0)を満たす場合の数は、1通りとなる。
16# c=1の時、c=2の時、c=3の時、、、の場合は、a0, b0の値が変化することにより、初期化段階では決められないので0としておく。
17dp[0][0] = 1
18
19# i回状態遷移を行う。
20for i in range(N):
21    # aiの値をtmpAとする。
22    tmpA = A[i]
23    # biの値をtmpAとする。
24    tmpB = B[i]
25
26    # tmpAよりも小さい値 && (ai-1 ≤ tmpAよりも小さい値 ≤ bi-1)を満たす場合の数の、総和を演算しておく。
27    s = sum(dp[i][:tmpA]) % MOD
28
29    # (ai ≤ ci ≤ bi)を満たす箇所のみ、状態の更新を行う。
30    for c in range(tmpA, tmpB + 1):
31        # tmpAとcが同値の場合の場合の数を演算する。
32        # cの値が+1されるごとに、一つ前のcの値も、場合の数に含められるので、s += を実行している。
33        s += dp[i][c]
34
35        s %= MOD
36        dp[i + 1][c] = s
37
38# N番目の状態の場合に、cの値を固定して、(aN ≤ c ≤ bN)を満たす場合の数が、どれくらい存在するのか総和する。
39print(sum(dp[N]) % MOD)

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

プロフィールを確認する

参考文献

• レーティングとは?
• AtCoderのプログラミングコンテストのルール
• AtCoder株式会社について
• Atcoder 222に関するコードまとめ
• 降順とは?
• 昇順とは?
• 広義単調増加とは?