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

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 232」

コンテスト情報

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

配点

ルール

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

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

A -> QQ solver

問題文

3文字からなる文字列Sが与えられます。Sは、1以上9以下の整数a, bと文字xを、axbのように順につなげて得られます。

aとbの積を求めてください。

制約

• Sの長さは3
• Sの1文字目および3文字目は1以上9以下の整数を表す
• Sの2文字目はx

入力

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

1S

出力

答えを出力せよ。

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

Contest中に考えたこと

• Sの1文字目をa, Sの3文字目をbとして文字列を抽出する。
• a x bを出力する。

解答

1# 標準入力を受け付ける。
2s = list(input())
3
4# Sの1文字目をa, Sの3文字目をbとして文字列を抽出する。
5a = int(s[0])
6b = int(s[2])
7 
8# a x bを出力する。
9print(a * b)

B -> Caesar Cipher

問題文

高橋君は英小文字からなる文字列Sを持っています。高橋君は文字列Sに対して、下記の操作をちょうど1回行います。

• まず、非負整数Kを選ぶ。
• その後、Sの各文字をK個後ろの英小文字に変更する。

ただし、

• aの1個後ろの英小文字はbであり、
• bの1個後ろの英小文字はcであり、
• cの1個後ろの英小文字はdであり、
• ⋯
• yの1個後ろの英小文字はzであり、
• zの1個後ろの英小文字はaです。

例えば、bの4個後ろの英小文字はfであり、yの3個後ろの英小文字はbです。文字列Tが与えられます。 高橋君が上記の操作によってSをTに一致させることができるかを判定してください。

制約

• SとTはそれぞれ英小文字からなる長さ1以上10の5乗以下の文字列
• Sの長さとTの長さは等しい

入力

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

1S
2T

出力

高橋君がSをTに一致させることができる場合はYesと出力し、 できない場合はNoと出力せよ。

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

Contest中に考えたこと

• 非負整数Kの選び方は0~25である。26個後ろの英小文字に変更にするとSの文字列になるため。 ⏩ 文字列Sの変更パターン全てを確かめるために、かかる計算量は最大で26 * 10の5乗 = 26 * 100000 = 2600000であるので、普通に計算して問題ない。
• Sの各文字をK個後ろの英小文字に変更する関数を作成する。

解答

1# 標準入力を受け付ける。
2s = input()
3t = input()
4
5# Sの各文字をK個後ろの英小文字に変更する関数を作成する。
6# 参考 : https://qiita.com/TodayInsane/items/94f495db5ba143a8d3e0
7def rot_n(s, n):
8    answer = ''
9    for letter in s:
10        answer += chr(ord('a') + (ord(letter) - ord('a') + n) % 26)
11
12    return answer
13
14# 0から始めるのは、文字列Sを変更しない場合も考慮するため。
15for k in range(0, 26):
16    if rot_n(s, k) == t:
17        print('Yes')
18        exit()
19
20print('No')

C -> Graph Isomorphism

問題文

高橋君と青木君は、それぞれN個のボールにM本のひもを取り付けたおもちゃを持っています。高橋君のおもちゃにおいて、ボールには1, …, Nと番号が付けられており、i(1 ≤ i ≤ M)本目のひもはボールAiとボールBiを結んでいます。

青木君のおもちゃにおいても同様に、ボールには1, …, Nと番号が付けられており、i(1 ≤ i ≤ M)本目のひもはボールCiとボールDiを結んでいます。

それぞれのおもちゃにおいて、同一のボールを結ぶようなひもは存在せず、2つのボールを2本以上の異なるひもが結んでいることはありません。

すぬけ君は、2人のおもちゃが同じ形であるかどうか気になっています。ここで、2人のおもちゃが同じ形であるとは、以下の条件を満たす数列Pが存在することをいいます。

1. Pは(1, …, N)を並べ替えて得られる。
2. 任意の1以上N以下の整数i, jに対し、以下が成り立つ。
   1. 高橋君のおもちゃにおいてボールi, jがひもで繋がれていることと、青木君のおもちゃにおいてボールPi, Pjがひもで繋がれていることは同値である。

2人のおもちゃが同じ形であるならYes、そうでないならNoと出力してください。

制約

• 1 ≤ N ≤ 8
• 0 ≤ M ≤ N(N − 1) / 2
• 1 ≤ Ai < Bi ≤ N(1 ≤ i ≤ M)
• (Ai, Bi) ≠ (Aj, Bj)(i ≠ j)
• 1 ≤ Ci < Di ≤ N(1 ≤ i ≤ M)
• (Ci, Di) ≠ (Cj, Dj)(i ≠ j)
• 入力は全て整数である。

