目次
CODE FESTIVAL 2018 Final A～E
CODE FESTIVAL 2018 Final (Parallel)
オンサイト以外解説はなし？
A - 2540
問題
- $N$ 頂点 $M$ 辺のグラフ
- $i$ 番目の辺は $A_i$と$B_i$を長さ$L_i$で結ぶ
- 以下の条件を満たす頂点の組$(a,b,c)$の個数を求めよ
- $ab$間と$bc$間の両方に辺があり、2本の長さの合計は2540である
- $a$と$c$は異なり、$a<c$ である
- 自己辺や二重辺はない
解法
グラフの問題っぽいが、求める内容が限定的なので、情報の持たせ方も簡単にできる。
各頂点に、そこから伸びる辺の長さと、その個数を記録していく。具体的な頂点番号は必要ない。
辺を1本ずつ調べ、それまでに調べた辺と、今の辺で、2540になるものがあれば、数え上げる。
①--1000-, ,-1000--② 今までに調べた辺
③ ③: 1000が2本,1200が1本
④--1200-' ⑤--1000--⑥ ⑤: 1000が1本
--------------------------------------------------
①--1000-, ,-1000--② ③⑤を1540で結ぶ辺を追加
③ →③または⑤から伸びる2540-1540=1000の辺の個数＝3本
④--1200-' `-1540--⑤--1000--⑥ →答えに3を加算
この問題に限らないが、全体的に入力行数が多いので、input()よりsys.stdin.readlines()を使った方が速くてよい。
import sys
from collections import defaultdict
n, m = map(int, input().split())
ans = 0
cnt = [defaultdict(int) for _ in range(n)]
for line in sys.stdin.readlines():
a, b, l = map(int, line.split())
a -= 1
b -= 1
r = 2540 - l
ans += cnt[a][r]
ans += cnt[b][r]
cnt[a][l] += 1
cnt[b][l] += 1
print(ans)
B - Theme Color
問題
- $N$人が$M$個の候補に投票する
- 各人は独立に等確率で投票する
- 票の入り方$r_1,r_2,...,r_M$が指定される
- $r_1+r_2+...+r_M=N$
- そのような票の入り方になる確率を$p$とした時、$p>10^{-x}$を満たす最小の$x$を求めよ
例
- 3人が2候補に投票
- $r1=1, r2=2$
このような票の入り方になる確率は、0.375。よって、$10^{0}>0.375>10^{-1}$なので、最小の$x$は「1」
解法
中学か高校くらいでやったことあるような数学。
まず、票の入り方の確率を立式する。
分子（指定された投票のされ方）は、$\displaystyle \frac{N!}{r_1!r_2! ... r_M!}$、分母（全ての投票のされ方）は、$M^N$。
まとめると$\displaystyle p=\frac{N!}{r_1!r_2! ... r_M! M^N}$
これをまともに計算したらオーバーフロー一直線なので、logをとる。答えが10の冪で問われているので、log10をとる。
logをとると、かけ算は足し算に、割り算は引き算になる。
$\log_{10}{p}=\log_{10}{N!}-\log_{10}{r_1!}-\log_{10}{r_2!}- ... -\log_{10}{r_M}!-N\log_{10}{M}$
$0! ... N!$までの階乗、および$M$のlog10を事前計算しておけば答えを出せる。
答えは、ガウス記号を用いて$[\log_{10}{p}]$となる。
ただ、言語や使用する関数によっては誤差が出てしまう。
Pythonでは、log(a, base)を使うと1ケースでWAだったが、log10(a)を使うとACだった。
from math import ceil, log10
def prepare(n, m):
l = 0
res = [0, 0]
for i in range(2, n + 1):
t = log10(i)
l += t
res.append(l)
return res
n, m = map(int, input().split())
res = prepare(n, m)
ans = res[n] - log10(m) * n
for r in map(int, input().split()):
ans -= res[r]
print(ceil(-ans))
C - Telephone Charge
問題
- ある携帯会社では料金プランが$N$個ある
- プラン$i$の通話料金は、ひと月の通話時間が$A_i$分以内なら$B_i$円、超過分は1分あたり1円
- $M$人の人がいて、$i$番目の人のひと月の通話時間は$T_i$
- それぞれの人について、最安プランを選択した時の通話料金を求めよ
- あるプランが、他のプランの上位互換となることはない
- つまり、ひと月の通話料金$T=A_i$の時、最安プランは$i$で、他より1円以上安い
解法
超過分はどのプランも一律1円であることと、最後の条件が重要で、この2つのおかげで調べる範囲を限定できる。
通話時間が$T$なら、$T$に近い$A_i$を持つ$i$が、最適なプランとなる。条件を考えると、$A_i=A_j$となる$i,j$は存在しない。
料| 金| / / / |A-------/------/---' |B------/------' |C-----' 時間 +-------|-------|-------- Cが最適 Bが最適 Aが最適
$A_i$をソートして$T$を二分探索し、$T=A_i$ならそのプラン。$A_i<T<A_j$なら$i,j$のいずれかが最適プランとなる。
import bisect
import sys
n = int(input())
lines = sys.stdin.readlines()
plans = [tuple(map(int, line.split())) for line in lines[:n]]
plans.sort()
min_t = plans[0][0]
max_t = plans[-1][0]
m = int(lines[n])
buf = []
for line in lines[n + 1:]:
t = int(line)
if t <= min_t:
buf.append(plans[0][1])
continue
if t >= max_t:
buf.append(plans[-1][1] + t - max_t)
continue
i = bisect.bisect(plans, (t,))
ans = min(plans[i - 1][1] + t - plans[i - 1][0], plans[i][1])
buf.append(ans)
print('\n'.join(map(str, buf)))
D - Three Letters
問題
- $N$個の3文字以上の文字列がある
- 英大小文字52種類の文字からなる
- 各文字列の部分文字列を考える（連続で無くてもよい）
- 最も多くの文字列の部分文字列となる、長さ3の部分文字列を求めよ
- 個数が同じ場合は、ASCII文字コードの辞書順で最初に来るものを求めよ
- $N$個の文字列の文字数総計$\le 90000$
例
aKIHaBaRa => KIB, aKa, aaa, ... aKIBa => KIB, aKa, IBa, ... aSaKUSa => SKU, aKa, aaa, ... SHINKIBA => KIB, SNK, IIA, ...
'aKa'と'KIB'が3個でトップ。ASCII文字コードでは大文字の方が先に来るので、KIBが答え。
解法
cnt[i][j][k]の配列を用意し、文字列$S$に$i,j,k$の部分文字列が存在したら、カウントしていくことを考える。（$i,j,k$は文字コードで考える）
さて、しかし存在するかどうかを愚直に求めると「$(i,j)$が出てきたかどうか」を保存し、それ以降の文字$k$ごとに調べていくために$52^2 \times |S|$くらいのループが必要になり、厳しい。
ここでは、「$(i,j)$が最初に出てきた位置」と「$k$が最後に出てきた位置」を分けて保存する。文字列$S$の全ての位置を保存し終えたら、出現した各$(i,j),k$について位置を比較し、$(i,j)$の方が前なら部分文字列$i,j,k$が存在することになる。
これでも、Pythonだと厳しい。PyPyで何とか。とにかく配列参照が遅いので、array[i][j][k]を$i,j,k$のループで回す時に、逐一array[i]、array[i][j]を変数に保存して、参照回数を減らすなどで、TLEを回避する。
もっと良い方法はあるかも？
import sys
from string import ascii_letters
cnt = [[[0] * 123 for _ in range(123)] for _ in range(123)]
first_appears2 = [[-1] * 123 for _ in range(123)] # switched
last_appears1 = [-1] * 123
appeared1 = set()
n = int(input())
for s in sys.stdin.readlines():
appeared2 = []
for i, c in enumerate(map(ord, s.strip())):
fac = first_appears2[c]
for a in appeared1:
if fac[a] == -1:
fac[a] = i
appeared2.append((a, c))
last_appears1[c] = i
appeared1.add(c)
for a, b in appeared2:
cnt_ab = cnt[a][b]
fab = first_appears2[b]
i = fab[a]
for c in appeared1:
if i < last_appears1[c]:
cnt_ab[c] += 1
fab[a] = -1
appeared1.clear()
ans = None
max_cnt = 0
ascii_orders = sorted(map(ord, ascii_letters))
for i in ascii_orders:
cnt_i = cnt[i]
for j in ascii_orders:
cnt_ij = cnt_i[j]
for k in ascii_orders:
cnt_ijk = cnt_ij[k]
if cnt_ijk > max_cnt:
ans = [i, j, k]
max_cnt = cnt_ijk
print(''.join(map(chr, ans)))
E - Tough Journey
問題
- 旅人が都市$0$にいて、$1,2,...$を順に経由して都市$N$まで行く
- 旅人は空のペットボトルを$K$本持っている
- 都市$i$（$0 \le i \lt N$）では以下の行動を取れる
- $A_i$円でペットボトル1本を水で満タンにする（お金さえ払えば何本でも可）
- ペットボトル1本を飲み干し、次の都市$i+1$へ移動する
- 最安で移動した時の金額を求めよ
解法
最適な行動は決まっている。
- 最も近い、今の都市よりも安く水を買える都市に行く。今の都市で水は、そこに到達できるぎりぎりの量だけ買う。
- $K$以内に今よりも安く水を買える都市が無い場合は、今の都市で$K$本全て満たし、行ける範囲で最も安い都市に行く。
ここで必要なのは、「$i+1～i+K$で一番安い都市」を手早く求められるデータ構造となる。
これは、セグメント木で持ったり、ソートして事前計算しておくことで可能となる。
あとは上記の行動をきちんと実装すればよい。
from heapq import heappop, heappush, heapify
from itertools import islice
def solve(n, k, aaa):
if n == 1:
return aaa[0]
min_array = []
q = [(a, -i) for i, a in islice(enumerate(aaa[:k + 1]), 1, None)]
heapify(q)
min_array.append(q[0])
for i, a in enumerate(aaa[k + 1:]):
j = i + k + 1
heappush(q, (a, -j))
while -q[0][1] <= i + 1:
heappop(q)
min_array.append(q[0])
min_array.extend([min_array[-1]] * k)
last_i = -min_array[-1][1]
ans = 0
remain = 0
i = 0
while i < last_i:
a = aaa[i]
nxa, nxi = min_array[i]
nxi = -nxi
need = nxi - i
if a <= nxa:
ans += a * (k - remain)
remain = k - need
i = nxi
else:
for j in range(i + 1, nxi + 1):
if a > aaa[j]:
need = j - i
if need <= remain:
remain -= need
else:
ans += a * (need - remain)
remain = 0
i = j
break
need = n - i
ans += aaa[i] * (need - remain)
return ans
n, k = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(n, k, aaa))
もしくは、以下のような解法もあるようだ。
- $0～N-1$の全ての都市で水を飲む必要がある
- その水は、$i-K～i-1$のどこかで購入したものである必要がある
- 最も安い都市で水を買ったことにして、それを合計する
F - Dinner Planning
問題
例
解法
G - Chicks and Cages
問題
- $N$羽のひよこを$M$個の箱に閉じ込める
- $i$番目のひよこの大きさは$A_i$
- 各ひよこは、自分を含めて同じ箱に入っているひよこの大きさの総和のストレスを受ける
- ひよこが受けるストレスの総和を最小化するとき、その総和を求めよ
- $1 \le M \le N \le 2000$
例
Ai 5 10 8 11 6
箱 └──┘ └────┘
↓ ↓
2羽が各15のｽﾄﾚｽ 3羽が各25のｽﾄﾚｽ
15 x 2 + 25 x 3 = 105
（※最適では無い）
解法
1羽のひよこの大きさは、同じ箱に入っているひよこの数だけ加算される。よってストレスの総和は「$A_i \times$(同じ箱のひよこの数)」の和で計算できる。
Ai 5 10 8 11 6
同じ箱のひよこ 2 2 3 3 3
10 +20 +24 +33 +18 = 105
そうすると、大きなひよこが、小さなひよこより、ひよこが沢山入っている箱に入っているのは非効率。交換すれば常に総和を減少できる。
v-----------v
Ai 11 10 8 5 6
同じ箱のひよこ 2 2 3 3 3
22 +20 +24 +15 +18 = 99
よって、ひよこの大きさでソートし、小さい方から箱に入れていけばいい。その際、例えば小さい方から1つの箱に6羽入れたら、次の箱には7羽以上入れないようにする。
これを全通り試すのは一見計算量がかかりそうだが、単調減少の制約があるループは、調和級数の和 $\displaystyle \sum^{n}_{k=1}{\frac{1}{k}}=\log{(n+1)}$ より$N$が$\log{N}$になり、意外と少なくなるらしい。
from itertools import accumulate
n, m = map(int, input().split())
aaa = sorted(map(int, input().split()))
acc = [0] + list(accumulate(aaa))
cache = [[0] * (m + 1) for _ in range(n + 1)]
def cal(chick, cage, k):
if cache[chick][cage] > 0:
return cache[chick][cage]
if cage == 1:
ans = (acc[-1] - acc[-chick - 1]) * chick
cache[chick][cage] = ans
return ans
upper = min(k, chick - (cage - 1))
lower = (chick - 1) // cage + 1
ans = float('inf')
for i in range(lower, upper + 1):
cur_min = (acc[-chick + i - 1] - acc[-chick - 1]) * i
cur_min += cal(chick - i, cage - 1, i)
ans = min(ans, cur_min)
cache[chick][cage] = ans
return ans
print(cal(n, m, n))
H - Pothunter
問題
例
解法
I - Homework
問題
例
解法
J - Complicated Operations
問題
例
解法
