ABC224のA,B,C,D問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッター、マシュマロまでどうぞ！
Twitter: u2dayo
マシュマロ： [https://marshmallow-qa.com/u2dayo]
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
Discordサーバー（質問や記事の感想・リクエストなどどうぞ！） : https://discord.gg/jZ8pkPRRMT
よかったらLGTMや拡散していただけると喜びます！
目次
ABC224 まとめ
A問題『Tires』
B問題『Mongeness』
C問題『Triangle?』
D問題『8 Puzzle on Graph』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC224 まとめ
全提出人数: 6549人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB------ | 300 | 35分 | 4863(4656)位 |
| 400 | ABC----- | 600 | 117分 | 3979(3776)位 |
| 600 | ABC----- | 600 | 58分 | 3274(3072)位 |
| 800 | ABC----- | 600 | 35分 | 2568(2367)位 |
| 1000 | ABC----- | 600 | 21分 | 1931(1730)位 |
| 1200 | ABC----- | 600 | 11分 | 1405(1206)位 |
| 1400 | ABCD---- | 1000 | 55分 | 994(801)位 |
| 1600 | ABC--F-- | 1100 | 62分 | 686(501)位 |
| 1800 | ABCDE--- | 1500 | 69分 | 451(288)位 |
| 2000 | ABCDEF-- | 2000 | 101分 | 295(151)位 |
| 2200 | ABCDEF-- | 2000 | 82分 | 196(72)位 |
| 2400 | ABCDEF-- | 2000 | 64分 | 135(33)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|---|---|
| 灰 | 2862 | 98.1 % | 69.3 % | 35.1 % | 1.3 % | 0.3 % | 0.5 % | 0.0 % | 0.0 % |
| 茶 | 1195 | 99.5 % | 97.5 % | 80.6 % | 4.9 % | 1.1 % | 1.1 % | 0.2 % | 0.0 % |
| 緑 | 907 | 99.8 % | 99.0 % | 94.4 % | 23.7 % | 5.7 % | 4.4 % | 0.2 % | 0.0 % |
| 水 | 578 | 99.5 % | 99.3 % | 96.9 % | 53.3 % | 31.3 % | 21.1 % | 0.9 % | 0.0 % |
| 青 | 333 | 100.0 % | 100.0 % | 99.4 % | 76.3 % | 65.5 % | 58.3 % | 4.2 % | 0.3 % |
| 黄 | 160 | 93.1 % | 92.5 % | 93.1 % | 84.4 % | 76.9 % | 77.5 % | 32.5 % | 3.1 % |
| 橙 | 27 | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 96.3 % | 100.0 % | 81.5 % | 22.2 % |
| 赤 | 20 | 95.0 % | 95.0 % | 95.0 % | 90.0 % | 95.0 % | 95.0 % | 95.0 % | 70.0 % |
※表示レート、灰に初参加者は含めず
A問題『Tires』
問題ページ：A - Tires
灰コーダー正解率：98.1 %
茶コーダー正解率：99.5 %
緑コーダー正解率：99.8 %
入力
$S$ : 文字列（末尾はerかistのどちらかで、必ず $2$ 文字以上）
コード
S = input()
print("Yes" if S[-2:] == "er" else "No")
もっと手を抜くなら、erの最後の $1$ 文字はr、ist はtで違いますから、最後の $1$ 文字がrかどうか判定するだけでもいいです。
S = input()
print("Yes" if S[-1] == "r" else "No")
B問題『Mongeness』
問題ページ：B - Mongeness
灰コーダー正解率：69.3 %
茶コーダー正解率：97.5 %
緑コーダー正解率：99.0 %
入力
$H,W$ : マス目の縦幅、横幅（それぞれ最大 $50$）
$A_{i,j}$ :マス $(i,j)$、すなわち上から $i$ 行目、右から $j$ 行目 には整数 $A_{i,j}$ が書かれている
考察
$4$ 重ループですべての $i_1\lt{i_2}$ および $j_1\lt{j_2}$ を満たす $(i_1,i_2,j_1,j_2)$ の組を全探索して、すべての組が$A_{i_1,j_1}+A_{i_2,J_2} \le A_{i2,j1}+A_{i1,j2}$ を満たすか確認すればいいです。
実装
判定部分を関数に分けて、$A_{i_1,j_1}+A_{i_2,J_2} \le A_{i2,j1}+A_{i1,j2}$ を満たさない組が $1$ つでもあれば、すぐに Falseを返すのがいいです。
$A_{i_1,j_1}+A_{i_2,J_2} \le A_{i2,j1}+A_{i1,j2}$ を満たさないとはつまり、$A_{i_1,j_1}+A_{i_2,J_2} \gt A_{i2,j1}+A_{i1,j2}$ ということです。
ループ変数名を工夫すると間違えづらいのでおすすめです。二次元のグリッドを扱う問題では、row（行）column（列）からとって、row、colというループ変数名にするのがいいです。
コード
def judge():
for row2 in range(H):
for row1 in range(row2):
for col2 in range(W):
for col1 in range(col2):
if A[row1][col1] + A[row2][col2] > A[row2][col1] + A[row1][col2]:
return False
return True
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
print("Yes" if judge() else "No")
C問題『Triangle?』
問題ページ：C - Triangle?
灰コーダー正解率：35.1 %
茶コーダー正解率：80.6 %
緑コーダー正解率：94.4 %
入力
$N$ : 点の数
$X_i, Y_i$ : 点 $i$ の座標（整数）
考察
『$3$ 点を選んで、選ばれた $3$ 点を線分で結んだ図形が正の面積を持つ三角形になる』条件は、『$3$ 点が一直線上に並んでいないこと』です。$3$ 点が一直線上に並んでいる場合、面積のある三角形にはならず、線分になってしまうからです。
選んだ $3$ 点 $A,B,C$ の座標をそれぞれ $A(x_1,y_1)$、$B(x_2,y_2)$、$C(x_3,y_3)$とすると、『$3$ 点が一直線上に並んでいる』条件は、線分 $AB$ と $AC$ の傾きが等しいことです。数式で表すと
\frac{y_2-y_1}{x_2-x_1} = \frac{y_3-y_1}{x_3-x_1}\\
分母を払って\\
(y_2-y_1)\times{(x_3-x_1)}=(y_3-y_1)\times{(x_2-x_1)}
です。
すべての点の組を $3$ 重ループで全探索して、この判定式を満たさない（$3$ 点が一直線上に並んでおらず、三角形になっている）組み合わせの数を数えればいいです。
コード
def solve():
ans = 0
for p1 in range(N):
x1, y1 = points[p1]
for p2 in range(p1):
x2, y2 = points[p2]
for p3 in range(p2):
x3, y3 = points[p3]
if (y2 - y1) * (x3 - x1) != (y3 - y1) * (x2 - x1):
ans += 1
return ans
N = int(input())
points = []
for _ in range(N):
x, y = map(int, input().split())
points.append((x, y))
print(solve())
D問題『8 Puzzle on Graph』
問題ページ：D - 8 Puzzle on Graph
灰コーダー正解率：1.3 %
茶コーダー正解率：4.9 %
緑コーダー正解率：23.7 %
入力
*$M$ : 辺の数
$u_i,v_i$ : 辺 $i$ は頂点 $u_i$ と $v_i$ をつないでいる
$p_j$ : 初期状態で、コマ $j$ は頂点 $p_j$ に置いてある *
考察
この問題は幅優先探索（BFS）を使って、移動回数が少ない順にマスの状態を全探索すれば解くことができます。マスの状態は、$9$ 頂点に 空きマス含め $9$ 種類のコマが置いてあるため、全部で $9!=362880$ 通りしかありません。
BFSの計算量は $O(VE)$ ですから、最大で $V=362880,E=36$ の制約では実行時間制限（$4$ sec）に間に合い、ACを取ることが可能です。
実装
基本的に、盤面の状態はstr型（数字の"1"～"9"、"9"は空きマスを表す）のリストstateでもっておきます。state[i]は、頂点番号iにコマstate[i]（"1"～"9"）が存在することを表します。state=["1", "2", "3", "4", "5", "6", "7", "8", "9"]ならば、パズルが完成したことになります。
すでに訪れた盤面の状態を管理するためにset型を使いたいのですが、set型にはリストのようなミュータブル（変更可能）オブジェクトを追加することができません。そこで、必要な場合にリストを''.join(state)で文字列に変換したものを得て、set型への追加や、存在判定をします。
BFSでは、空いている頂点をstate.index("9")で取得し、その頂点から辺でつながっている頂点に置いてあるコマを、空きマスに移動させます。
コード
from collections import deque
def main():
def make_start():
"""
コマjはP[j]に置かれています。"9"が空きマスということにします
str型のリストにしたほうが、後々都合が良いです（''.join(state)で文字列に変換する必要があるため）
"""
start = ["9"] * 9
for piece, v in enumerate(P, 1):
start[v] = str(piece)
return start
def bfs(start):
def to_str(state): # setに追加不能なstate: List[str]を、setに追加可能なstrに変換します
return ''.join(state) # いちいちこれを打つのが面倒なため、関数にしておきます
goal = [str(i + 1) for i in range(9)] # ["1", "2", "3", "4", "5", "6", "7", "8", "9"] です
seen = set() # 既に探索した状態を管理します。リストはsetに追加できないので、リストを文字列に変換したものを追加します
que = deque()
que.append((start, 0)) # 現在のマス目の状態、移動回数
while que:
state, d = que.popleft()
if state == goal:
return d
u_empty = state.index("9") # 空マスの頂点番号を取得し、そこに辺で繋がっている頂点に置いてあるコマを移動させます
for v in G[u_empty]:
n_state = state[:] # 現在の状態をコピーします
n_state[u_empty], n_state[v] = n_state[v], n_state[u_empty] # # コマを移動します
ns_str = to_str(n_state) # setで存在判定をするために、strに変換します
if ns_str not in seen:
seen.add(ns_str)
que.append((n_state, d + 1))
return -1
"""
コマは1～8の8種類、頂点は-1して、0～8の9頂点とします
コマが置かれていない「空の頂点」には、コマ9が置かれていることにします
マスの状態は、『頂点i』に『コマj』が置いてある、というリストで管理します
"""
# ここは 入力を受け取って辺から無向グラフを構築しているだけです
M = int(input())
G = [[] for _ in range(9)] # 無向グラフです
for _ in range(M):
u, v = (x - 1 for x in map(int, input().split()))
G[u].append(v)
G[v].append(u)
P = [x - 1 for x in map(int, input().split())] # Pの中身は頂点番号ですから、それぞれ-1して0はじまりにします
start = make_start() # 最初の盤面の状態を、文字列のリストにして得ます
print(bfs(start))
if __name__ == '__main__':
main()