入力

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

1N M
2A1 B1
3⋮
4AM BM
5​C1 D1
6⋮
7CM DM

出力

2人のおもちゃが同じ形であるならYes、そうでないならNoと出力せよ。

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

Contest中に考えたこと

• 数列Pを全列挙して確かめて問題ないのか考える。 ⏩ 全列挙の通りの最大数(8! = 40320) x Mの最大値(8(8 - 1) / 2 = 28) = 1128960通りなので問題ない。
• 全列挙した中のある数列Pに対して、高橋君のおもちゃにおいてボールi, jがひもで繋がれていることと、青木君のおもちゃにおいてボールPi, Pjがひもで繋がれていることは同値であるかどうか確認する。

解答

1import itertools
2
3# 標準入力を受け付ける。
4N, M = map(int, input().split())
5
6takahashi_list = []
7for _ in range(M):
8    A, B = map(int, input().split())
9    takahashi_list.append([A, B])
10
11# in句を利用するためset型を利用する。(参考 : https://qiita.com/kitadakyou/items/6f877edd263f097e78f4)
12aoki_list = set(())
13for _ in range(M):
14    C, D = map(int, input().split())
15    # ボールの順序が逆になるパターンも考慮する。
16    aoki_list.add((C, D))
17    aoki_list.add((D, C))
18
19# 全列挙するための準備
20num_list = []
21for i in range(1, N + 1):
22    num_list.append(i)
23
24# itertools.permutations参考 : https://minus9d.hatenablog.com/entry/2017/04/30/110855
25for P in itertools.permutations(num_list, N):
26    cnt = 0
27    for k in range(M):
28        # 全列挙した中のある数列Pに対して、高橋君のおもちゃにおいてボールi, jがひもで繋がれていることと、青木君のおもちゃにおいてボールPi, Pjがひもで繋がれていることは同値であるかどうか確認する。
29        ball_i, ball_j = takahashi_list[k]
30        if (P[ball_i - 1], P[ball_j - 1]) in aoki_list:
31            cnt += 1
32    
33    if cnt == M:
34        print('Yes')
35        exit()
36print('No')

D -> Weak Takahashi

問題文

縦H行、横W行のH × Wマスからなるグリッドがあります。上からi行目、左からj列目のマスを(i, j)と表します。各マスの状態は文字Ci, jで表され、Ci, j= .ならばマス(i, j)は空きマスであり、Ci, j = #ならばマス(i, j)は壁です。

高橋君がグリッド上を歩こうとしています。彼がマス(i, j)にいるとき、マス(i, j + 1)またはマス(i + 1, j)に移動することができます。ただし、グリッドの外に出るような移動や、壁のマスへの移動を行うことはできません。高橋君は、移動することのできるマスが無くなった時点で立ち止まります。

高橋君がマス(1, 1)から歩き始めるとき、彼が立ち止まるまでに通ることのできるマスは最大で何マスですか？

制約

• 1 ≤ H, W ≤ 100
• H, Wは整数
• Ci, j = .またはCi, j = #(1 ≤ i ≤ H, 1 ≤ j ≤ W)
• C1, 1 = .

入力

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

1H W
2C1, 1 … C1, W
3⋮
4CH, 1 … CH, W

出力

答えを出力せよ。

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

Contest中に考えたこと

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

解答

1import collections
2
3# 標準入力を受け付ける。
4H, W = map(int,input().split())
5C = [input() for _ in range(H)]
6
7ans = 1
8seen = [list(-1 for _ in range(W)) for _ in range(H)]
9todo = collections.deque()
10todo.append((0, 0))
11seen[0][0] = 1
12
13while len(todo) != 0:
14    # 参考 : https://note.nkmk.me/python-collections-deque/
15    h, w = todo.popleft()
16    for d in [[1, 0], [0, 1]]:
17        if h + d[0] < H and w + d[1] < W:
18            # なぜ一度確認した箇所を確認しなくていいのか？ ⏩ 左や上へ戻る操作がないため。一度踏んでいた場合、再度同じ箇所を踏んだとしても同じ回数でたどり着いたことになるので、確認する必要がない。
19            if seen[h + d[0]][w + d[1]] != -1 or C[h + d[0]][w + d[1]] == '#':
20                continue
21            else:
22                todo.append((h + d[0], w + d[1]))
23                seen[h + d[0]][w + d[1]] = seen[h][w] + 1
24                ans = max(ans, seen[h + d[0]][w + d[1]])
25
26print(ans)

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

プロフィールを確認する

参考文献

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