12 min readAtCoder
【備考録】AtCoder Beginner Contest 218 A~D問題
AtCoder Beginner Contest 218のA~D問題に関して、問題文からContest中に考えたこと、解答等を備忘録としてまとめました。是非最後までご一読ください。
- そもそもAtCoderとは?
- 「AtCoder Beginner Contest 218」
- A -> Weather Forecast
- B -> qwerty
- C -> Shapes
- D -> Rectangles
- 参考文献
執筆者 - おすすめの記事3選
そもそもAtCoderとは?
AtCoderを一言で表すと、オンラインで参加できるプログラミングコンテスト(競技プログラミング)サイトになります。リアルタイムのコンテストで競い合ったり、約3000問のコンテストの過去問に、いつでも挑戦出来ることが魅力です。
今回は 「AtCoder Beginner Contest 218」のプログラミングコンテストへ参加しました。
「AtCoder Beginner Contest 218」
コンテスト情報
- コンテスト時間 : 100分
- レーティング更新対象 : 0 - 1999
配点
| 問題 | 点数 |
|---|---|
| A | 100 |
| B | 200 |
| C | 300 |
| D | 400 |
| E | 500 |
| F | 500 |
| G | 600 |
| H | 600 |
ルール
- コンテスト中に問題に正解すると点数を獲得できます。
- 順位は総合得点で決定します。
- 同点の場合は提出時間の早い人が上の順位になります。
- 誤答を提出するたびにペナルティが加算されます。このコンテストのペナルティは5分です。(ルールに関して詳しくみる)
このコンテストは「コンテスト中に提出された結果」だけで順位が決定します。
A -> Weather Forecast
問題文
明日からの7日間の天気予報を表す文字列Sが与えられます。i日後の予報はSのi文字目がoであるとき晴れ、xであるとき雨です。
N日後の天気予報が晴れかどうかを教えてください。
制約
- Nは1以上7以下の整数
- Sは長さ7の文字列であり、
oとxのみからなる
入力
入力は以下の形式で標準入力から与えられる。
1N
2S
出力
N日後の天気予報が晴れであるときYesを、雨であるときNoを出力せよ。
本問題は、AtCoder株式会社で作成された、A - Weather Forecast問題を参照しております。
Contest中に考えたこと
- 文字列Sを1文字単位に分割し、リストに格納する。
- 上記のリスト内の、N - 1番目の値を取り出す。
oならYes、xならNoを出力する。
解答
1# 標準入力を受け付ける。
2N = int(input())
3# 文字列Sを1文字単位に分割し、リストに格納する。
4S = list(input())
5
6# リスト内のN - 1番目の値を取り出す。
7# -1しているのは、配列のindexが0から始まるため。
8ans = S[N - 1]
9
10# 'o'なら'Yes'、'x'なら'No'を出力する。
11if ans == 'o':
12 print('Yes')
13else:
14 print('No')B -> qwerty
問題文
1以上26以下の整数からなる長さ26の数列P=(P1, P2, …, P26)が与えられます。ここで、Pの要素は相異なることが保証されます。
以下の条件を満たす長さ26の文字列Sを出力してください。
- 任意のi(1 ≤ i ≤ 26)について、Sのi文字目は辞書順で小さい方からPi番目の英小文字である。
制約
- 1 ≤ Pi ≤ 26
- Pi ≠ Pj(i ≠ j)
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
1P1 P2 … P26出力
文字列Sを出力せよ。
本問題は、AtCoder株式会社で作成された、B - qwerty問題を参照しております。
Contest中に考えたこと
- アルファベットのリストを作成する。
- P0, P1...の値に合致するアルファベットを選択し、文字列をつなぎ合わせる。
解答
1# アルファベットのリストを作成する。
2alphabetList = [
3 'a',
4 'b',
5 'c',
6 'd',
7 'e',
8 'f',
9 'g',
10 'h',
11 'i',
12 'j',
13 'k',
14 'l',
15 'm',
16 'n',
17 'o',
18 'p',
19 'q',
20 'r',
21 's',
22 't',
23 'u',
24 'v',
25 'w',
26 'x',
27 'y',
28 'z',
29]
30
31# 標準入力を受け付ける。
32P = list(map(int, input().split()))
33
34ans = ''
35for i in range(0, len(P)):
36 # P0, P1...の値に合致するアルファベットを選択し、文字列をつなぎ合わせる。
37 # -1しているのは、配列のindexが0から始まるため。
38 ans = ans + alphabetList[P[i] - 1]
39
40print(ans)C -> Shapes
問題文
2次元グリッド上に2つの図形SとTがあります。グリッドは正方形のマスからなります。SはN行N列のグリッド内にあり、Si, jが#であるようなマス全体からなります。TもN行N列のグリッド内にあり、Ti, jが#であるようなマス全体からなります。
SとTを90度回転及び平行移動の繰り返しによって一致させることができるか判定してください。
制約
- 1 ≤ N ≤ 200
- S, Tは
#と.のみからなる - S, Tは1つ以上
#を含む
入力
入力は以下の形式で標準入力から与えられる。
1N
2S1, 1 S1, 2 … S1, N
3⋮
4SN, 1 SN, 2 … SN, N
5T1, 1 T1, 2 … T1, N
6⋮
7TN, 1 TN, 2 … TN, N出力
SとTを90度回転及び平行移動の繰り返しによって一致させることができるときYesを、そうでないときNoを出力せよ。
本問題は、AtCoder株式会社で作成された、C - Shapes問題を参照しております。
Contest中に考えたこと
- Sを90度回転して図形が等しいか確かめるために、4回ループさせる必要がある。
- 平行移動して図形が等しいか確かめる方法や90度回転させる方法がわからず、終了。
解答
1# 図形を90度回転する関数
2def rotate(S):
3 res = [[''] * N for _ in range(N)]
4 # N = 5の時を考える。
5 # (0, 0)の値は(0, 4)へ移動。(0, 1)の値は(1, 4)へ移動。(0, 2)の値は(2, 4)へ移動。(0, 3)の値は(3, 4)へ移動。(0, 4)の値は(4, 4)へ移動。
6 # (1, 0)の値は(0, 3)へ移動。(1, 1)の値は(1, 3)へ移動。...と続けていく。
7 # 参考 : https://daeudaeu.com/2d-rotate/#i-6
8 for i in range(0, N):
9 for j in range(0, N):
10 res[j][N - i - 1] = S[i][j]
11 return res
12
13# 初めて左上に#が現れる座標を取得する関数
14def leftAndTop(S):
15 for i in range(0, N):
16 for j in range(0, N):
17 if S[i][j] == '#':
18 return i, j
19
20# 図形が等しいかどうか検証する関数
21def isSame(S, T):
22 # 初めて左上に#が現れる、座標を取得する。
23 sx, sy = leftAndTop(S)
24 tx, ty = leftAndTop(T)
25 # 座標のずれを調整するためにoffsetを設ける。
26 # offsetとは? : https://wa3.i-3-i.info/word11923.html
27 offsetX = tx - sx
28 offsetY = ty - sy
29
30 for i in range(0, N):
31 for j in range(0, N):
32 # offsetをプラスする。
33 ii = i + offsetX
34 jj = j + offsetY
35 # 座標の値が枠の中の場合
36 if 0 <= ii < N and 0 <= jj < N:
37 if S[i][j] != T[ii][jj]: return False
38 # 座標の値が枠の外の場合
39 else:
40 # 座標の値が枠の外の場合に、S[i][j] == '#'だと、#の数が一致せずに異なる図形となるため、Falseを返す。
41 if S[i][j] == '#': return False
42 return True
43
44# 標準入力を受け付ける。
45N = int(input())
46
47S = [list(input()) for _ in range(N)]
48T = [list(input()) for _ in range(N)]
49
50# #の数を数える。
51# #の数が違うと、図形が同じであると言えないため。
52sumS = 0
53sumT = 0
54for i in range(0, N):
55 for j in range(0, N):
56 if S[i][j] == '#':
57 sumS += 1
58 if T[i][j] == '#':
59 sumT += 1
60
61if sumS != sumT:
62 print('No')
63 exit()
64
65# range(0, 4)なのは、図形を90度回転して等しいか検証するパターンが、4種類あるため。
66for i in range(0, 4):
67 if isSame(S, T):
68 print('Yes')
69 exit()
70 S = rotate(S)
71print('No')D -> Rectangles
問題文
2次元平面上にN個の相異なる点があり、1, 2, …, Nの番号がついています。点i(1 ≤ i ≤ N)の座標は(xi, yi)です。
これらの点のうち4つを頂点とし、全ての辺がx軸またはy軸に平行であるような長方形はいくつありますか？
制約
- 4 ≤ N ≤ 2000
- 0 ≤ xi, yi ≤ 10の9乗
- (xi, yi) ≠ (xj, yj) (i ≠ j)
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
1N
2x1 y1
3x2 y2
4⋮
5xN yN
出力
答えを出力せよ。
本問題は、AtCoder株式会社で作成された、D - Rectangles問題を参照しております。
学んだこと
- 2点を選んで長方形を作れるか考える。
- 1点を固定(p1とする)して、もう一点をp2とする場合、p1のx座標 < p2のx座標かつp1のy座標 < p2のy座標の場合の長方形を探す。 ⏩ 重複して長方形を数えないようにするため。
- 2点の情報から残りの2点の座標を洗い出す。
- 残りの2点の情報が標準入力内に含まれるか、確認する。(含まれるか確認する際に、set型を利用して、高速化を図る)
解答
1# 標準入力を受け付ける。
2N = int(input())
3# 重複の削除 + set型を利用する。 ⏩ in句を利用する際に、探索を高速化するため。
4# なぜset型を利用すると高速になるのか? : https://qiita.com/kitadakyou/items/6f877edd263f097e78f4
5points = set(tuple(map(int, input().split())) for _ in range(N))
6
7ans = 0
8for p1 in points:
9 for p2 in points:
10 # 1点を固定(p1とする)して、もう一点をp2とする場合、p1のx座標 < p2のx座標かつp1のy座標 < p2のy座標の場合の長方形を探す。
11 if not(p1[0] < p2[0] and p1[1] < p2[1]):
12 continue
13
14 # 2点の情報から残りの2点の座標を洗い出す。
15 r = (p2[0], p1[1])
16 q = (p1[0], p2[1])
17
18 # 残りの2点の情報が標準入力内に含まれるか、確認する。
19 if r in points and q in points:
20 ans += 1
21
22print(ans)2021年9月11日時点のレート画像
