ABC208 参加記録

3完0ペナ 25分でした

A - Rolling Dice

最も小さい数 1 で合計した場合と、最も大きい数 6 で合計した場合を考えれば良さそうです。その間の数は 1 から 6 を自由に使えるのでいくらでも作れます。

よって、 $1\times A \leq B \leq 6\times A$ が成り立てば Yes、そうでないなら No です。

A, B = map(int, input().split())
if 1*A <= B <= 6*A: print('Yes')
else: print('No')

B - Factorial Yen Coin

この問題の貨幣の単位である $x !$ 円は、 $x! + (x+1)! > (x+2)!$ が成り立つことはないので、大きい方から単純に払っておけば良いです。これが成り立つ場合は DP で遷移を考える必要があります（ $(x+2)!$ 円よりも $x! + (x+1)!$ 円で払った方が結果的に枚数が少なくなる場合が出てくる）。

ゆえに、大きい方から商を答えに加算し、余りを次の $P$ 使って計算してけば、最小枚数を計算できます。最大枚数が 100 枚しかないので、その処理も追加しておけば問題ないと思います。

P = int(input())
S = [1]
for n in range(2, 11):
    S.append(S[-1] * n)

S.reverse()
ans = 0
while P > 0:
    for s in S:
        tmp = P//s
        if tmp > 100: 
            ans += 100
            P -= 100*s
        else:
            ans += tmp
            P = P%s
print(ans)

C - Fair Candy Distribution

まずは $K \geq N$ であれば、全員に同じ個数のお菓子を配れるので配ってしまいます。余りは、番号の小さい順に足していきます。python でやる際はソートする列の位置を次のように指定できます。例えば2列目をキーにしてソートする場合は list.sort(key=lambda x: x[1]) とかけます。

$A$ のインデックスと番号を持つリストに直して、番号でソートした後にお菓子を配り、出力時にはインデックスでソートして元の並び順に戻します。

N, K = map(int, input().split())
A = [(i, a) for i, a in enumerate(map(int, input().split()))]
A.sort(key=lambda x: x[1])
tmp = K//N
K %= N
ans = []
for i, _ in A:
    if K > 0:
        ans.append((i, tmp+1))
        K -= 1
    else:
        ans.append((i, tmp))
ans.sort(key=lambda x: x[0])
for _, x in ans:
    print(x)

本番ではダイクストラで実装しました。ダイクストラだと計算量が $O(N^{2}(N+M)\log{N})$ となりますが、今回の制約だと $O(N^{3})$ が $6.4 \times 10^{7}$ くらいになり、この時点で厳しいです。特に $(N+M)$ の部分を失念しており、最悪は $M$ の制約が $M \leq N(N-1)/2$ であることから、 $O(N^{4}\log{N})$ となります。

ちなみにダイクストラでの方針は、まずはスタートの頂点を固定（ここで $O(N)$ ）して、次に $k$ の値を動かすようにしました。 $k$ が増えていくごとに移動可能な頂点からの道を追加し、移動可能になった頂点をキューに入れてそこからダイクストラする、という風にしました。しかし辺が多いパターンでは計算量からして間に合わず、やはり TLE になります。

実際は、ワーシャルフロイド法を使って $O(N^{3})$ でできます。

私の中でワーシャルフロイド法は、書く手順だけ覚えて中身を理解できていないもの代表になっていました。まずはコードですが、要素がコストである隣接行列 g を使って以下のように書けます。

for k in range(N):
    for i in range(N):
        for j in range(N):
            g[i][j] = min(g[i][k] + g[k][j], g[i][j])

さて、この問題の状況で考えてみます。まずは、 $k = 0$ の場合です。スタートの頂点とゴールの頂点のみで到達できるかどうかを見ます。その際は g[i][j] を見れば良いです。

次に、 $k = 1$ の場合を考えます。頂点 $1$ を通る場合と通らない場合では、以下のように書けます。

$k = 1$ で固定して、g[i][k] + g[k][j] と g[i][j] を比較する。比較した値を隣接行列に反映する。

次に、 $k = 2$ の場合を考えます。同じく頂点 $1$ 、 $2$ を通る場合と通らない場合を考えますが、上記で $1$ を通った場合と通らない場合を調べた結果が反映されているので、頂点 $2$ についても同様に

$k = 2$ で固定して、g[i][k] + g[k][j] と g[i][j] を比較する。比較した値を隣接行列に反映する。

となります。これを続けていくと、結果ワーシャルフロイドの実装方法と同じになります。

初期化する際、辿り着かない値を大きな値にするのですが、float('inf') を使った場合なんと TLE になりました。 int 型と float 型を混ぜると幾分か低速になるようです。

提出コード

import sys

input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    graph = [[10**12]*N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1; B -= 1
        graph[A][B] = C
    
    for i in range(N):
        graph[i][i] = 0
    
    ans = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                tmp = min(graph[i][j], graph[i][k] + graph[k][j])
                if tmp < 10**12: ans += tmp
                graph[i][j] = tmp
    print(ans)


if __name__ == "__main__":
    main()

E - Digit Products

これは桁DP だな、、と思いましたが EDPC の桁DP がまだ理解できていなかったので諦めました。EDPC 履修後にやります。

F - Cumulative Sum

やれたらやります。

Xenous の精進記録

AtCoder関連他、学習したことの記録です。

A - Rolling Dice

B - Factorial Yen Coin

C - Fair Candy Distribution

D - Shortest Path Queries 2

E - Digit Products

F - Cumulative Sum