ABC248のA,B,C,D,E,F問題を、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や拡散していただけると喜びます！
目次
ABC248 まとめ
A問題『Lacked Number』
B問題『Slimes』
C問題『Dice Sum』
D問題『Range Count Query』
E問題『K-colinear Line』
F問題『Keep Connect』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC248 まとめ
全提出人数: 8471人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB------ | 300 | 37分 | 5976(5722)位 |
| 400 | AB------ | 300 | 15分 | 4835(4581)位 |
| 600 | AB------ | 300 | 7分 | 3995(3741)位 |
| 800 | ABC----- | 600 | 37分 | 3099(2856)位 |
| 1000 | ABCD---- | 1000 | 87分 | 2297(2061)位 |
| 1200 | ABCD---- | 1000 | 30分 | 1648(1418)位 |
| 1400 | ABCDE--- | 1500 | 89分 | 1155(931)位 |
| 1600 | ABCDE--- | 1500 | 55分 | 795(582)位 |
| 1800 | ABCDEF-- | 2000 | 114分 | 520(335)位 |
| 2000 | ABCDEF-- | 2000 | 77分 | 328(174)位 |
| 2200 | ABCDEF-- | 2000 | 54分 | 199(87)位 |
| 2400 | ABCDEF-- | 2000 | 37分 | 119(41)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F | G | Ex |
|---|---|---|---|---|---|---|---|---|---|
| 灰 | 3003 | 94.6 % | 87.8 % | 9.8 % | 9.7 % | 1.1 % | 0.2 % | 0.0 % | 0.0 % |
| 茶 | 1394 | 98.5 % | 97.6 % | 36.0 % | 35.9 % | 4.0 % | 0.1 % | 0.1 % | 0.0 % |
| 緑 | 1086 | 97.8 % | 97.2 % | 74.7 % | 74.6 % | 26.1 % | 3.0 % | 0.4 % | 0.0 % |
| 水 | 706 | 98.7 % | 98.9 % | 94.5 % | 93.2 % | 71.0 % | 15.0 % | 1.0 % | 0.0 % |
| 青 | 381 | 97.9 % | 97.9 % | 97.9 % | 97.1 % | 91.9 % | 54.9 % | 5.5 % | 0.8 % |
| 黄 | 200 | 92.5 % | 92.5 % | 91.5 % | 90.0 % | 85.5 % | 72.0 % | 14.0 % | 5.0 % |
| 橙 | 32 | 93.8 % | 90.6 % | 90.6 % | 93.8 % | 90.6 % | 90.6 % | 37.5 % | 9.4 % |
| 赤 | 26 | 96.2 % | 96.2 % | 96.2 % | 96.2 % | 96.2 % | 100.0 % | 92.3 % | 42.3 % |
※表示レート、灰に初参加者は含めず
A問題『Lacked Number』
問題ページ：A - Lacked Number
灰コーダー正解率：94.6 %
茶コーダー正解率：98.5 %
緑コーダー正解率：97.8 %
入力
$S$ : 長さがちょうど $9$ の文字列で、0から9までのうち、ちょうど $1$ つの数字を除いた $9$ 種類の数字が一度ずつ登場する
考察
x not in S で、文字列 S に文字列 x が出現していないことを判定できるので、0から9までforループで調べればいいです。
コード
def solve():
S = input()
for i in range(10):
if str(i) not in S:
return i
print(solve())
B問題『Slimes』
問題ページ：B - Slimes
灰コーダー正解率：87.8 %
茶コーダー正解率：97.6 %
緑コーダー正解率：97.2 %
入力
$A$ : スライムの初期値
$K$ : すぬけくんが $1$ 回叫ぶたびに、スライムは $K$ 倍に増殖する（$K\ge{2}$）
$B$ : スライムが $B$ 匹以上になるためには、すぬけくんが最小で何回叫ぶ必要があるか求める（$B\le{10^9}$）
考察
スライムの増殖をシミュレートして、すぬけくんが何回叫んだ時点で $B$ 匹以上になるか求めれば解けます。
一番回数がかかるのは、スライムの初期値が最小の $A=1$、スライムの目標値が最大の $B=10^9$、スライムの増殖倍率が最低の $K=2$ の場合です。ここで、 $10^3\lt{2^{10}}$ より、$10^9\lt{2^{30}}$ です。したがって、一番回数がかかるパターンでも $30$ 回程度で済むと見積もることができます。
コード
def solve():
A, B, K = map(int, input().split())
curr = A # スライムが今何匹か
ans = 0 # すぬけくんが叫んだ回数
while not (curr >= B):
ans += 1 # すぬけくんが叫ぶと
curr *= K # スライムがK倍に増える
return ans
print(solve())
C問題『Dice Sum』
問題ページ：C - Dice Sum
灰コーダー正解率：9.8 %
茶コーダー正解率：36.0 %
緑コーダー正解率：74.7 %
入力
$N$ : 長さ $N$ の数列（$N\le50$）
$M$ : 数列の各要素は $1$ 以上 $M$ 以下（$M\le50$）
$K$ : 数列の総和は $K$ 以下（$N\le{K}\le{NM}$）
考察
以下の条件を満たす数列がいくつあるか答える問題です。
- 長さ $N$ の数列
- 各要素は $1$ 以上 $M$ 以下の整数
- 要素の総和が $K$ 以下
長さ $N$、各要素が $1$ 以上 $M$ 以下の数列は $M^N$ 通りありますから、当然全探索は不可能です。
動的計画法で解きます。
状態
$\mathrm{dp}[i][j]$ : 数列の $i$ 番目まで決めて、総和が $j$ であるものの数
答え
$\mathrm{dp}[N][1]+\mathrm{dp}[N][2]+\dots+\mathrm{dp}[N][K]$
初期値
$\mathrm{dp}[0][0]=1$ : 数列の $0$ 番目まで決めて、総和が $0$
遷移
数列の前から $1$ 個ずつ順番に要素を決めていきます。
『$i$ 番目 $A_i$ まで決めて、総和が $j$ の数列』から、$i+1$ 番目の要素 $A_{i+1}$ を決めたときの遷移を考えます。 $A_{i+1}$ を $1$ 以上 $M$ 以下の整数 $k$ にすると、次の状態は『 $i+1$ 番目 $A_{i+1}$ まで決めて、総和が $j+k$ の数列』になります。
したがって、すべての $0\le{j}\le{K}$, $1\le{k}\le{M}$ の組に対して
$\mathrm{dp}[i+1][j+k]\ +=\mathrm{dp}[i][j]$
とすればいいです。$998244353$ で割った余りを求めるのを忘れないようにしてください。
コード
MOD = 998244353
def main():
N, M, K = map(int, input().split())
dp = [[0] * (K + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
for j in range(K):
for k in range(1, M + 1):
if j + k > K: # Kを超える数列はどうでもいいです
break
dp[i + 1][j + k] += dp[i][j]
dp[i + 1][j + k] %= MOD
print(sum(dp[-1]) % MOD)
if __name__ == '__main__':
main()
D問題『Range Count Query』
問題ページ：D - Range Count Query
灰コーダー正解率：9.7 %
茶コーダー正解率：35.9 %
緑コーダー正解率：74.6 %
入力
$N$ : 数列の長さ
$A_i$ : 数列の $i$ 番目の値（$1\le{A_i}\le{N}$）
$Q$ : クエリの数
クエリ
$L,R,X$ : $A_L,\dots,A_R$ のうち、値が $X$ であるものの数を答える
考察
もちろん、クエリごとに範囲をすべて確認して $X$ の個数を数えていてはとても間に合いません。
クエリに高速で答える
各クエリで重要なのは、値が $X$ の要素がどこに出てくるかだけです。
したがって、クエリは次のように言い換えることができます。
『$X$ と $X$ 以外からなる長さ $N$ の数列があります。この数列の $L$ 番目から $R$ 番目に、$X$ は何個出てくるか答えてください。』
さらに
($L$ 番目 から $R$ 番目の $X$ の個数) $=$ ($1$ 番目 から $R$ 番目の $X$ の個数) $-$ ($1$ 番目 から $L-1$ 番目の $X$ の個数)
ですから、『$1$ 番目 から $K$ 番目の $X$ の個数』を高速に求められればいいです。
二分探索
『$1$ 番目 から $K$ 番目の $X$ の個数』を高速に求めるために、二分探索を使います。
あらかじめ、値 $x=1,2,\dots,N$ がそれぞれ $A$ の何番目に出てくるか、昇順に並べた配列 $pos_x$ を作っておきます。例えば、$A=\{3,1,4,1,5\}$ なら
A == [3, 1, 4, 1, 5]
pos[1] == [2, 4]
pos[2] == []
pos[3] == [1]
pos[4] == [3]
pos[5] == [5]
とします。
各クエリでは、$B=pos_X$ として、配列 $B$ に含まれる $R$ 以下の要素の個数を bisect_right(B, R)、$L$ 未満の要素の個数を bisect_left(B, L) で求めます。答えはbisect_right(B, R) - bisect_left(B, L) です。
コード
from bisect import bisect_left, bisect_right
def main():
N = int(input())
A = list(map(int, input().split()))
pos = [[] for _ in range(N + 1)]
for i, x in enumerate(A, 1):
pos[x].append(i)
Q = int(input())
for _ in range(Q):
L, R, X = map(int, input().split())
B = pos[X]
print(bisect_right(B, R) - bisect_left(B, L))
if __name__ == '__main__':
main()
E問題『K-colinear Line』
問題ページ：E - K-colinear Line
灰コーダー正解率：1.1 %
茶コーダー正解率：4.0 %
緑コーダー正解率：26.1 %
入力
$N$ : 点の個数（$N\le{400}$）
$K$ : $K$ 個以上の点を通る直線がいくつあるか答える
$X_i,Y_i$ : 点 $i$ の座標
考察
まず、$K=1$ ならば Infinity です。適当な $1$ 点を通る直線はいくらでも引くことができるからです。
そうでないとき、すなわち $K\ge2$ のとき、答えは有限です。$N$ 点から $2$ 点を選んだとき、その $2$ 点を通る直線はただ $1$ つだけ存在します。したがって、$N$ 点のうち $2$ 点以上を通る直線は、最大でも $\dfrac{N(N-1)}{2}$ 本です。
2点を通る直線を全探索
$2$ 点を通る $\dfrac{N(N-1)}{2}$ 本の直線を全探索します。ただし、同一の直線を複数回判定しないように、以前にチェックした直線上にあった組ならば、スキップします。
各直線ごとに、何個の点が載っているかも $O(N)$ の全探索で求めて、$K$ 個以上点が乗っているかどうかを判定します。
$xy$ 平面上の $3$ 点が同一直線上にある条件は
$(x_2−x_1)(y_3−y_1)=(x_3−x_1)(y_2−y_1)$
です。
直線の数は $O(N^2)$、点の数は $O(N)$、判定は $O(1)$ですから、計算量は $O(N^3)$ です。
コード
def solve():
def is_colinear(p1, p2, p3):
return (X[p2] - X[p1]) * (Y[p3] - Y[p1]) == (X[p3] - X[p1]) * (Y[p2] - Y[p1])
def judge(a, b):
A = [a, b] # 点a, 点bを通る直線上の点
cnt = 2 # 点a, 点bの2点が初期値
for c in range(b + 1, N):
if is_colinear(a, b, c):
cnt += 1
A.append(c)
# この直線上の点同士は今後判定しない
for j in range(cnt):
for i in range(j):
seen[A[i]][A[j]] = True
return cnt >= K
N, K = map(int, input().split())
if K == 1:
return "Infinity"
X, Y = [], []
for _ in range(N):
x, y = map(int, input().split())
X.append(x)
Y.append(y)
seen = [[False] * N for _ in range(N)] # 既に見た直線上にある、2点の組は判定しない
ans = 0
for i in range(N):
for j in range(i + 1, N):
if not seen[i][j]:
ans += judge(i, j)
return ans
print(solve())
F問題『Keep Connect』
問題ページ：F - Keep Connect
灰コーダー正解率：0.2 %
茶コーダー正解率：0.1 %
緑コーダー正解率：3.0 %
入力
$N$ : $2N$ 頂点 $3N-2$ 辺のグラフについて考える
$P$ : 答えを素数 $P$ で割った余りを求める
考察
動的計画法で解きます。
上下の $2$ 点 をまとめて、$N$ 列あるとみなします。$i-1$ 列目まで状態が確定しているところに、次の列の $2$ 頂点と $0$ ～ $3$ 辺 を加えて、$i$ 列目を確定させます。
状態は以下の $3$ つです。
- 何列目まで確定させたか
- 使わなかった辺の数（取り除いた辺の数）
- グラフの状態
遷移は状態 $1$ つにつき、$3$ 辺を加えるか加えないかで $2^3=8$ 通り考えられますが、連結にならないことが確定するグラフの状態に遷移する場合もあるので実際はより少ないです。（例えば、$1$ つも辺を加えないのは、 $i-1$ 列目と $i$ 列目の間でグラフが分かれてしまうのでありえません）
図を書いてがんばって考えてみてください。
グラフの状態の詳細
列 $i$ の上の点を $a_i$、下の点を $b_i$ と表します。さらに、列 $1$ の上の点 $a_1$ が属する連結成分を $A$、下の点 $b_1$ が属する連結成分を $B$ とします。
列 $i$ まで確定させたとき、最終的にグラフが連結になりうるのは
状態 $0$ : $A$ と $B$ が連結でなく、$a_i$ は $A$ と連結、$b_i$ は $B$ と連結
状態 $1a$ : $A$ と $B$ が連結で、$a_i$ は $A$ および $B$ と連結で、 $b_i$ は連結でない
状態 $1b$ : $A$ と $B$ が連結で、$b_i$ は $A$ および $B$ と連結で、 $a_i$ は連結でない
状態 $2$ : $A$ と $B$ が連結で、$a_i$ も $b_i$ も $A$ および $B$ と連結
の $4$ 通りだけです。答えは 列 $N$ まで確定させたときの状態 $2$ です。
ただし、グラフの対称性より、状態 $1a$ と $1b$ は同一とみなせるので、実際は $3$ 通りの状態だけ考えればいいです。
遷移
$a_{i-1}$ と $a_i$ をつなぐ辺を上、$b_{i-1}$ と $b_i$ をつなぐ辺を下、$a_i$ と $b_i$ をつなぐ辺を中と呼ぶことにします。
上/下の1本辺を加える場合
- 状態 $2$ から状態 $1$ に遷移
上下2本辺を加える場合
- 状態 $0$ から状態 $0$、状態 $1$ から状態 $1$、状態 $2$ から状態 $2$ に遷移
上/下と中 の2本辺を加える場合
- 状態 $2$ から 状態 $2$ に遷移
上中下の3本辺を加える場合
- 状態 $0,1,2$ から状態 $3$ に遷移
コード
def main():
def solve():
N, P = map(int, input().split())
dpp0 = [0] * (N + 5)
dpp1 = [0] * (N + 5)
dpp2 = [0] * (N + 5)
dpp0[1] = 1
dpp2[0] = 1
for i in range(N - 1):
dpn0 = [0] * (N + 5)
dpn1 = [0] * (N + 5)
dpn2 = [0] * (N + 5)
for j in range(N):
# 上/下だけ1本
dpn1[j + 2] += 2 * dpp2[j]
# 上下2本
dpn0[j + 1] += dpp0[j]
dpn1[j + 1] += dpp1[j]
dpn2[j + 1] += dpp2[j]
# 上/下と中2本
dpn2[j + 1] += 2 * dpp2[j]
# すべて3本
dpn2[j] += dpp0[j] + dpp1[j] + dpp2[j]
for j in range(N + 5):
dpn0[j] %= P
dpn1[j] %= P
dpn2[j] %= P
dpp0 = dpn0
dpp1 = dpn1
dpp2 = dpn2
print(*dpp2[1:N])
solve()
if __name__ == '__main__':
main()