AtCoder diverta 2019 Programming Contest 2 参戦記

AtCoder の diverta 2019 Programming Contest 2 に参戦しました。

結果は ABC (1WA) を早解きして 424 位。D 問題に 1 時間半かけて解けなかったのは悔しいです。(なお +20 分で AC しました。)
パフォーマンスのほうはまずまずで 1819。レーティングはぎりぎり青復帰ならずです。

f:id:y_r:20190615235659p:plain

瞬殺した...はずだがまさかの WA。原因は他のコンテストの回答をなげていたため。

n = 50 なので 4 重ループがまわせる。

の 4 重ループをまわして AC

が最大値を構成する。

最初の考察であっていたのは

のみ。最初は A, B で 1 種類しか金属に交換しない方法で当然ながら WA。以下のように実装をかえつつ粘ったがAC できたのはコンテスト終了後...さらに当然のごとく実装行数がかさんでるので、もっといい方法があるはず。

3 種類の金属をうまく組み合わせれば最大になる -> 金と銀 (銅は移動先との価値比に応じて全ぶっぱ or 交換なし) に関する 2 重ループを実装して TLE。
移動地点先の交換価が低い金属を交換しても無駄なので考慮しない -> TLE
- B -> A の戻りで最大 $(5000 * 5000)^2$ ぐらいのループになる
B -> A は A -> B で交換できる金属の種類数に応じて最適化できる
- A -> B で交換できない : B -> A でのループは $5000^2$ なので A -> B と同じ計算
- A -> B で 1 種類交換 : B -> A は 2 種類交換。全ループすると TLE なので以下の工夫をする
  - B でのどんぐり数を $n$ , 1 種類目の価値を $p1$ , 2 種類目の価値を $p2$ とすると探索するのは $0 <= i * p1 <=p1 * p2$ の間と $(n - p1 * p2 - p1 + 1) <= i * p1 <= n$ の間でよいのでここに限って探索する
- A -> B で 2 種類交換 : B -> A は 1 種類交換。全ぶっぱすればよい
- A -> B で 3 種類交換 : B -> A は交換できないのでパススルー *1
これで AC