目次
AtCoder Beginner Contest 146 D～F問題メモ
D - Coloring Edges on Tree
問題
- $N$ 頂点の木の $N-1$ 本の辺を、何色かで塗り分ける
- 1つの頂点に繋がる任意の2辺は同じ色であってはいけない
- 使う色の数を最も少なくした時、各辺の塗り方の一例を求めよ
- $2 \le N \le 10^5$
解法
辺彩色問題。
色は1～からの番号で表すとする。
適当な頂点①から、順に辺で繋がった頂点を探索し、辺の色を、まだ使われてない最小の色で確定していけば、条件を満たすように作れる。
①--- 1 ---②--- 2 ---⑤
| `-- 3 ---⑥
|--- 2 ---③--- 1 ---⑦
| `-- 3 ---⑧
`--- 3 ---④--- 1 ---⑨
`-- 2 ---⑩
木の場合は、根から順に確定する限り、相手先の頂点の他の辺が必ず未確定である（後でその頂点の処理時に何とでも調整できる）ので、この方法が使える。
今回は木なので大丈夫だが、グラフに閉路があると、相手先に繋がる他の辺が確定しているかも知れず、1つの頂点だけでは決められないのでちょっと面倒。
①から、②③に繋がる辺の色を確定後、②について処理
①--- 1 --② ←②からは2が使えないことが見えない
\ /
2 ○ ←1と2が使えない
\ /
③
この場合でも、次数の最大値 $k$ または $k+1$ 色あれば、辺彩色可能らしい（Vizingの定理）
import sys
n = int(input())
links = [set() for _ in range(n)]
for i, line in enumerate(sys.stdin):
a, b = map(int, line.split())
a -= 1
b -= 1
links[a].add((i, b))
links[b].add((i, a))
ans = [-1] * (n - 1)
k = max(map(len, links))
q = [(0, -1)]
fixed = set()
while q:
v, c = q.pop()
color = 1
if c == color:
color += 1
for i, u in links[v]:
if ans[i] != -1:
continue
ans[i] = color
q.append((u, color))
color += 1
if c == color:
color += 1
print(k)
print('\n'.join(map(str, ans)))
E - Rem of Sum is Num
問題
- 長さ $N$ の正整数列 $a_1,a_2,...,a_N$ と正の整数 $K$ が与えられる
- $A$ の空でない連続する部分列であって、要素の和を $K$ で割った余りが要素の数と等しくなるものの数を求めよ
- 2つの部分列が列として同じでも、取り出す位置が異なるならば区別する
- $1 \le 2 \times 10^5$
- $1 \le a_i \le 10^9$
- $1 \le K \le 10^9$
例
N=5 K=4
1 4 2 3 5
要素数 和%K
(1) 1 1
(1,4,2) 3 3
(4,2) 2 2
(5) 1 1
以上の4つ
解法
とりあえず足し算を $K$ で割った余りのみ必要なので、$a_i$ やその計算過程で出てくる要素は、$K$ で割った余りに置き換えても問題ない。
連続する区間の和なので、累積和を計算しておけばよさそう。
A : 1 4 2 3 5 A%K : 1 0 2 3 1 累積 : 1 1 3 2 3
しかし、この問題では、1つ区間を伸ばすたびに、求められる累積和が増えていくという点が厄介。
↓ ここを左端として考えたとき
累積%K: 1 1 3 2 3
↑ ↑ ↑ ↑___ 要素数が K 以上の区間は、和%K が K 以上にならないため、あり得ない
｜ ｜ `------ ここが3ならいい = (a1,a2,a3) が条件を満たす
｜ `--------- ここが2ならいい = (a1,a2) が条件を満たす
`------------ ここが1ならいい = (a1) が条件を満たす
左端から何個先かによって求められる累積和が異なるので、(index, 累積和)の組で情報を持っておかねばならず、計算量が大きくなりすぎる。
ここで、あらかじめ累積和に1ずつ減っていく数を足しておくと、右端として条件を満たす値が1種類となり、区間長を考慮する必要がなくなると思いつく。
↓ ここを左端として考えたとき
累積 : 1 1 3 2 3
足す数: 0 3 2 1 0
合計 : 1 0 1 3 3
↑ ↑ ↑
｜ ｜ `------ ここが1ならいい
｜ `--------- ここが1ならいい
`------------ ここが1ならいい
この1ずつ減っていく数を足した結果を、“累積和改”と呼ぶことにする。
こうすれば「左端から $K-1$ 個先までの区間に、累積和改が $x$ である箇所が何個あるか」さえ保持しておけばよいので、尺取法で更新していける。
累積和改: 1 0 1 3 3
|-------| 0:1個 1:2個
x o ↓-1 ↓+1
|-------| 0:1個 1:1個 3:1個
x o ↓-1 ↓+1
|-------| 1:1個 3:2個
では、左端を固定した時に、求めるべき累積和改の値 $x$ は、何であればよいか。
ここまでの数列の計算を追っていく。左端として固定する要素を $a$ とする。
A : a ... ideal(仮) : 1 2 3 ... 区間の右端とできる累積和（aからはじめた値） ideal(仮) : 1-a 2-a 3-a ... 区間の右端とできる累積和（aを考慮した値） 累積和 : b ... 実際のaまでの累積和 ideal : 1-a+b 2-a+b 3-a+b ... 区間の右端とできる実際の累積和 足される数: c c-1 c-2 ... 累積和改を求める際に足される数 累積和改 : 1-a+b+c 1-a+b+c 1-a+b+c 区間の右端とできる累積和改の値
よって、各 $i$ について、累積和改の $i～i+K-1$ の中に存在する $1-a_i+b_i+c_i$ の個数が、条件を満たす区間の数となる。
from collections import Counter
from itertools import accumulate
n, k = map(int, input().split())
aaa = list(map(int, input().split()))
bbb = list(accumulate(aaa))
ccc = list(-i % k for i in range(n))
ddd = [(b + c) % k for b, c in zip(bbb, ccc)]
count = dict(Counter(ddd[:k - 1]))
ans = 0
for i in range(n):
key = (1 - aaa[i] + bbb[i] + ccc[i]) % k
if key in count:
ans += count[key]
j = i + k - 1
if j < n:
dj = ddd[j]
if dj not in count:
count[dj] = 1
else:
count[dj] += 1
di = ddd[i]
count[di] -= 1
if count[di] == 0:
count.pop(di)
print(ans)
別解法として、最初に $a_i$ から1ずつ引いておけば、累積和%K が0になる要素数を求めるだけでよく、より楽に考察を進められる。
F - Sugoroku
問題
- $0～N$ までの $N+1$ マスがあるスゴロク、0がふりだし、$N$ があがり
- $1～M$ までの目が出るサイコロで、出た目の数だけ進む
- マス $N$ へは出た目がちょうどでないとあがることができず、越えたらゲームオーバー
- また、途中のマスにもゲームオーバーマスがあり、その位置は与えられる
- ゲームオーバーにならずに0から $N$ まで行く方法の中で、最小手数のものを求めよ
- ただし、複数ある場合、出た目の並びが辞書順で最小のものを求めよ
解法
F問題という配置に騙されると、セグメント木とか持ち出してDPしそうになるが、気付けば簡単。（別にセグ木でも答えは出るが、Pythonだと時間的に厳しかった）
$N$ から、「そのマスにたどり着ける内、最小のマス目」を逆順に求めていくとよい。
M=3
i : 0 1 2 3 4 5 6 7 8 9
マス: 0 0 0 1 0 0 0 1 0 0 (1がゲームオーバーマス)
|-------| 9にたどり着ける範囲で、最小は6、その目は3
|-------| 6にたどり着ける範囲で、最小は4、その目は2
|-------| 4にたどり着ける範囲で、最小は1、その目は3
|-| 1にたどり着ける範囲で、最小は0、その目は1
→ 答えは 1 3 2 3
これが最適である証明は以下のように考える。
もし $x$ にたどり着けるマスの中で、最小は $i$ だが、それより後の $j$ に止まるのが最適だったとする。
その時、$j$ の前に止まったマス $k$ があるはずだが、$k$ を出発点として主眼に置いた場合、$k$ からは当然 $i$ にも止まれるはずで、その方が回数を減らさずに出た目の辞書順をより小さくできるので、矛盾する。
i : .... k .... i .. j .... x 例 : .... 2 .... 4 .. 5 .... 8 ...→k→j→x (..., 3, 3) ...→k→i→x (..., 2, 4)
よって、$j$ に止まるなら $i$ に止まった方がよい。
def solve(n, m, s):
curr = n
l = max(0, n - m)
r = n
ans = []
while r > 0:
for i, c in enumerate(s[l:r], start=l):
if c == '0':
dice = curr - i
ans.append(dice)
curr = i
l = max(0, i - m)
r = i
break
else:
return (-1,)
return reversed(ans)
n, m = map(int, input().split())
s = input()
print(*solve(n, m, s))
