AtCoder Beginner Contest 123
Updated:
Source codes
Solutions
A - Five Antennas
$E - A < K$ であるかどうかを判定する。
ポイント
sort 済みだったとは。
B - Five Dishes
$A[0], \dots, A[4]$ が全て $10$ の倍数の時は、どの順番で頼んでも結果は変わらない。そうでない場合は $0$ でない $A[i] \% 10$ が最も小さいものを最後に頼むと最小の時間となる。
C - Five Transportations
$M = \min(A[0], \dots, A[4])$ とする。この時移動にかかる最小値が $4 + (N + M - 1)/M$ であることを示す。
まず毎秒全ての交通機関に $M$ 人ずつ乗せると、最後の人が乗り始めるのは $(N + M - 1)/M - 1$ 分後であり、そこから $5$ 分後に最後の人が最終地点に到達する。つまり $4 + (N + M - 1)/M$ 分で移動する方法が存在する。
次に、 $M = \min(A[0], \dots, A[4])$ しか乗れない交通機関を考える。この交通機関で全員を運ぶためには $(N + M - 1)/M$ 回の移動が必要であり、それだけの分数がかかる。これ以外の都市も、全員移動だけは必ずしなくてはならないので、交通機関を利用するのに最低でも $1$ 分ずつかかる。つまり移動には $4 + (N + M - 1)/M$ 分以上かかる。
以上より、最小値の定義から答えは $4 + (N + M - 1)/M$ である。
ポイント
かなり早い段階で気がつけた。
D - Cake 123
普通にやると $O(XYZ)$ になり当然間に合わない。
コンテスト中の解法
まず $B$ と $C$ を全部組み合わせて $D$ を作る。これを sort, reverse する。これを $A$ と組み合わせると答えが出るのだが、 index を $X$ 個配列で持っておく。そして $A[i] + D[ind[i]]$ が最大値を達成する場合は $ind[i] \mathbin{ {+} {+} }$ する。これを $K$ 回繰り返す。計算量は $O(YZ \log (YZ) + X K)$ である。
模範解法 その 1
まず $B$ と $C$ を全部組み合わせて $D$ を作る。これを sort, reverse する。これの上位 $K$ 個以外は絶対に必要ない。なぜなら $D[K] + A[0]$ よりも $K$ 個の $D[i] + A[0]$ の方が大きいからだ。ゆえにこれと $A$ と組み合わせると答えが出る。計算量は $O(YZ \log (YZ) + XK \log(XK))$ である。
模範解法 その 2
$A, B, C$ を組み合わせるが、よく考えると $A[i]B[j]C[k]$ が答えになりえるのは $(i + 1)(j + 1)(k + 1) \leq K$ のときのみである。なぜなら $(i’, j’, k’) \leq (i, j, k)$ となる $(i’, j’, k’)$ が $K$ 個以上存在すると、それらは $A[i’]B[j’]C[k’] \geq A[i]B[j]C[k]$ を充たす。ゆえに上位 $K$ 個には入らない。したがって枝刈りを入れていけばよろしい。計算量は $O(K (\log K)^3)$ で抑えられる。
模範解答 その 3
$i \in K$ についての帰納法で解く。 $i = 0$ のとき、答えは $A[0]B[0]C[0]$ である。すると次の候補は $A[1]B[0]C[0]$, $A[0]B[1]C[0]$, $A[0]B[0]C[1]$ である。 $i \in K$ の候補が列挙できているとする。このとき最大値をとった index $(x, y, z)$ とする。 $i + 1$ の最大値としてありえるものは、今の最大値を除いた集合に $(x + 1, y, z)$, $(x, y + 1, z)$, $(x, y, z + 1)$ を重複を除いたものを入れることである。
最大値の候補は priority queue で管理すればよろしい。また同じ候補を二度と入れないためには set を使って入れるときに判定する。
計算量は $O(X \log X + Y \log Y + Z \log Z + K \log K)$ である。
ポイント
色々な解法があって驚いた。
Others
18 位でした。やったね。