作成日 : 2022-01-29
更新日 : 2022-01-29
9 min readAtCoder

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 236」

コンテスト情報

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

配点

ルール

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

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

A -> chukodai

問題文

英小文字からなる文字列Sが与えられます。Sの先頭からa文字目とb文字目を入れ替えて得られる文字列を出力してください。

制約

• Sは英小文字からなる文字列
• Sの長さ∣S∣は、2 ≤ ∣S∣ ≤ 10を満たす
• 1 ≤ a < b ≤ ∣S∣
• a, bは整数

入力

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

1S
2a b

出力

答えを出力せよ。

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

Contest中に考えたこと

• Sの文字列を1文字単位で配列に格納する。
• a文字目とb文字目を入れ替える。

解答

1# 標準入力を受け付ける。
2# Sの文字列を1文字単位で配列に格納する。
3S = list(input())
4 
5a, b = map(int, input().split())
6 
7# a文字目とb文字目を入れ替える。
8# a - 1, b - 1しているのは、配列indexを考慮するため。
9S[b - 1], S[a - 1] = S[a - 1], S[b - 1]
10 
11print(''.join(S))

B -> Who is missing?

問題文

整数1, 2, …, Nが書かれたカードが4枚ずつ、合計4N枚あります。高橋君は、これらのカードをシャッフルしたのち1枚のカードを選んで抜き取り、残りの4N − 1枚を束にしてあなたに渡しました。渡された束のi(1≤ i ≤ 4N − 1)枚目のカードには、整数Aiが書かれています。

高橋君が抜き取ったカードに書かれていた整数を求めてください。

制約

• 1 ≤ N ≤ 10の5乗
• 1 ≤ Ai ≤ N(1 ≤ i ≤ 4N − 1)
• 各k(1 ≤ k ≤ N)に対し、Ai = kとなるiは4個以下である。
• 入力は全て整数である。

入力

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

1N
2A1 A2 … A4N − 1

出力

答えを出力せよ。

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

Contest中に考えたこと

• 標準入力として与えられる、A1, A2, ...のカードに書かれた数字が、それぞれ何枚ずつあるのか数える。
• A1, A2, ...のカードに書かれた数字を、持っている枚数の多い順に並べ替える。
• 持っている枚数が一番少ない、Axの値を出力する。

解答

1import collections
2 
3# 標準入力を受け付ける。
4N = int(input())
5A = list(map(int, input().split()))
6 
7# 標準入力として与えられる、A1, A2, ...のカードに書かれた数字が、それぞれ何枚ずつあるのか数える。
8# 参考 : https://note.nkmk.me/python-collections-counter/
9c = collections.Counter(A)
10
11# most_common() : A1, A2, ...のカードに書かれた数字を、持っている枚数の多い順に並べ替える。
12# 持っている枚数が一番少ない、Axの値を出力する。
13print(c.most_common()[len(c) - 1][0])

C -> Route Map

問題文

AtCoder鉄道のとある路線にはN個の駅が存在し、始点から終点に向かってi(1 ≤ i ≤ N)番目の駅の名前はSiです。

普通列車は全ての駅に止まりますが、急行列車は全ての駅に止まるとは限りません。具体的には、急行列車はM(M ≤ N)個の駅にのみ止まり、j(1 ≤ j ≤ M)番目に止まる駅の名前はTjです。

ただし、T1 = S1かつTM = SN、すなわち急行列車は始点と終点の両方に止まることが保証されます。

N個の駅それぞれについて、その駅に急行列車が止まるかどうか判定してください。

制約

• 2 ≤ M ≤ N ≤ 10の5乗
• N, Mは整数
• Si(1 ≤ i ≤ N)は英小文字のみからなる1文字以上10文字以下の文字列
• Si ≠ Sj(i ≠ j)
• T1 = S1かつTM = SN
• (T1, …, TM)は(S1, …, SN)から0個以上の文字列を選んで取り除き、残った文字列を元の順序で並べることで得られる

入力

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

1N M
2S1 … SN
3T1 … TM

出力

N行出力せよ。i(1 ≤ i ≤ N)行目には、始点から終点に向かってi番目の駅に急行列車が止まるならYes、そうでないなら Noと出力せよ。

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

Contest中に考えたこと

• 普通列車で止まることのできる、全ての駅をdict型で保存する。
• 急行列車で止まる駅が、上で宣言したdict型の駅に該当するかどうか確かめる。 ⏩ ある場合Yes, ない場合Noと返す。

解答

1# 標準入力を受け付ける。
2N, M = map(int, input().split())
3 
4S = list(map(str, input().split()))
5T = list(map(str, input().split()))
6 
7# 普通列車で止まることのできる、全ての駅をdict型で保存する。
8stations = {}
9for i in range(len(T)):
10    stations[T[i]] = True
11 
12for i in range(len(S)):
13    # 急行列車で止まる駅が、上で宣言したdict型の駅に該当するかどうか確かめる。
14    # ある場合`Yes`, ない場合`No`と返す。
15    if stations.get(S[i]) is not None:
16        print('Yes')
17    else:
18        print('No')

D -> Dance

問題文

1, 2, …, 2Nと番号づけられた2N人の人が舞踏会に参加します。 彼らはN個の2人組にわかれてダンスを踊ります。2人組を構成する人のうち、番号の小さい方の人が人i、番号の大きい方の人が人jのとき、 その2人組の「相性」はAi,jです。

N個の2人組の相性がそれぞれB1, B2, …, BNであるとき、 「舞踏会全体の楽しさ」はそれらのビットごとの排他的論理和であるB1 ⊕ B2 ⊕ ⋯ ⊕ BNです。

「2N人の参加者がN個の2人組に分かれる方法」を自由に選べるとき、「舞踏会全体の楽しさ」としてあり得る最大値を出力してください。

制約

• 1 ≤ N ≤ 8
• 0 ≤ Ai, j <2の30乗
• 入力はすべて整数

入力

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

1N
2A1,2 A1,3 A1,4 ⋯ A1,2N
3A2,3 A2,4 ⋯ A2,2N
4A3,4 ⋯ A3,2N
5⋮
6A2N−1,2N

出力

舞踏会全体の楽しさとしてあり得る最大値を出力せよ。

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

Contest中に考えたこと

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

解答

1# <方針>
2# Nの最大値が小さいので、前通りの組み合わせを試して答えを求めると良い。
3# 2人を選ぶときに、1, 2 = 2, 1の選び方は等しいことを意味する。
4# 1, 1の組み合わせなどは存在しない。
5
6# 標準入力を受け付ける。
7N = int(input())
8A = [list(map(int, input().split())) for _ in range(2 * N - 1)]
9
10ans = 0
11
12def dfs(dancer, score):
13
14    if len(dancer) == 0:
15        global ans
16        ans = max(ans, score)
17        return
18
19    first_dancer = dancer[0]
20
21    for i in range(1, len(dancer)):
22        second_dancer = dancer[i]
23
24        dfs(dancer[1:i] + dancer[i+1:], score ^ A[first_dancer - 1][second_dancer - first_dancer - 1])
25
26dfs([i + 1 for i in range(2 * N)], 0)
27print(ans)

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

プロフィールを確認する

参考文献

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