ABC218のA,B,C問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッター、マシュマロまでどうぞ！
Twitter: u2dayo
マシュマロ： [https://marshmallow-qa.com/u2dayo]
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
よかったらLGTMや拡散していただけると喜びます！
目次
ABC218 まとめ
A問題『Weather Forecast』
B問題『qwerty』
C問題『Shapes』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC218 まとめ
全提出人数: 8839人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB------ | 300 | 14分 | 6515(6262)位 |
| 400 | AB------ | 300 | 8分 | 5346(5096)位 |
| 600 | AB------ | 300 | 4分 | 4398(4148)位 |
| 800 | AB-D---- | 700 | 72分 | 3425(3179)位 |
| 1000 | ABCD---- | 1000 | 93分 | 2530(2286)位 |
| 1200 | AB-DE--- | 1200 | 60分 | 1795(1557)位 |
| 1400 | ABCDE--- | 1500 | 89分 | 1240(1011)位 |
| 1600 | ABCDE--- | 1500 | 52分 | 837(620)位 |
| 1800 | ABCDEF-- | 2000 | 107分 | 547(357)位 |
| 2000 | ABCDEF-- | 2000 | 80分 | 358(191)位 |
| 2200 | ABCDE-G- | 2100 | 99分 | 210(96)位 |
| 2400 | ABCDEFG- | 2600 | 98分 | 135(47)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|---|---|
| 灰 | 3896 | 97.7 % | 94.0 % | 7.2 % | 12.4 % | 4.9 % | 0.3 % | 0.0 % | 0.0 % |
| 茶 | 1528 | 99.5 % | 99.3 % | 27.7 % | 43.5 % | 18.4 % | 1.3 % | 0.1 % | 0.1 % |
| 緑 | 1209 | 99.9 % | 99.9 % | 46.3 % | 75.8 % | 50.8 % | 5.5 % | 0.8 % | 0.2 % |
| 水 | 713 | 99.7 % | 99.4 % | 69.1 % | 95.0 % | 88.2 % | 24.1 % | 2.5 % | 0.1 % |
| 青 | 377 | 99.5 % | 99.5 % | 84.6 % | 98.9 % | 97.1 % | 52.2 % | 19.6 % | 1.9 % |
| 黄 | 186 | 97.3 % | 95.7 % | 84.4 % | 93.5 % | 93.0 % | 67.7 % | 40.3 % | 4.8 % |
| 橙 | 44 | 93.2 % | 90.9 % | 84.1 % | 90.9 % | 90.9 % | 77.3 % | 63.6 % | 22.7 % |
| 赤 | 28 | 92.9 % | 92.9 % | 92.9 % | 96.4 % | 96.4 % | 92.9 % | 71.4 % | 53.6 % |
※表示レート、灰に初参加者は含めず
A問題『Weather Forecast』
問題ページ：A - Weather Forecast
灰コーダー正解率：97.7 %
茶コーダー正解率：99.5 %
緑コーダー正解率：99.9 %
入力
$N$ : $N$ 日後に晴れかどうか知りたい
$S$ : 長さ $7$ の文字列で、$i$ 文字目が 'o' なら $i$ 日後が晴れ、'x' なら $i$ 日後が雨
実装
$S_N$ が'o' か 'x' か判定すればいいのですが、Pythonにおいて $1$ 文字目は S[0] に対応することに注意してください。$N$ 日後は S[N-1] です。
コード
N = int(input())
S = input()
print('Yes' if S[N - 1] == "o" else 'No')
B問題『qwerty』
問題ページ：B - qwerty
灰コーダー正解率：94.0 %
茶コーダー正解率：99.3 %
緑コーダー正解率：99.9 %
入力
$P_i$: 答えとして出力する文字の $i$ 文字目が、アルファベットの はじめから $i$ 番目であることを表す（たとえば $P_1=1$ なら $1$ 文字目は 'a'、$P_5=25$ なら $5$ 文字目は 'x'）
考察
問題文は難しく書いてありますが、「数字が26個与えられるので、それぞれ $a$ から数えて $P_i$ 番目のアルファベットに変換してください」というだけの問題です。
実装
a~zの文字列を作って、答えに追加していく方法
$1$ は $a$、$2$ は $b$、$3$ は $c$、……$26$ は $z$ という変換さえできれば、$P$ を前から順番に見ていって、数字をアルファベットに変換した文字を答えにくっつけていくだけです。
変換するには、ただ単に文字列alps = "abcdefghijklmnopqrstuvwxyz"に添え字でアクセスするだけで良いです。このままだと、alps[0] = 'a' と一文字ずれて面倒なので、alps = "!abcdefghijklmnopqrstuvwxyz" と $0$ 文字目に適当な文字を追加してずらすと楽です。
ord関数とchr関数を使う方法
文字を文字コードという文字ごとに決まっている整数に変換する ord() 関数と、整数を受け取って対応する文字コードの文字に変換する関数 chr() を使って解きます。
ややB問題の難易度を逸脱する方法ではありますが、文字を整数に変換して扱いたいときに使える関数なので、覚えておいて損はありません。
アルファベットの文字コードは連続している
$a$ の文字コードは $97$ です。そして、$b$ は $98$、$c$ は $99$、……、$y$ は $121$、$z$ は $122$ と、英小文字の文字コードは連続しています。
ord関数
文字を受け取って、対応する文字コードの整数を返します。たとえば、ord('a')==97、ord('y')==121です。
chr関数
整数を受け取って、対応する文字コードの文字を返します。たとえば、chr(97)=='a'、chr(121)=='y'です。ord関数の逆です。
解き方
英小文字の文字コードが連続していることを利用します。$a$ から数えて $x$ 番目の英小文字の文字コードは、ord('a') + (x-1) と書けます。これをchr()関数に入れれば、目当ての英小文字を得られます。
コード
a~zの文字列を作って、答えに追加していく方法
P = list(map(int, input().split()))
alps = "!abcdefghijklmnopqrstuvwxyz" # 0文字目は!にしています
ans = ""
for x in P:
ans += alps[x] # += による文字列の連結は低速ですが、Pの長さは26しかないので問題ありません
print(ans)
タイプミスが怖い場合、stringモジュールの定数 ascii_lowercase を使ってもいいです。ascii_lowercaseは、"abcdefghijklmnopqrstuvwxyz"という文字列の定数です。非常にマイナーで、とくに覚える必要はありませんが、たまに使えることもあります。
from string import ascii_lowercase # ascii_lowercaseは、"abcdefghijklmnopqrstuvwxyz"という文字列の定数です
P = list(map(int, input().split()))
alps = '!' + ascii_lowercase
ans = ""
for x in P:
ans += alps[x] # += による文字列の連結は低速ですが、Pの長さは26しかないので問題ありません
print(ans)
ord関数とchr関数を使う方法
P = list(map(int, input().split()))
ans = [chr(ord('a') + x - 1) for x in P]
print(''.join(ans)) # ''.join(ans)で文字列のリストを結合しています
備考: 文字列を+=で連結する場合は、速度に注意が必要
今回の解説では、文字列の連結に+=を使っています。しかし、文字列の連結に+=を使うのは低速で、$1$ 万回程度の文字列を+=で連結するとTLEになることがあります。
今回の問題では文字列の長さは $26$ 文字しかないので、+=で構いません。
$1000$ 回以上文字列を連結するような場合は、空のリスト L に文字や文字列 c をL.append(c)で追加して、最後にS = ''.join(L)という構文で連結すると高速です。
※1 空の文字列に $N$ 回 += で $1$ 文字ずつ連結するときの計算量は、$O(N^2)$になります。S += 'a'は 『S の末尾に 'a' を追加』しているのではなく、『S の末尾に 'a' を追加した文字列をゼロから新しく作り直して、Sに代入している』からです。長さ $M$ の文字列をゼロから生成するときの計算量は $O(M)$ で、数万回も生成しなおすと無視できないほど遅くなります。
※2 ただし、通常のPython（CPython）では最適化が効いて高速に動作する場合のほうが多いです。PyPyでは、必ず $O(N^2)$ の計算量になります。どちらにせよ、リストにappendして最後にjoinする方法を使うのが無難です。
C問題『Shapes』
問題ページ：C - Shapes
灰コーダー正解率：7.2 %
茶コーダー正解率：27.7 %
緑コーダー正解率：46.3 %
こちらの ユーザー解説の方法が楽なので、そちらのほうが良いです。
入力
$N$ : グリッドの大きさ（$N$ 行 $N$ 列）
$S_{i,j}$ : $S_{i,j}$ が # であるマスが図形 $S$ の一部分である
$T_{i,j}$ : $T_{i,j}$ が # であるマスが図形 $S$ の一部分である
考察
非常に面倒です。
- $S$ と $T$ に含まれる
#の数が等しくなければその時点でNo - $S$ と $T$ の一致判定をする
- $T$ を $90$ 度回転させて、$S$ と $T$ の一致判定をするのを $3$ 回繰り返す
実装
一致判定
横方向、縦方向にどれくらい平行移動させるかを全探索すると、一致判定 $1$ 回の計算量が $O(N^2)$、平行移動の組み合わせが $O(N^2)$ なので、全体で $O(N^4)$ となりTLEになります。
$S$ の一番左上の#の位置と、$T$の一番左上の# の位置を求めます。これらが一致しなければいけませんが、そのように平行移動する方法は $1$ 通りだけなので、平行移動の方法は回転の方法 $1$ つにつき $1$ 通りだけ試せば良いことになります。
回転は4通り
$(row,col)$ を $90$ 度回転させたあとの位置は、$(col, N - 1 - row)$ になります。これをこのまま書いてもいいですが、Python では list(zip(*s[::-1])) と書くと $90$ 度回転した二次元リストを返してくれます。
コード
def main():
def count_sharp(s):
ret = 0
for s_row in s:
ret += s_row.count('#')
return ret
def find_first_sharp(s):
for row in range(N):
for col in range(N):
if s[row][col] == '#':
return row, col
def is_same(s, t, dr, dc):
for row in range(N):
for col in range(N):
row_s = row + dr
col_s = col + dc
if 0 <= row_s < N and 0 <= col_s < N:
if s[row_s][col_s] != t[row][col]:
return False
else:
if t[row][col] == '#':
# グリッドから # がはみ出ているため
return False
return True
def rot(s):
return list(zip(*s[::-1]))
def judge(s, t):
if count_sharp(s) != count_sharp(t):
return False
for _ in range(4):
sr, sc = find_first_sharp(s) # sの一番左上の#の位置
tr, tc = find_first_sharp(t) # tの一番左上の#の位置
dr = sr - tr # 平行移動する量を計算
dc = sc - tc
if is_same(s, t, dr, dc):
return True
t = rot(t) # tを90度回転
return False
N = int(input())
S = []
for _ in range(N):
_s = input()
S.append(list(_s))
T = []
for _ in range(N):
_t = input()
T.append(list(_t))
print("Yes" if judge(S, T) else "No")
if __name__ == '__main__':
main()