AtCoder Beginner Contest 204 D,E,F問題メモ

AtCoder Beginner Contest 204

████←#ABC204

D - Cooking

• $N$ 品の料理を作る
• 料理 $i$ を作るには1つのオーブンを連続して $T_i$ 分間占有する
• オーブンが2つ使えるとき、$N$ 品全てを作るのにかかる最短時間を求めよ
• $1 \le N \le 100$
• $1 \le T_i \le 10^3$

全ての料理を作る時間の総計は $10^5$ 程度なので、以下のナップサックDPが作れる。

• $DP[i][j]=$ 料理 $1～i$ からいくつか選んで、1つのオーブンで作るのにちょうど $j$ 分間かかる組み合わせを作れるか？

全料理の総計 $\sum{T_i}$ の半分以上で、半分になるべく近い、可能な所要時間を求めればよい。

このように、可能/不可能の0/1を保持するナップサックDPは、 Pythonなど多倍長演算が使える言語なら、整数のbitで計算すると実装も楽だし高速に動作する。

Python3

n = int(input())
ttt = list(map(int, input().split()))
can = 1
for t in ttt:
    can |= can << t

m = 1 << (can.bit_length() // 2)
while can & m == 0:
    m <<= 1

print(m.bit_length() - 1)

E - Rush Hour 2

2が作られたのなら映画と同じく3までいきたいね。

• $N$ 個の都市と $M$ 本の道路に見立てたグラフが与えられる
• 各道路は時刻0に混雑のピークを迎え、だんだんと解消していく
  • 具体的には、道路 $i$ の所要時間は $C_i,D_i$ によって以下のように決められる
  • 時刻 $t$ に通行を開始した場合、$C_i + \left \lfloor \dfrac{D_i}{t+1} \right \rfloor$
• 各都市では好きな整数時間、待機できる
• 都市1に時刻 $0$ にいる時、都市 $N$ に到達できるか判定し、可能なら最短時間を求めよ
• $2 \le N \le 10^5$
• $0 \le M \le 10^5$
• $0 \le C_i,D_i \le 10^9$
• グラフは自己辺、多重辺がありえるし、連結とも限らない

辺のコストが時間で変化する最短経路探索は、FIFO制約が満たされているかを確認する。
つまり、都市 $i$ に最短 $t$ で到達可能としてそこから都市 $j$ に移動するにあたり、 「都市 $i$ に、$t$ より後に到達した方が、都市 $j$ に早く着ける、ということが絶対にない」状態でないと、 Dijkstraなどの効率的なアルゴリズムは使えない。

今回の場合、すぐに出発してしまうとそういうことがあり得るが、 各都市では好きなだけ待てるので、「待つ部分も含めて辺のコストとする」ことで 上手くFIFO制約を満たせるようにグラフを作り替えられる。

頂点を $(都市, 到達時刻)$ の組でもって、各都市から「すぐ出発する」「1分待つ」の2つに遷移するようなDijkstraでも 正しい答えは求まるには求まるが、頂点数が多くなりすぎてこの方法ではTLEしてしまう。

もう少し高速に、最適な待機時間を求める必要がある。

都市 $i$ に時刻 $t$ に着いたとき、何分待てば良いか？を考える。（説明上、時刻1単位を[分]とする）

待機時間を $a$ として、$\left \lfloor \dfrac{D_i}{t+a} \right \rfloor \gt \left \lfloor \dfrac{D_i}{t+a+1} \right \rfloor$ であり続ける限り、 つまり1分待つと所要時間が1分以上縮まる限り、待った方が良い。

しかし、どこかの $a$ を境に、それから1分追加で待っても所要時間が変わらなくなりはじめるポイントがある。

そして一度そのような時間になったら、その後は1分待っても床関数 $\lfloor \ \rfloor$ の部分はたかだか1分しか短くならず、待ち時間を含めると得することはあり得なくなる。
そうなったら即座に出発した方がよい。

その境目は、およそ $\sqrt{D_i}$ の近傍となる。（Editorialによると、$\lfloor \sqrt{D_i} \rfloor - 1$ がちょうどいいらしい）

■ t と 所要時間の可変部分 は、およそ反比例の関係
D = 24
     →所要時間の可変部分 = D/(t+1)
↓t   1                      24
通 0  oooooooooooooooooooooooo
行 1  oooooooooooo
開 2  oooooooo
始 3  oooooo
時 4  oooo
間 5  oooo
   6  ooo
   7  ooo
   8  oo
   9  oo
   :

到達時刻 $t$ が $\lfloor \sqrt{D_i} \rfloor - 1$ より前ならそこまで待ち、後なら即座に出発すればよい。

最適な待ち時間を求めるにあたり $\sqrt{D_i}$ 近くが良いという性質がわからなくても、 待ち時間を含めた所要時間 $\left \lfloor \dfrac{D}{t+1} \right \rfloor$ は（広義）下に凸の形状をしているので三分探索でも求めることができる。

一般に三分探索は、隣り合う評価値が同じ値になり得る場合、どちらに答えがあるか判断できないので使えない。

• E869120@公開アカウントさんはTwitterを使っています 「E で三分探索を実装すると WA になる理由です。 https://t.co/l0piDaFBps」 / Twitter

しかし今回の場合、最適な待機時間は床関数を外して $C_i+\dfrac{D_i}{t+1}$ で考えた場合と変わらないし、 これなら同じ値にならないので、これで評価すると求めることができる。

Python3

import sys
from heapq import heappop, heappush


def get_waiting_time(t, d):
    l = 0
    r = 1 << 31
    while l + 1 < r:
        m1 = (l + r) // 2
        m2 = m1 + 1
        cost1 = m1 + (d / (t + m1 + 1))
        cost2 = m2 + (d / (t + m2 + 1))
        if cost1 <= cost2:
            if r == m2:
                r = m2 - 1
            else:
                r = m2
        else:
            l = m2
    true_cost = 1 << 31
    for i in range(max(0, l - 1), r + 2):
        true_cost = min(true_cost, i + (d // (t + i + 1)))
    return true_cost


def dijkstra(links, s, g):
    q = [(0, s)]
    INF = 1 << 60
    distances = [INF] * n
    distances[s] = 0
    while q:
        cost, v = heappop(q)
        if distances[v] < cost:
            continue
        if v == g:
            return cost
        for u, c, d in links[v]:
            new_cost = cost + c + get_waiting_time(cost, d)
            if distances[u] <= new_cost:
                continue
            distances[u] = new_cost
            heappush(q, (new_cost, u))
    return -1


input = sys.stdin.buffer.readline
n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    a, b, c, d = map(int, input().split())
    if a == b:
        continue
    a -= 1
    b -= 1
    links[a].add((b, c, d))
    links[b].add((a, c, d))
print(dijkstra(links, 0, n - 1))

F - Hanjo 2

• $H \times W$ のグリッドに、$1 \times 2$ の畳と、$1 \times 1$ の半畳を敷き詰める
• 敷き詰め方の総数を $\mod{998244353}$ で求めよ
• $1 \le H \le 6$
• $1 \le W \le 10^{12}$

なんかPASTで出そうな実装重めな典型問題という印象。

ある列の敷き詰め方は、「1列前にどんな敷き詰め方をしたか」だけで決定できる。（2列以上前の状態は関係ない）

その情報は $2^H$ 通りのbitフラグで持つことができ、$H$ が小さいのでこれは高々 $64$ 通りとなる。

$i$ 列目の状態がたとえば 101110 のとき、次の列の敷き詰め方は、以下のようになる。

• '0' の行には、全畳を横にして敷き詰める
• '1' の行は好きに置いたり置かなかったりできる

              (一例)
  i-1 i        i i+1
0  ■□        ＜＞  1       ■: 何でも良いので畳が敷かれたマス(=1)
1  ■■        ■＾  1       □: 畳が敷かれていないマス(=0)
1  ■■   →   ■ｖ  1       ＜＞: 全畳を横に配置
1  ■■        ■◇  1       ＾: 全畳を縦に配置
0  ■□        ＜＞  1       ｖ
1  ■■        ■□  0       ◇: 半畳を配置

'0'が連続していたらそこに縦にも敷けるのだが、 そうすると状態を重複して数えてしまうため、あくまで'0'は「必ず全畳を横に敷く行」と決めると上手くいく。

これを、64通りの各敷き詰め方につき、どれからどれへ遷移できるか、事前に求めておく。

• $Table[s][t]=i-1$ 列目の状態 $s$ から、$i$ 列目の状態が $t$ となるような敷き詰め方の個数

例えば上記の例では、'101110' の状態から '011111' の状態へは、 図で示された一例に加えて「縦に敷いた全畳 と 半畳 を入れ替えたもの」「半畳だけを3つ敷いたもの」があり得るため、$Table[101110][011111]=3$ となる。

答えはこの遷移を $W$ 回繰り返したものなのだが、$W$ は非常に大きいため、そのままやるとTLE。

遷移が毎回同じことを生かし、行列累乗で計算する。

$2^H \times 2^H$ の行列積の計算には1回 $(2^H)^3$ かかる。
行列積は約 $\log_2{W}$ 回求めればよいので、全体で $O(8^H \log{W})$ となる。

制約の最大値を代入して、約 $10^7$ となり、間に合うことがわかる。

事前計算Tableの作り方は、まぁいろいろな構築方法があると思うが、再帰関数などでかぶり無く数え上げるのがわかりやすいかと思う。

「前の行が $s$ で、今の行を $i-1$ 行目まで決めていて、決まっている行の状態が $t'$ のときの処理をする関数」を $f(s,t',i)$ とすると、

• $i=H$ のとき、$s$ から生成できる1つの状態 $t$ が確定したので $Table[s][t]$ に1加算してreturn
• $s[i]=0$ （$s$ の $i$ bit目が0）のとき、全畳を横に置くので $t'$ の $i$ bit目は1確定、$t'$ を更新して $i$ を1つ進めて次へ（$f(s,t'|(1<<i),i+1)$ へ）
• $s[i]=1$ なら、「置かない（次の列とまたがって全畳を横に置く）」「半畳を置く」「（$s[i+1]=1$ の場合のみ）全畳を縦に置く」の選択肢がとれるので、それぞれ適切に $t'$ と $i$ を更新して次へ

みたいなことをすると求まる。

Python3

import os
import sys

import numpy as np

MOD = 998244353


def precalc(table, prestate, curstate, i, h):
    if i == h:
        table[prestate, curstate] += 1
        table[prestate, curstate] %= MOD
        return

    if prestate & (1 << i) == 0:
        precalc(table, prestate, curstate | (1 << i), i + 1, h)
        return

    if i == h - 1:
        precalc(table, prestate, curstate, i + 1, h)
        precalc(table, prestate, curstate | (1 << i), i + 1, h)
        return

    if prestate & (1 << (i + 1)) == 0:
        precalc(table, prestate, curstate, i + 1, h)
        precalc(table, prestate, curstate | (1 << i), i + 1, h)
        return

    precalc(table, prestate, curstate, i + 1, h)
    precalc(table, prestate, curstate | (1 << i), i + 1, h)
    precalc(table, prestate, curstate | (1 << i) | (1 << (i + 1)), i + 2, h)


def solve(h, w):
    def mat_mul(a, b):
        n, m = a.shape
        m2, l = b.shape
        assert m == m2

        result = np.zeros((n, l), np.int64)

        for i in range(n):
            for j in range(l):
                tmp = 0
                for k in range(m):
                    tmp = (tmp + a[i, k] * b[k, j]) % MOD
                result[i, j] = tmp

        return result

    table = np.zeros((1 << h, 1 << h), np.int64)
    for prestate in range(1 << h):
        precalc(table, prestate, 0, 0, h)

    ans = np.zeros((1 << h, 1), np.int64)
    ans[-1, 0] = 1

    tmp = table.copy()
    while w:
        if w & 1:
            ans = mat_mul(tmp, ans)
        tmp = mat_mul(tmp, tmp)
        w >>= 1

    return ans[-1, 0]


SIGNATURE = '(i8,i8)'
SIGNATURE2 = '(i8[:,:],i8,i8,i8,i8)'
from numba import njit

precalc = njit(SIGNATURE2, cache=True)(precalc)
solve = njit(SIGNATURE, cache=True)(solve)
print('compiled', file=sys.stderr)

h, w = map(int, input().split())
ans = solve(h, w)
print(ans)

Hanjoってローマ字で書かれるとキミノミヤさんが思い浮かぶ。