【競プロ精進日記】AtCoder ABC160

2020.04.01
競プロ

1. はじめに
2. A
3. B
4. C
5. D
6. E
7. F

はじめに

当ブログは問題の解説がメインではなく、筆者の解法やアイデアの保存がメインです。
したがって、読者の期待に沿えないことがあると思いますがご了承ください。

A

A – Coffee
問題に従う
https://atcoder.jp/contests/abc160/submissions/11264524

B

B – Golden Coins
500円硬貨だと1円当たり嬉しさ2、5円硬貨だと1円当たり嬉しさ1なので、500円硬貨から両替したほうが良いです。
500円硬貨に両替できる枚数×1000＋両替後の残金で5円硬貨に両替できる枚数×5が答え。
https://atcoder.jp/contests/abc160/submissions/11269741

C

C – Traveling Salesman around Lake
最も間隔の広い家を通らないのが最短です。
したがって、各家の間隔を計算します。
\(1\leq i \leq N – 1\)における次の家への間隔は\(A_{i+1}-A_i\)ですが、\(i=N\)では、\(K-A_N+A_1\)が間隔になります。
これらの間隔の最大値を\(K\)から引いたものが答えになります。
https://atcoder.jp/contests/abc160/submissions/11281569

D

D – Line++
頭が混乱します。
\(N\leq 2\times 10^3\)なので、\(O(N^2)\)まではできそうです。
BFSが\(O(N)\)でできるので、すべての頂点でBFSしてもよいです（頭を使わなくていい）。
私は、頂点\(i\)から\(j(\lt i)\)への最短距離を考えて解きました。
すると、頂点\(i\)から頂点\(j\)までまっすぐ行く経路（\(j-i\)）とワープ（X,Y）を通って行く経路（\(|i-x|+|j-y|+1\)）の小さい方が最短です。
この最短距離を配列の添え字にしてカウントして、最後に出力すればACです。
https://atcoder.jp/contests/abc160/submissions/11300116

E

E – Red and Green Apples
難しそうに見えて実は簡単で、やっぱり難しい？を繰り返しました。
p,q,rで大きいものから使っていく。そして、pは最大X個まで、qは最大Y個まで、p,q,r合計でX+Y個まで使っていけばおいしさの総和が最大になります。
各配列をソートして、添え字でごにょごにょすると面倒なので、p,q,rをまとめて優先度付きキューを使ってしまうのが簡単です。

添え字でごにょごにょ↓
https://atcoder.jp/contests/abc160/submissions/11399706
優先度付きキュー↓
https://atcoder.jp/contests/abc160/submissions/11318154