ABC232のA,B,C,D問題を、Python3でなるべく丁寧に解説していきます。

ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。

シンプル：余計なことを考えずに済む
実装が楽：ミスやバグが減ってうれしい
時間がかからない：パフォが上がって、後の問題に残せる時間が増える

ご質問・ご指摘はコメントかツイッター、マシュマロ、Discordサーバーまでお気軽にどうぞ！

Twitter: u2dayo
マシュマロ： https://marshmallow-qa.com/u2dayo
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
Discordサーバー（質問や記事の感想・リクエストなどどうぞ！） : https://discord.gg/jZ8pkPRRMT
よかったらLGTMや拡散していただけると喜びます！

ABC232 まとめ

全提出人数: 6864人

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	AB------	300	86分	4580(4370)位
400	AB------	300	27分	3751(3541)位
600	ABC-----	600	65分	3077(2879)位
800	AB-D----	700	36分	2429(2234)位
1000	ABCD----	1000	70分	1829(1638)位
1200	ABCD----	1000	39分	1344(1157)位
1400	ABCDE---	1500	103分	946(772)位
1600	ABCDE---	1500	71分	653(486)位
1800	ABCDE---	1500	36分	439(283)位
2000	ABCDEF--	2000	85分	281(151)位
2200	ABCDEF--	2000	64分	182(75)位
2400	ABCDEF--	2000	43分	107(35)位

色別の正解率

色	人数	A	B	C	D	E	F	G	H
灰	2208	97.1 %	70.1 %	11.9 %	19.4 %	0.9 %	0.1 %	0.0 %	0.0 %
茶	1038	98.9 %	94.6 %	51.5 %	62.7 %	3.0 %	0.0 %	0.0 %	0.0 %
緑	865	98.8 %	97.1 %	82.5 %	92.4 %	21.4 %	1.9 %	0.3 %	0.1 %
水	549	99.3 %	98.4 %	94.7 %	96.7 %	60.7 %	14.9 %	0.9 %	0.2 %
青	350	96.6 %	96.0 %	95.1 %	95.7 %	86.6 %	54.9 %	4.3 %	2.0 %
黄	166	83.1 %	81.3 %	82.5 %	81.3 %	79.5 %	66.9 %	16.3 %	8.4 %
橙	33	93.9 %	93.9 %	90.9 %	90.9 %	87.9 %	78.8 %	42.4 %	18.2 %
赤	22	90.9 %	90.9 %	90.9 %	95.5 %	90.9 %	95.5 %	77.3 %	63.6 %

※表示レート、灰に初参加者は含めず

A問題『QQ solver』

問題ページ：A - QQ solver
灰コーダー正解率：97.1 %
茶コーダー正解率：98.9 %
緑コーダー正解率：98.8 %

入力

$S$ : 長さ $3$ の axb という形式の文字列（a, bはそれぞれ123456789のいずれか $1$ 文字）

考察

aとbを取り出して掛け算すればいいです。

コード

a, b = map(int, input().split('x'))
print(a * b)

B問題『Caesar Cipher』

問題ページ：B - Caesar Cipher
灰コーダー正解率：70.1 %
茶コーダー正解率：94.6 %
緑コーダー正解率：97.1 %

入力

$S,T$ : 長さ $1$ 以上 $10^5$ 以下の英小文字からなる文字列

考察

$26$ 個後ろの文字に変換すると元の文字に戻りますから、$0$ ～ $25$ 文字後ろの英小文字に変換するのをすべて試して、一致するものがあるか確かめればいいです。

アルファベットのままだと扱いづらいので、a を $0$、bを $1$、$c$ を $2$、……、$z$ を $25$ の数字に変換します。そして、ある文字を $K$ 個後ろの文字列にするときは、$(x + K)\ \%\ 26$ （$x+K$ を $26$ で割った余り）を計算すればいいです。

コード

def judge():
    S = input()
    T = input()
    A = [ord(char) - ord('a') for char in S]
    B = [ord(char) - ord('a') for char in T]
    for k in range(26):
        C = [(x + k) % 26 for x in A]
        if B == C:
            return True
    return False


print("Yes" if judge() else "No")

別解

