ABC245の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や拡散していただけると喜びます！
目次
ABC245 まとめ
A問題『Good morning』
B問題『Mex』
C問題『Choose Elements』
D問題『Polynomial division』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC245 まとめ
全提出人数: 9825人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB------ | 300 | 48分 | 6604(6379)位 |
| 400 | AB------ | 300 | 13分 | 5333(5109)位 |
| 600 | ABC----- | 600 | 76分 | 4317(4098)位 |
| 800 | ABC----- | 600 | 22分 | 3294(3082)位 |
| 1000 | ABCD---- | 1000 | 90分 | 2414(2203)位 |
| 1200 | ABCD---- | 1000 | 52分 | 1693(1484)位 |
| 1400 | ABCDE--- | 1500 | 114分 | 1157(955)位 |
| 1600 | ABCD-F-- | 1500 | 56分 | 775(583)位 |
| 1800 | ABCDEF-- | 2000 | 89分 | 508(330)位 |
| 2000 | ABCDEF-- | 2000 | 67分 | 331(174)位 |
| 2200 | ABCDEF-- | 2000 | 43分 | 210(83)位 |
| 2400 | ABCDEFG- | 2600 | 104分 | 123(39)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F | G | Ex |
|---|---|---|---|---|---|---|---|---|---|
| 灰 | 3343 | 92.0 % | 85.6 % | 29.3 % | 11.1 % | 0.3 % | 0.8 % | 0.0 % | 0.0 % |
| 茶 | 1474 | 97.8 % | 98.4 % | 75.6 % | 38.1 % | 1.5 % | 3.0 % | 0.0 % | 0.0 % |
| 緑 | 1156 | 97.4 % | 98.1 % | 93.8 % | 67.5 % | 8.5 % | 14.8 % | 0.4 % | 0.1 % |
| 水 | 704 | 97.9 % | 98.2 % | 97.9 % | 86.1 % | 38.9 % | 49.0 % | 1.3 % | 0.0 % |
| 青 | 389 | 96.9 % | 97.4 % | 97.7 % | 93.3 % | 77.9 % | 82.5 % | 13.9 % | 0.0 % |
| 黄 | 178 | 86.5 % | 86.5 % | 87.1 % | 88.2 % | 79.8 % | 89.3 % | 39.9 % | 1.1 % |
| 橙 | 32 | 90.6 % | 93.8 % | 87.5 % | 90.6 % | 87.5 % | 87.5 % | 81.2 % | 15.6 % |
| 赤 | 21 | 90.5 % | 90.5 % | 95.2 % | 95.2 % | 95.2 % | 90.5 % | 85.7 % | 52.4 % |
※表示レート、灰に初参加者は含めず
A問題『Good morning』
問題ページ：A - Good morning
灰コーダー正解率：92.0 %
茶コーダー正解率：97.8 %
緑コーダー正解率：97.4 %
入力
$A,\ B$ : 『ある日』の高橋君の起床時刻は $A$ 時 $B$ 分ちょうど（$A$ 時 $B$ 分 $0$ 秒）
$C,\ D$ : 『ある日』の青木君の起床時刻は $C$ 時 $D$ 分 $1$ 秒
考察
ふたりの起床時間を『時』と『分』で場合分けして解いてもいいですが、『ある日』がはじまってから、何分経った時点でふたりが起床したかを求めて比較するのが楽です。（高橋君は $0$ 秒、青木君は $1$ 秒に起きるので、分単位で同じなら高橋君が先です）
サンプル $3$ によると、$0$ 時 $0$ 分ちょうどはその日に含むらしいです。言われてみればそんな気がします。
高橋君、青木君が起きた時刻が $0$ 時 $0$ 分 から何分経っているかを求めて、早いほうが答えです。 ただし、青木君は $C$ 時 $D$ 分 $1$ 秒に起きますから、分単位で同じならば高橋君が先です。
$1$ 時間は $60$ 分ですから、$X$ 時 $Y$ 分 は、$0$ 時 $0$ 分から $60X+Y$ 分経過しています。
以上より、$60A+B\le60C+D$ が成り立つならTakahashi、成り立たないならばAokiを出力すればいいです。
コード
Takahashi と Aoki はタイプミスする恐れがあるので、心配なら問題文からコピーしてペーストするといいです。
def judge():
a, b, c, d = map(int, input().split())
fi = 60 * a + b
se = 60 * c + d
return fi <= se
print("Takahashi" if judge() else "Aoki")
B問題『Mex』
問題ページ：B - Mex
灰コーダー正解率：85.6 %
茶コーダー正解率：98.4 %
緑コーダー正解率：98.1 %
問題名の『Mex』とは、"Minimum EXcluded Value"の略で、定義はこの問題で答える値そのものです。Mexはたまに競技プログラミングの問題に出てくるので、知っておいて損はないです。
入力
$N$ : 数列 $A$ の長さ
$A_i$ : $A$ の $i$ 番目の整数の値
- $0\le{A_i}\le{2000}$
考察
数列 $A$ に含まれない、『最小の非負整数』を求める問題です。非負整数とは、負ではない整数、$0,\ 1,\ 2,\ 3,\dots$ のことです。
制約より、$A_i$ は最大で $2000$ です。最悪の場合でも $2001$ は $A$ に含まれません。
$0$ ～ $2001$ のどの整数が $A$ に一度でも出てくるかを記録して、一度も出てこない最小の数を答えればいいです。
実装
記録する範囲が 『$2000$ ちょうど』か『$2001$ ちょうど』のどちらかという『境界値』のミスは、非常に起こりやすいです。$0$ ～ $2010$ のように、適当に上限を適当に大きく取っておくテクニックが有効です。
コード
N = int(input())
ok = [True] * 2010
A = list(map(int, input().split()))
for x in A:
ok[x] = False
print(ok.index(True)) # ok.index(True)は0からはじめて一番最初にTrueが見つかったインデックスを返します
set を使う
この問題では、$A$ に ある整数がひとつ以上含まれているか含まれていないかだけが重要です。$S,\ A$ をset型（重複なし集合）とし、$S$ を $0$ から $2010$ のすべての整数として、集合 $S$ から集合 $A$ を引いた集合 $S-A$ の最小値を答えるのが簡単です。（集合 $S$ から $A$ を引いた差集合の最小値を答える）
N = int(input())
A = set(map(int, input().split()))
S = {i for i in range(2010)}
T = S - A
print(min(T))
C問題『Choose Elements』
問題ページ：C - Choose Elements
灰コーダー正解率：29.3 %
茶コーダー正解率：75.6 %
緑コーダー正解率：93.8 %
入力
$N$ : 整数列の長さ
$K$ : すべての $i\ (1\le{i}\le{N-1})$ について、 $|X_i-X_{i+1}|\le{K}$ を満たす必要がある
$A_i,\ B_i$ : それぞれ数列 $A$ と $B$ の $i$ 番目の要素
考察
- 数列 $X$ の $i$ 番目の要素は、$A_i$ か $B_i$ のどちらか
- すべての $i\ (1\le{i}\le{N-1})$ について、 $|X_i-X_{i+1}|\le{K}$ を満たす必要がある、つまり隣接する要素の差の絶対値が、$K$ 以下でなければいけない
前から $1$ 項ずつ決めていきます。
そのために記録しておく必要があるのは、「$i$ 番目まで数列 $X$ を決めたとき、末尾の $i$ 番目の要素 $X_i$ を $A_i$ にできる数列があるか、$X_i$ を $B_i$ にできる数列があるか」だけです。$2$ つ以上前で何を使ったかは関係ありません。なぜなら、条件は隣接する要素の差の絶対値が $K$ 以下かだけを見ているからです。
はじめは $A_1$ と $B_1$、どちらも使うことができます。
$X_i$ を $A_i$ にできるとき
- $|A_i-A_{i+1}|\le{K}$ を満たすなら、$i+1$ 番目を $A_{i+1}$ にできる
- $|A_i-B_{i+1}|\le{K}$ を満たすなら、$i+1$ 番目を $B_{i+1}$ にできる
$X_i$ を $B_i$ にできるとき
- $|B_i-A_{i+1}|\le{K}$ を満たすなら、$i+1$ 番目を $A_{i+1}$ にできる
- $|B_i-B_{i+1}|\le{K}$ を満たすなら、$i+1$ 番目を $B_{i+1}$ にできる
コード
def main():
def judge():
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a_ok, b_ok = True, True # 1個前でA, Bの要素を使うことができるか？
for i in range(N - 1):
a0, a1 = A[i], A[i + 1] # 前のA、今のA
b0, b1 = B[i], B[i + 1] # 前のB、今のB
na_ok, nb_ok = False, False # A[i+1]、B[i+1]を末尾として使えるか？
if a_ok: # 前の末尾がA[i]にできる場合
na_ok |= abs(a0 - a1) <= K # 次の末尾をA[i+1]にできるか判定
nb_ok |= abs(a0 - b1) <= K # 次の末尾をB[i+1]にできるか判定
if b_ok: # 前の末尾がB[i]にできる場合
na_ok |= abs(b0 - a1) <= K # 次の末尾をA[i+1]にできるか判定
nb_ok |= abs(b0 - b1) <= K # 次の末尾をB[i+1]にできるか判定
a_ok, b_ok = na_ok, nb_ok # 1つ次の要素の判定に移るので、古いフラグは捨てて書き換えます
return a_ok or b_ok
print("Yes" if judge() else "No")
if __name__ == '__main__':
main()
DPっぽく書く
実はこの問題の解法は、動的計画法（DP)の定義を満たしています。DPっぽい書き方をすると以下のコードになります。上の方法とやっていることは同じです。
def main():
def judge():
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
dp_a = [False] * N
dp_b = [False] * N
dp_a[0] = True
dp_b[0] = True
for i in range(N - 1):
if dp_a[i]:
dp_a[i + 1] |= abs(A[i] - A[i + 1]) <= K
dp_b[i + 1] |= abs(A[i] - B[i + 1]) <= K
if dp_b[i]:
dp_a[i + 1] |= abs(B[i] - A[i + 1]) <= K
dp_b[i + 1] |= abs(B[i] - B[i + 1]) <= K
return dp_a[N - 1] or dp_b[N - 1]
print("Yes" if judge() else "No")
if __name__ == '__main__':
main()
D問題『Polynomial division』
問題ページ：D - Polynomial division
灰コーダー正解率：11.1 %
茶コーダー正解率：38.1 %
緑コーダー正解率：67.5 %
入力
$N$ : $N$ 次多項式 $A(x)=A_Nx^N+A_{N-1}x^{N-1}+\dots+A_1x+A_0$ が与えられる
$M$ : $M$ 次多項式 $B(x)$ の係数を求める
$A_0,\ A_1,\dots,A_{N-1},A_N$ : $N$ 次多項式 $A(x)$ の各項の係数（昇べきの順、$N+1$ 項あります）
$C_0,\ C_1,\dots,C_{N+M-1},C_{N+M}$ : $N+M$ 次多項式 $C(x)$ の各項の係数（昇べきの順、$N+M+1$ 項あります）
考察
※たぶんコードをみたほうがはやいです
求めたいものは、$B(x)=\dfrac{C(x)}{A(x)}$ の $B$ の係数です。
$C(x)=A(x)B(x)$ を紙に書いて展開してみると、以下のことがわかります。（全部展開しなくていいです）
\begin{eqnarray}
C_{N+M}x^{N+M}&=&A_NB_Mx^Nx^M\\
C_{N+M-1}x^{N+M-1}&=&A_NB_{M-1}x^Nx^{M-1}+A_{N-1}B_Mx^{N-1}x^M\\
C_{N+M-2}x^{N+M-2}&=&A_NB_{M-2}x^Nx^{M-2}+A_{N-1}B_{M-1}x^{N-1}x^{M-1}+A_{N-2}B_Mx^{N-2}x^{M}\\
\dots
\end{eqnarray}
B_Mは簡単
$C_{N+M}$ に寄与するのは $A_N\times{B_M}$ の一つだけというのはすぐわかると思います。
$B_M=\dfrac{C_{N+M}}{A_N}$ で求めることができます。
それ以降は決まった分をCから引いてまたA_Nで割るだけ
次に、$C_{N+M-1}$ に寄与するのは $A_N\times{B_{M-1}}$ と $A_{N-1}\times{B_M}$ の $2$ 項ですが、$B_M$ は先ほど求めたので、左辺に移項してしまえば、$B_{M-1}=\dfrac{C_{N+M-1}-A_{N-1}B_M}{A_N}$ で求められます。
同様の手順を $B_0$ まで続けることで、$B$ のすべての係数を求めることができます。
具体的には、$B_i$ がひとつ決定するごとに、$A_0$ ～ $A_N$ をかけ合わせ、対応する $C$ の係数から引けばいいです。
備考
$B_0$ から決める方法もありますが、こちらは $A_0$ で割ることになります。$A_N$ は $0$ でないことが保証されていますが、$A_0$ は $0$ の場合もあります。この場合、ゼロ除算を回避するための工夫が必要です。
コード
def main():
N, M = map(int, input().split())
A = list(map(int, input().split()))
C = list(map(int, input().split()))
B = [0] * (M + 1)
for i in reversed(range(M + 1)):
B[i] = C[N + i] // A[N]
for j in range(N + 1):
C[i + j] -= A[j] * B[i]
print(*B)
if __name__ == '__main__':
main()
numpyを使う方法
検索して、NumPyのpoly1dクラスを使うと楽かもしれません。AtCoderジャッジサーバーのPyPyにはNumPyが入っていないので、Pythonで提出してください。
import numpy as np
def main():
N, M = map(int, input().split())
A = list(map(int, input().split()))[::-1]
C = list(map(int, input().split()))[::-1]
A_poly = np.poly1d(A)
C_poly = np.poly1d(C)
B = C_poly / A_poly
print(*map(int, reversed(B[0].c)))
if __name__ == '__main__':
main()