−目次

AtCoder Beginner Contest 143 C～F問題メモ
- C - Slimes
  - 問題
  - 解法
- D - Triangles
  - 問題
  - 解法
- E - Travel by Car
  - 問題
  - 解法
- F - Distinct Numbers

AtCoder Beginner Contest 143 C～F問題メモ

AtCoder Beginner Contest 143

AtCoder BeginnerContest 143 - YouTube

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に悪影響を及ぼし続ける。

ダイクストラ法が分からなかった君のために - kuuso1のブログ
- 上記リンクの図を用いた説明で、黄色の丸を「確定済み」、水色の丸を「暫定距離判明済み」と称する
- 上の方の水色の丸が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氏）
- 提出 #8064841 - AtCoder Beginner Contest 143

Naive Dijkstra

Dijkstraに名を残すエドガー・ダイクストラさんが考案したままのアルゴリズム。 heapを使う方法は、後から別の人が改善したもの。

単一始点最短路(Single-Source Shortest Path) - kanetaiの二次記憶装置

これを見ると、密グラフでは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個しか無いので、埋められず、不可能と分かる。

一般化すると、

$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:])

            

        
      