[[AtCoder Beginner Contest 143 C～F問題メモ]]
現在位置: トップページ » アルゴリズム » contest_history » 索引 » 2019 » AtCoder Beginner Contest 143 C～F問題メモ
管理サイトマップ

−目次

AtCoder Beginner Contest 143 C～F問題メモ

AtCoder Beginner Contest 143

C - Slimes

C - Slimes

問題

  • NN 個のスライムが一列に並ぶ
  • それぞれのスライムの色は N 文字から成る文字列 S で表される
    • 1つのスライムの色は1文字で表され、i 番目のスライムの色は文字列 S の i 文字目に相当する
  • 同色のスライムが隣り合っていると、全てくっついて1つになる
  • くっついた後のスライムの個数を求めよ
  • 1≤N≤105

解法

ランレングス圧縮後の長さ。

itertools.groupbyを使えば短くかける。（覚えた知識をすぐ使いたがる）

1
2
3
4
5
from itertools import groupby
 
n = int(input())
s = input()
print(len(list(groupby(s))))

D - Triangles

D - Triangles

問題

  • N 本の棒があり、i 番目の棒の長さは Li である
  • 3本の棒を使って三角形を作ろうと思えば、3辺の長さを a,b,c として、以下を全て満たす必要がある
    • a<b+c
    • b<c+a
    • c<a+b
  • 作れる三角形は何種類あるか、求めよ
  • 同じ長さの棒が複数本ある場合もあるが、区別して数える
  • 3≤N≤2000
  • 1≤Li≤1000

解法

ソートしてにぶたん。

まず、使う3本のうち短い方の2本を全探索する。 

Li  1  1  2  3  4  4  5  6
          ^     ^

たとえば2と4を選んだ時、この2本が短い辺となるように作れるもう一本の長さは、6未満である。

なので、それより短い棒の個数を調べる。ソートした Li 配列上で二分探索する。bisect_leftを使えば「6以上となる最も短い棒のindex」が得られる。 

Li  1  1  2  3  4  4  5  6
          ^     ^
          i     j |----| k

最初に選んだ2本のindexを i,j(i<j) とした時、k−j−1 が、その間にある棒の本数となる。

これらを全ての2本の組について合計した値が答えとなる。

1
2
3
4
5
6
7
8
9
10
11
12
13
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≤2000,Li≤1000 より、クエリが最大 N(N−1)2=2×106 回くらい投げられるのに対して、クエリの種類は2つの数の和の範囲2～2000の2000通り程度しか無い。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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

E - Travel by Car

問題

  • N 個の都市、M 本の道路があり、i 本目の道路は 都市 Ai と Bi を長さ Ci で結ぶ
  • 車で都市から都市まで移動することを考える
    • 車は1単位長さ走る毎に、1リットルの燃料を消費する
    • 燃料タンクには L リットルまで入り、補給は都市でのみ、満タンになるまで行える（行わなくてもよい）
    • 出発時、燃料は満タンである
    • 途中で燃料が無くなるような移動は行えない（到着と同時に空になるのはOK）
  • クエリが Q 個与えられるので、全てに答えよ
    • i 番目のクエリは Si,Ti が与えられる
    • 都市 Si から Ti まで行くのに必要なガソリンの最小補給回数を求める
  • 2≤N≤300
  • 0≤M≤N(N−1)2
  • 1≤L,Ci≤109
  • 1≤Q≤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)logN) とされている。

今回、頂点数は少ないが辺の数は完全グラフまであり得る。さらにこれを各頂点から行うので、全体で O(N3logN) となる。

そのまま計算すると 2×108、多少の定数倍は省略されるにしても、107 くらいはありそうなので、やはり厳しい。入力行数も多いのでそれにも少し時間を取られる。

高速化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(V2) VS O((E+V)logV) なので、E=O(V2) なら確かにそう。これなら通るか。

話は変わるけど書いてあることには従いましょうという話

最近のAtCoderでは、「各行に1つの答えを出力せよ」という問題でも、空白区切りで1行に全て出力しても受け取ってくれる問題が多いが、 この問題はちゃんと言われたとおり改行しないとダメだった。

Pythonでは空白区切り1行だとansに出力を溜めて print(*ans) で済むから楽なんだよねえ。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
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

F - Distinct Numbers

問題

  • N 個の整数 A={A1,A2,...,AN} がある
  • 1≤K≤N の全ての正整数 K について、以下を求めよ
    • 互いに相異なる K 個の数を A から繰り返し取り出す時、取り出せる最大回数
  • 1≤N≤3×105

例

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種類あるので、これは最大限使うとする。（以下では説明のため具体的な Ai の値を入れているが、実際に解く際には不要） 

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個しか無いので、埋められず、不可能と分かる。

一般化すると、

  • gt=t 回以上出現する数の種類数
  • st=t 回未満出現する数の個数

を計算しておくと、gt+stt≥k なら、K=k の時に t 回の取り出しが達成可能と判定できる。

達成可能/不可能は t に対して単調性がある（どこかに唯一の可能/不可能の境界がある）ので、これを二分探索で求めればよい。

計算量は O(NlogN) となり、（Pythonでは多少枝刈りなどすれば）解ける。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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