ABC208

結果

A \ 05:20

B \ 15:15

C \ 24:02

D \ 40:29

2WAの4完で，パフォは1432，rating変動は +92で 738 \to 830でした．

考察

A問題

N個のサイコロで表せる和の最大は 6 \times Nなので， 6 \times N \lt Kならば確実にNoです．

K \leq 6 \times N ならばYesかというと実はそうではないです(そのせいで2WAした)．

N個のサイコロで表せる和の最小は 1 \times Nなので， K \lt NならばNoです．

逆に N \leq K ならばYesです．

B問題

支払う硬貨の枚数を最小化するので，硬貨はできるだけ高価なものを使いたいです．

よって， n=10, 9, \cdots, 1と見ていき， n! \leq Nならば N \lt n!となるまで n!円硬貨で払い続けます．

ちなみに問題文の 100枚というのは気にしなくてもよいです．

10! \times 100 \gt 10^{7}なので硬貨が足りないこともないし， n!円硬貨が 100枚あると (n+1)!を超えますが，既に (n+1)!硬貨未満まで支払いをしているためです．

C問題

N \leq Kならば，とりあえず全員に K/N個ずつお菓子を配っておき，お菓子の個数 Kを K \% Nで更新します．

( K/Nは切り捨て除算， K \% Nは剰余演算)

次に， i番目という情報を持ったまま国民番号についてソートします．(私はpairで実装しました．)

あとは国民番号が小さい方から N人分だけ，持っておいた i番目という情報によってお菓子を 1つ増やします．

D問題

Warshall Floydです．

Warshall Floyd法では，経由してもよい頂点が k以下であるという制約で最短経路を更新していきます．

よって，最短経路を持つ隣接行列を kの更新ごとに毎回見て，INFでないものは全て答えに加算していきます．( 0は足しても 0なので足しとけばOK．)

感想

A問題で2WAしたときはどうしようかと思いましたが，D問題で大挽回しました．

最短経路は何回か書いたことがあったので，Warshall Floyd法の性質を覚えていたおかげで爆速でDを解けました．