目次
AtCoder Beginner Contest 143 C～F問題メモ
C - Slimes
問題
- $N$ 個のスライムが一列に並ぶ
- それぞれのスライムの色は $N$ 文字から成る文字列 $S$ で表される
- 1つのスライムの色は1文字で表され、$i$ 番目のスライムの色は文字列 $S$ の $i$ 文字目に相当する
- 同色のスライムが隣り合っていると、全てくっついて1つになる
- くっついた後のスライムの個数を求めよ
- $1 \le N \le 10^5$
解法
ランレングス圧縮後の長さ。
itertools.groupbyを使えば短くかける。（覚えた知識をすぐ使いたがる）
from itertools import groupby n = int(input()) s = input() print(len(list(groupby(s))))
D - Triangles
問題
- $N$ 本の棒があり、$i$ 番目の棒の長さは $L_i$ である
- 3本の棒を使って三角形を作ろうと思えば、3辺の長さを $a,b,c$ として、以下を全て満たす必要がある
- $a \lt b+c$
- $b \lt c+a$
- $c \lt a+b$
- 作れる三角形は何種類あるか、求めよ
- 同じ長さの棒が複数本ある場合もあるが、区別して数える
- $3 \le N \le 2000$
- $1 \le L_i \le 1000$
解法
ソートしてにぶたん。
まず、使う3本のうち短い方の2本を全探索する。
Li 1 1 2 3 4 4 5 6
^ ^
たとえば2と4を選んだ時、この2本が短い辺となるように作れるもう一本の長さは、6未満である。
なので、それより短い棒の個数を調べる。ソートした $L_i$ 配列上で二分探索する。bisect_leftを使えば「6以上となる最も短い棒のindex」が得られる。
Li 1 1 2 3 4 4 5 6
^ ^
i j |----| k
最初に選んだ2本のindexを $i,j(i \lt j)$ とした時、$k - j - 1$ が、その間にある棒の本数となる。
これらを全ての2本の組について合計した値が答えとなる。
from bisect import bisect_left
n = int(input())
lll = list(map(int, input().split()))
lll.sort()
ans = 0
for i in range(n - 2):
li = lll[i]
for j in range(i + 1, n - 1):
k = bisect_left(lll, li + lll[j])
ans += k - j - 1
print(ans)
なお、Pythonでは、サーバでの実行速度のばらつきによっては、微妙にTLEとなることがある。
素直にPyPyで提出すればよいが、Pythonで通したい場合、結構bisect_leftは同じクエリが何回も投げられることになるため、キャッシュすれば余裕を持って通るようになる。
$N \le 2000, L_i \le 1000$ より、クエリが最大 $\frac{N(N-1)}{2} = 2 \times 10^6$ 回くらい投げられるのに対して、クエリの種類は2つの数の和の範囲2～2000の2000通り程度しか無い。
from bisect import bisect_left
n = int(input())
lll = list(map(int, input().split()))
lll.sort()
ans = 0
def get_bisect_left():
cache = {}
def _f(x):
if x in cache:
return cache[x]
cache[x] = bisect_left(lll, x)
return cache[x]
return _f
bisect_left_cache = get_bisect_left()
for i in range(n - 2):
li = lll[i]
for j in range(i + 1, n - 1):
k = bisect_left_cache(li + lll[j])
ans += k - j - 1
print(ans)
E - Travel by Car
問題
- $N$ 個の都市、$M$ 本の道路があり、$i$ 本目の道路は 都市 $A_i$ と $B_i$ を長さ $C_i$ で結ぶ
- 車で都市から都市まで移動することを考える
- 車は1単位長さ走る毎に、1リットルの燃料を消費する
- 燃料タンクには $L$ リットルまで入り、補給は都市でのみ、満タンになるまで行える（行わなくてもよい）
- 出発時、燃料は満タンである
- 途中で燃料が無くなるような移動は行えない（到着と同時に空になるのはOK）
- クエリが $Q$ 個与えられるので、全てに答えよ
- $i$ 番目のクエリは $S_i,T_i$ が与えられる
- 都市 $S_i$ から $T_i$ まで行くのに必要なガソリンの最小補給回数を求める
- $2 \le N \le 300$
- $0 \le M \le \frac{N(N-1)}{2}$
- $1 \le L,C_i \le 10^9$
- $1 \le Q \le N(N-1)$
解法
各頂点から（コストの計算を拡張した）Dijkstra……で通ると思ったら、PyPyではTLEで通らなかった（適切な実装すれば通る?）。 Floyd-Warshallは、数字の埋まり方をイマイチちゃんと理解してなくて、同様の拡張を行おうとしたらWAとなった。
想定解はもっと単純で、2回のFloyd-Warshallを行えばよい。これは気付くべきですね……
Floyd-Warshall解法が鮮やかなのは感嘆するとして、Dijkstraをもう少し考えておさらいする。
Floyd-WarshallでWAとなる理由
ここでは、1回で一気に答えを求めようとするFloyd-Warshallを指す。
Dijkstraによる解法では、コストを2つの変数（補給量、最後に満タンにしてからの使用量）で持てばよい。 ある都市に到着したとき、補給量は少ない方が、同じならタンクに残っている燃料は多い方が常によいので、これを最小化すればよい。
しかし、このコストの更新が可能なのは、Dijkstraが常にリンクで接した次の頂点にのみ探索を広げるので、その都度、補給するかしないか決められるからである。
対して、Floyd-Warshallはパス同士を繋げて最小値を更新するため、コストには結合法則（でいいのかな）が成り立っていないといけない。
Dijkstra
s -- ○ -- ... -- ● -- ◎
次のノードへの更新で補給するかしないか決められる
Floyd-Warshall
s -- ○ -- ... -- ● -- ○ -- ... -- ◎
|-----------------||------------------|
sで満タンにして ●で満タンにして
●までの最小コスト ◎までの最小コスト
→足し合わせるだけでは●で残っている燃料を活用することができない
Dijkstraの計算量
二分ヒープによるDijkstraの計算量は、$O((N+M)\log{N})$ とされている。
今回、頂点数は少ないが辺の数は完全グラフまであり得る。さらにこれを各頂点から行うので、全体で $O(N^3 \log{N})$ となる。
そのまま計算すると $2 \times 10^8$、多少の定数倍は省略されるにしても、$10^7$ くらいはありそうなので、やはり厳しい。入力行数も多いのでそれにも少し時間を取られる。
高速化1 heapに入れるノードの枝刈り
人によっては、通常のDijkstraの時点で常にやっているかもしれないが。
特に今回のような密なグラフの場合、既に確定済みの頂点の他のパスがheapに残り続け、全体のpop, pushに悪影響を及ぼし続ける。
-
- 上記リンクの図を用いた説明で、黄色の丸を「確定済み」、水色の丸を「暫定距離判明済み」と称する
- 上の方の水色の丸がheapに残り続けることで、全体に悪影響を及ぼす
よって、頂点 $v$ から $u$ に探索を広げる際、heapに入れなくてもよい条件でなるべく弾きたい。
既に確定済み
$u$ が、既に確定済みなら、heapに追加しない。これは特に追加のデータも不要で、単純だが一定の効果がある。
既に他の経路でより短い距離で行けることが判明済み
追加のデータが必要になるが、より強力。密グラフの場合、こちらがよい。
「各頂点につき、現在判明している中で最短の暫定距離」を保持する。
$v$ を経由する新しい $u$ への距離が、それより長ければ、追加する必要は無い。
高速化2 終了条件
始点から全ての頂点までの距離が確定した後も、水色の丸（高速化1 参照）はheapに残り続ける。
通常は、heapが空になるまでpopし続ける。 popしても飛ばされるだけなのだが、特にグラフが密だと、それだけでも結構時間はかかる。
確定すべき頂点数が事前にわかっていれば、その数だけ確定したらそこで終了して良いとわかる。
グラフが連結ならその頂点数は $N$ なのだが、 今回の場合、グラフは連結とは限らないので、Union-Find等で連結頂点数を計算しておき、確定すべき頂点数とする。
（ちょっと牛刀割鶏っぽい気がしないでも無い）
ただこれ、1点だけ、どの頂点からもめっちゃ離れた頂点を用意するなどで、あまり意味をなさなくなってしまう。 結局その1点が取り出されるまで終了できず、それまでにheapのほとんども取り出される。
ランダムケースでは効果はあるが、狙い撃ちの意地悪ケースには弱い。
高速化3 コストのint化
可読性の悪くなる、あまりやりたくない手法だが、効果はそれなりにある。
コストを表現するのに複数の変数（補給回数、最後の補給からの使用量）が必要な今回の問題では、tupleで持つのが一般的である。 だが、tupleは大小比較に少し時間がかかる（intと比べて）。
それぞれの変数の取り得る最大数を制約より確認し、 被らない固定の桁数だけbitshiftして1つのint型として持たせると、比較が高速化される。 そのための演算コストはかかるが、heap内で繰り返される比較コストと比べると、十分償却される。
上記の3つをやって、コンテスト後に追加された1ケース以外は通った。（PyPy 1079ms）
最後の1ケースはDijkstra解法を落とすため？の意地悪ケースのようで、C++でも1000ms以上かかっているものが散見される。 でもPyPyでDijkstraで通している人もいるので、後で確認する。
- C++ でboostのfibonacci_heapを使うことで最後のケースでも144msで通っているケース（kroton氏）
Naive Dijkstra
Dijkstraに名を残すエドガー・ダイクストラさんが考案したままのアルゴリズム。 heapを使う方法は、後から別の人が改善したもの。
これを見ると、密グラフではNaiveの方がいいらしい。$O(V^2)$ VS $O((E+V)\log{V})$ なので、$E=O(V^2)$ なら確かにそう。これなら通るか。
話は変わるけど書いてあることには従いましょうという話
最近のAtCoderでは、「各行に1つの答えを出力せよ」という問題でも、空白区切りで1行に全て出力しても受け取ってくれる問題が多いが、 この問題はちゃんと言われたとおり改行しないとダメだった。
Pythonでは空白区切り1行だとansに出力を溜めて print(*ans) で済むから楽なんだよねえ。
import sys
from heapq import heappop, heappush
class UnionFind:
def __init__(self, n):
self.table = [-1] * n
def _root(self, x):
if self.table[x] < 0:
return x
else:
self.table[x] = self._root(self.table[x])
return self.table[x]
def find(self, x, y):
return self._root(x) == self._root(y)
def union(self, x, y):
r1 = self._root(x)
r2 = self._root(y)
if r1 == r2:
return
d1 = self.table[r1]
d2 = self.table[r2]
if d1 <= d2:
self.table[r2] = r1
self.table[r1] += d2
else:
self.table[r1] = r2
self.table[r2] += d1
def united_count(self, x):
return -self.table[self._root(x)]
def dijkstra(links, l, uft):
dists = []
F9 = (1 << 9) - 1
F30 = (1 << 30) - 1
INF = 10 ** 18
for s in range(n):
q = [s]
fixed = [-1] * n
upper = [INF] * n
fixed_count = 0
limit = uft.united_count(s)
while q:
item = heappop(q)
v = item & F9
if fixed[v] != -1:
continue
count = item >> 39
used = (item >> 9) & F30
fixed[v] = count
fixed_count += 1
if fixed_count >= limit:
break
for u, c in links[v]:
if l - used < c:
new_item = ((count + 1) << 39) | (c << 9) | u
else:
new_item = (count << 39) | ((used + c) << 9) | u
if new_item >= upper[u]:
continue
upper[u] = new_item
heappush(q, new_item)
dists.append(fixed)
return dists
n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
uft = UnionFind(n)
for line in lines[:m]:
a, b, c = map(int, line.split())
a -= 1
b -= 1
if l < c:
continue
links[a].add((b, c))
links[b].add((a, c))
uft.union(a, b)
dists = dijkstra(links, l, uft)
buf = []
for line in lines[m + 1:]:
s, t = map(int, line.split())
buf.append(dists[s - 1][t - 1])
print('\n'.join(map(str, buf)))
F - Distinct Numbers
問題
- $N$ 個の整数 $A=\{A_1,A_2,...,A_N\}$ がある
- $1 \le K \le N$ の全ての正整数 $K$ について、以下を求めよ
- 互いに相異なる $K$ 個の数を $A$ から繰り返し取り出す時、取り出せる最大回数
- $1 \le N \le 3 \times 10^5$
例
N = 16 A = 1 2 3 4 4 4 4 4 5 5 6 6 7 7 7 7 K = 4 に対して、以下のように3回取り出せ、これが最大となる 1 4 5 7 2 4 6 7 4 5 6 7
解法
$K$ と同時に、「取り出せる回数」を仮定すると、方針が見えてくる。
まず事前準備として、具体的な数字は必要なく、それぞれが何回出現したかのみが重要なので、出現回数の配列にする。
A = 1 2 3 4 4 4 4 4 5 5 6 6 7 7 7 7 B = 1 1 1 ~~~~5~~~~ ~2~ ~2~ ~~~4~~~ ↓ソート B = 1 1 1 2 2 4 5
ここで、$K=4$、取り出せる回数をたとえば $t=4$ として、達成可能か考える。
$t$ 回以上出現する数は、それぞれの組に1個ずつ入れたらそれ以上は入れられない。
4回以上出現する数は2種類あるので、これは最大限使うとする。（以下では説明のため具体的な $A_i$ の値を入れているが、実際に解く際には不要）
4 7 ○ ○ 4 7 ○ ○ 4 7 ○ ○ 4 7 ○ ○
残り埋めるべき○は8個。これを、4回未満出現する数で埋められれば達成可能、できなければ不可能である。 縦に順に埋めていけば、4回未満出現する数が同じ組（横列）に被ることは無いので、全て使える。
4 7 1 5 4 7 2 6 4 7 3 6 4 7 5 ○
今回の場合、4回未満出現する数は7個しか無いので、埋められず、不可能と分かる。
一般化すると、
- $g_t = t$ 回以上出現する数の種類数
- $s_t = t$ 回未満出現する数の個数
を計算しておくと、$g_t + \frac{s_t}{t} \ge k$ なら、$K=k$ の時に $t$ 回の取り出しが達成可能と判定できる。
達成可能/不可能は $t$ に対して単調性がある（どこかに唯一の可能/不可能の境界がある）ので、これを二分探索で求めればよい。
計算量は $O(N \log{N})$ となり、（Pythonでは多少枝刈りなどすれば）解ける。
from collections import Counter
from itertools import groupby
def bin_search(k, greater_count, smaller_sum):
l = 0
r = n + 1
while l < r - 1:
m = (l + r) // 2
gc = greater_count[m]
ss = smaller_sum[m]
if gc + ss // m >= k:
l = m
else:
r = m
return l
n = int(input())
aaa = list(map(int, input().split()))
cnt = sorted(Counter(aaa).values())
# Precompute
greater_count = [0] * (n + 2) # Number of types of Ai same or greater than i
smaller_sum = [n] * (n + 2) # Number of Ai smaller than i
remain = greater_count[1] = len(cnt)
total = smaller_sum[1] = 0
cnt_grp = [(c, len(list(itr))) for c, itr in groupby(cnt)]
for (c, l), (c2, _) in zip(cnt_grp, cnt_grp[1:]):
remain -= l
total += c * l
for i in range(c + 1, c2 + 1):
greater_count[i] = remain
smaller_sum[i] = total
# Query
buf = []
for k in range(1, len(cnt) + 1):
buf.append(bin_search(k, greater_count, smaller_sum))
buf.extend([0] * (n - len(cnt)))
print(*buf)
もう少し速い解法
それぞれの $t$ に対して、その回数の取り出しを行える最大の $K$ の値というのは既述の方法で求められる。
事前計算の後、$t=1～N$ に対して最大の $K$ を求める。
t 1 2 3 4 5 6 7 8 9 ... 16 k 7 5 4 3 3 2 2 2 1 ... 1
indexと値を逆転させる。重複する分に関しては、$t$ が最大のものを取る。
k 1 2 3 4 5 6 7 8 9 ... 16 t 16 8 5 3 2 0 1 0 0 ... 0
埋まっていない箇所に関しては、後ろから累積maxを取る。これで答えが求められ、計算量は $O(N)$ となる。
k 1 2 3 4 5 6 7 8 9 ... 16 t 16 8 5 3 2 1 1 0 0 ... 0
from collections import Counter
from itertools import groupby, accumulate
n = int(input())
aaa = list(map(int, input().split()))
cnt = sorted(Counter(aaa).values())
remain = len(cnt)
total = 0
kkk = [0] * (n + 1)
p = 1
for c, itr in groupby(cnt):
l = len(list(itr))
for i in range(p, c + 1):
kkk[remain + total // i] = i
remain -= l
total += c * l
p = c + 1
for i in range(p, n + 1):
kkk[remain + total // i] = i
kkk.reverse()
kkk = list(accumulate(kkk, func=max))
kkk.reverse()
print(*kkk[1:])
