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

よって、頂点 $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で通している人もいるので、後で確認する。

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

programming_algorithm/contest_history/atcoder/2019/1019_abc143.txt · 最終更新: 2019/10/23 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0