ABC240のA,B,C,D,E問題を、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や拡散していただけると喜びます！
目次
ABC240 まとめ
A問題『Edge Checker』
B問題『Count Distinct Integers』
C問題『Jumping Takahashi』
D問題『Strange Balls』
E問題『Ranges on Tree』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC240 まとめ
全提出人数: 8931人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB------ | 300 | 14分 | 5758(5525)位 |
| 400 | AB------ | 300 | 5分 | 4741(4508)位 |
| 600 | ABC----- | 600 | 28分 | 3843(3632)位 |
| 800 | ABCD---- | 1000 | 83分 | 2999(2792)位 |
| 1000 | ABCD---- | 1000 | 34分 | 2236(2031)位 |
| 1200 | ABCD-F-- | 1500 | 76分 | 1608(1410)位 |
| 1400 | ABCDE--- | 1500 | 46分 | 1127(931)位 |
| 1600 | ABCDEF-- | 2000 | 109分 | 753(576)位 |
| 1800 | ABCDEF-- | 2000 | 82分 | 487(331)位 |
| 2000 | ABCDEF-- | 2000 | 64分 | 302(177)位 |
| 2200 | ABCDEF-- | 2000 | 50分 | 182(85)位 |
| 2400 | ABCDEF-- | 2000 | 32分 | 109(38)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F | G | Ex |
|---|---|---|---|---|---|---|---|---|---|
| 灰 | 3034 | 97.9 % | 93.3 % | 23.1 % | 18.4 % | 3.0 % | 0.5 % | 0.0 % | 0.0 % |
| 茶 | 1350 | 99.0 % | 99.0 % | 72.4 % | 60.1 % | 12.4 % | 1.7 % | 0.0 % | 0.0 % |
| 緑 | 1047 | 97.8 % | 97.5 % | 93.7 % | 89.4 % | 51.4 % | 8.0 % | 0.2 % | 0.0 % |
| 水 | 674 | 98.2 % | 98.2 % | 97.9 % | 96.6 % | 86.5 % | 37.5 % | 1.2 % | 0.1 % |
| 青 | 394 | 98.0 % | 98.2 % | 98.2 % | 97.2 % | 98.0 % | 76.7 % | 6.1 % | 0.0 % |
| 黄 | 178 | 83.7 % | 84.3 % | 84.3 % | 85.4 % | 85.4 % | 75.8 % | 25.3 % | 2.2 % |
| 橙 | 42 | 83.3 % | 83.3 % | 83.3 % | 83.3 % | 81.0 % | 76.2 % | 52.4 % | 7.1 % |
| 赤 | 20 | 95.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 60.0 % | 25.0 % |
※表示レート、灰に初参加者は含めず
A問題『Edge Checker』
問題ページ：A - Edge Checker
灰コーダー正解率：97.9 %
茶コーダー正解率：99.0 %
緑コーダー正解率：97.8 %
入力
$a,b$ : $2$ 点の番号
- $a\lt{b}$
考察
$a<b$ なので、基本的には $b-a=1$ ならば隣あっていますが、$a=1,b=10$ のケースだけはこれに当てはまりません。
$a=1,b=10$ のパターンだけ特別に判定するといいでしょう。
コード
a, b = map(int, input().split())
if b - a == 1 or (a, b) == (1, 10):
print("Yes")
else:
print("No")
B問題『Count Distinct Integers』
問題ページ：B - Count Distinct Integers
灰コーダー正解率：93.3 %
茶コーダー正解率：99.0 %
緑コーダー正解率：97.5 %
入力
$N$ : 正整数列 $a$ の長さ
$a_i$ : 正整数列 $a$ の $i$ 番目の要素
- $1\le{a_i}\le{10^9}$
考察
len(set(A)) で、リストやタプル A に含まれる要素の種類数が一発でわかります。
コード
N = int(input())
A = list(map(int, input().split()))
print(len(set(A)))
C問題『Jumping Takahashi』
問題ページ：C - Jumping Takahashi
灰コーダー正解率：23.1 %
茶コーダー正解率：72.4 %
緑コーダー正解率：93.7 %
入力
$N$ : ジャンプの回数
$X$ : 目的の座標（$X\le{10000}$）
$a_i,b_i$ : $i$ 回目のジャンプでは、$a_i$ か $b_i$ 正の方向に移動する
考察
動的計画法（DP）で解きます。
状態
$\mathrm{dp}[i][j]$ : $i$ 回ジャンプを行った時点で、座標 $j$ にいることができるなら True、できないなら False
初期値は、$\mathrm{dp}[0][0]$ のみ True で、ほかはFalseです。（$1$ 度もジャンプしていない時点では、座標 $0$ に存在するため）
正の方向にしかジャンプできませんから、座標 $X+1$ 以降からは絶対に座標 $X$ に到達不可能です。したがって、配列の二次元目は $X$ までで良いです。
遷移
$\mathrm{dp}[i][j]$ が True であれば、$i+1$ 回目のジャンプで
- 座標 $j$ から $a_i$ 正の方向にジャンプすることで座標 $j+a_i$ に移動し $\mathrm{dp}[i+1][j+a_i]$ を
Trueに - 座標 $j$ から $b_i$ 正の方向にジャンプすることで座標 $j+b_i$ に移動し $\mathrm{dp}[i+1][j+b_i]$ を
Trueに
することができます。
ジャンプしないという選択はできませんから、$\mathrm{dp}[i][j]$ が True でも、$\mathrm{dp}[i+1][j]$ が Trueになるとは限らないことに注意してください。
コード
def solve():
N, X = map(int, input().split())
dp = [[False] * (X + 1) for _ in range(N + 1)]
dp[0][0] = True
for i in range(N):
a, b = map(int, input().split())
for j in range(X + 1):
if dp[i][j]:
if j + a <= X:
dp[i + 1][j + a] = True
if j + b <= X:
dp[i + 1][j + b] = True
return dp[N][X]
print("Yes" if solve() else "No")
setを使う方法
$2$ つのセットを使っても実装できます。なお、 $a_i,b_i$ の制約が小さいので、$X+1$ 以上の座標を捨てずに持っていても実は問題ありません。
def solve():
N, X = map(int, input().split())
pre = {0}
for _ in range(N):
a, b = map(int, input().split())
cur = set()
for x in pre:
cur.add(x + a)
cur.add(x + b)
pre = cur
return X in cur
print("Yes" if solve() else "No")
多倍長整数を使う方法
整数を二進法表記したときの $i$ 桁目が $1$ なら $i$ が True、 $0$ なら False とみなして、ビット演算でDPを行います。
遷移は $a_i$ ビット、 $b_i$ ビット左シフトしたものの論理和を取ればいいです。
C++でいうところのbitsetDPです。難しめの問題だと、この手法による高速化が必要になる場合もあります。
def solve():
N, X = map(int, input().split())
dp = 1
for _ in range(N):
a, b = map(int, input().split())
dp = (dp << a) | (dp << b)
return dp >> X & 1
print("Yes" if solve() else "No")
D問題『Strange Balls』
問題ページ：D - Strange Balls
灰コーダー正解率：18.4 %
茶コーダー正解率：60.1 %
緑コーダー正解率：89.4 %
入力
$N$ : ボールの数
$a_i$ : $i$ 回目に筒に落とすボールには、$a_i$ が書かれている（$a_i$ は $2$ 以上の整数）
考察
スタックというデータ構造を使って解きます。スタックは、後入れ先出し（LIFO）の構造でデータを保持するものです。Pythonでは、普通のリストでスタックを実現できます。単に入れるときはappend、出すときはpopを使うだけです。
たとえば、入力例 $1$ の $\{3,2,3,2,3\}$ をリストでシミュレートすると、リストは以下のように変化します。
[]
3:[3]
2:[3, 2]
3:[3, 2, 3]
2:[3, 2, 3, 2]
3:[3, 2, 3, 2, 2] -> [3, 2, 3]
しかし、$k$ が書かれたボール を入れるたびに、リストの後ろから $k-1$ 個を確認してボールが消えるか判定していては、計算量が $O(N^2)$ となるため間に合いません。
そこで、そのままリストに数字を入れるのではなく、$(ボールに書かれた整数、ボールの連続する個数)$ の形でリストに入れます。こうすれば、筒の一番上でどの整数が何個連続しているかを、リストの一番後ろを確認するだけで済みます。
入力例 $2$ の $\{2,3,2,3,3,3,2,3,3,2\}$ をこの形式でシミュレートすると、リストは以下のように変化します。
2: [[2, 1]]
3: [[2, 1], [3, 1]]
2: [[2, 1], [3, 1], [2, 1]]
3: [[2, 1], [3, 1], [2, 1], [3, 1]]
3: [[2, 1], [3, 1], [2, 1], [3, 2]]
3: [[2, 1], [3, 1], [2, 1], [3, 3]]
-> [[2, 1], [3, 1], [2, 1]]
2: [[2, 1], [3, 1], [2, 2]]
-> [[2, 1], [3, 1]]
3: [[2, 1], [3, 2]]
3: [[2, 1], [3, 3]]
-> [[2, 1]]
2: [[2, 2]]
-> []
コード
def main():
N = int(input())
A = list(map(int, input().split()))
L = [[-1, 0]] # 番兵として絶対取り出されない要素を1個入れておくと楽です
ans = 0
for cx in A:
tx, cnt = L[-1]
ans += 1 # ボールを1個入れる
if cx == tx: # 筒の一番上と同じ数の場合、連続数を+1
L[-1][1] += 1
else: # 違う数なら、[cx, 1]を筒の一番上に追加
L.append([cx, 1])
if L[-1][0] == L[-1][1]: # 筒の一番上で、cxがcx個連続したら、消す
L.pop()
ans -= cx # ボールがcx個消えたので減らす
print(ans)
main()
E問題『Ranges on Tree』
問題ページ：E - Ranges on Tree
灰コーダー正解率：3.0 %
茶コーダー正解率：12.4 %
緑コーダー正解率：51.4 %
入力
$N$ : 木の頂点数
$u_i,v_i$ : $i$ 本目の辺は頂点 $u_i$ と $v_i$ を結ぶ
考察
葉からボトムアップに考えます。
葉はL_u=R_u
どの $2$ つの葉を選んでも、当然ですが部分木の集合に共通部分はありません。（葉の部分木はその葉の頂点 $1$ 個だけからなるため）
そのため、葉同士の区間は交わらないようにする必要があります。$L,R$ の 最大値を最小にしたいので、葉は $(L_u,R_u)=(1,\ 1), (2,\ 2), (3,\ 3),\dots$ と $1$ から順に $L_u=R_u$ となるようにして値を節約します。
親のL_uは子の最小、R_uは子の最大
次に、葉の $1$ 階層上の頂点の $L_u,R_u$ を決めます。これは、以下のように決定することで無駄なく、$L_u$ ～ $R_u$ ですべての葉頂点と共通区間があるようにできます。
- $L_u=\mathrm{min}({L_v\ |\ v\ は\ u\ の子 })$
- $R_u=\mathrm{max}({R_u\ |\ v\ は\ u\ の子 })$
さらに上の階層の頂点も、同様にして決められます。
最終的に、例えば葉の数が $9$ 個だとすると、$L_1,R_1=\ (1,9)$ となります。
図解
言葉だけだとわかりづらいと思うので、図を用意しました。
- 赤字は $L_i$
- 青字は $R_i$
- 葉頂点は緑でマークしてある
- 緑の下線がそれぞれ親の $L_u,R_u$ に採用された最小・最大の $L_u,R_u$
対応する入力
16
1 2
1 3
2 4
2 5
3 6
4 7
4 8
6 9
6 10
8 11
8 12
10 13
10 14
10 15
10 16
対応する出力
後述のコードの出力は以下になります。図と同じことが確認できます。（子を探索する順番によって数字が入れ替わる場合がありますが、いずれも正解です）
1 9
1 4
5 9
1 3
4 4
5 9
1 1
2 3
5 5
6 9
2 2
3 3
6 6
7 7
8 8
9 9
実装
解説のアルゴリズムを、深さ優先探索（DFS）で実装すればいいです。
コード
PyPyは再帰に弱いので、Pythonで出してください。
import sys
sys.setrecursionlimit(10 ** 6) # 再帰上限を上げないとREになります
readline = sys.stdin.readline # 一応高速な入力を使っておきましょう（readlineは改行文字も受け取るので注意）
def main():
leaf_count = 0 # これまでの葉の数
def dfs(u, p):
nonlocal leaf_count
is_leaf = True
l_min = r_max = leaf_count + 1
for v in G[u]:
if v == p:
continue
is_leaf = False # 子頂点があるので、葉ではない
dfs(v, u)
l_min = min(l_min, L[v])
r_max = max(r_max, R[v])
if is_leaf:
leaf_count += 1
L[u], R[u] = l_min, r_max
N = int(readline())
G = [[] for _ in range(N + 1)]
for _ in range(N - 1):
a, b = map(int, readline().split())
G[a].append(b)
G[b].append(a)
L = [0] * (N + 1)
R = [0] * (N + 1)
dfs(1, 0)
for l, r in zip(L[1:], R[1:]):
print(l, r)
main()