$K$ 文字後ろにずらすして一致するのは、 $S$ と $T$ の各文字を数字で表したときの差を $26$ で割った余りがすべて同じときだけです。set の len で差の種類数が $1$ 種類かどうか判定することで解けます。

def judge():
    S = input()
    T = input()
    A = [ord(char) - ord('a') for char in S]
    B = [ord(char) - ord('a') for char in T]
    C = {(x - y) % 26 for x, y in zip(A, B)}
    return len(C) == 1


print("Yes" if judge() else "No")

C問題『Graph Isomorphism』

問題ページ：C - Graph Isomorphism
灰コーダー正解率：11.9 %
茶コーダー正解率：51.5 %
緑コーダー正解率：82.5 %

入力

$N$ : ボールの数
$M$ : ヒモの数
$A_i, B_i$ : 高橋君のおもちゃの $i$ 本目のヒモは $A_i$ と $B_i$ を結んでいる
$C_i, D_i$ : 青木君のおもちゃの $i$ 本目のヒモは $C_i$ と $D_i$ を結んでいる

考察

$P$ の並び替え方 $N!$ 通りを全て試して、同じ形のものがあるか判定します。$N$ は最大で $8$ ですから、多くても $8!=40320$ 通りです。

よくある嘘解法に、ボールに繋がっている辺の数が同じかどうか判定するというものがありますが、例えば以下のような反例があります。辺の数が同じ必要はありますが、辺の数が同じだけでは十分ではありません。

実装

itertools モジュールの permutations で順列 $P$ を生成します。そして、高橋君のおもちゃの i 番目のボールを P[i]、j 番目のボールを P[j] とみなしたとき、青木くんのおもちゃと完全に一致するか確かめます。

コード

from itertools import permutations


def judge():
    def is_same_shape(P):
        for i in range(N):
            for j in range(N):
                if AB[P[i]][P[j]] != CD[i][j]: return False
        return True

    N, M = map(int, input().split())
    AB = [[False] * N for _ in range(N)]
    CD = [[False] * N for _ in range(N)]

    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        AB[a][b] = True
        AB[b][a] = True

    for _ in range(M):
        c, d = map(int, input().split())
        c, d = c - 1, d - 1
        CD[c][d] = True
        CD[d][c] = True

    for perm in permutations(range(N)):
        if is_same_shape(perm):
            return True
    return False


print("Yes" if judge() else "No")

D問題『Weak Takahashi』

問題ページ：D - Weak Takahashi
灰コーダー正解率：19.4 %
茶コーダー正解率：62.7 %
緑コーダー正解率：92.4 %

入力

$H$ : マスの縦幅
$W$ : マスの横幅
$C_{i,j}$ : マスの $i$ 行 $j$ 列の状態（.なら通行可能、#なら通行不可）

考察

単純な動的計画法で解きます。

あるマス $(i,\ j)$ を踏むとき、その上のマス $(i-1,j)$ か、左のマス $(i,j-1)$ から来る以外の方法はありません。左のマスと上のマスまでの最大距離が確定していれば、あとから $C_{i,j}$ の最大距離が更新されることはないので、動的計画法を使えます。

$dp[i][j]$ を $i$ 行目 $j$ 列目までの最大距離とします。$C_{i,j}$ が通行可能 . であるとき、$dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + 1$ です。ただし、$dp[0][0]=1$ 、その他のマスを $-INF$ （十分大きな負の値）で初期化します。通行不能#であるときは、更新を行いません。

コード

INF = 1 << 60


def main():
    H, W = map(int, input().split())
    C = [list(input()) for _ in range(H)]
    dp = [[-INF] * W for _ in range(H)]
    dp[0][0] = 1
    for row in range(H):
        for col in range(W):
            if row == col == 0:
                continue
            if C[row][col] == ".":
                d1 = dp[row - 1][col] if row - 1 >= 0 else -INF
                d2 = dp[row][col - 1] if col - 1 >= 0 else -INF
                dp[row][col] = max(d1, d2) + 1
    ans = 0
    for dp_row in dp:
        ans = max(ans, *dp_row)
    print(ans)


if __name__ == '__main__':
    main()

【AtCoder解説】PythonでABC232のA,B,C,D問題を制する！

目次

アプリ AtCoderFacts を開発しています