AtCoder Beginner Contest 062
Updated:
Source codes
Solutions
A - Grouping
やるだけ。
ポイント
これ実装にくだらない労力がかかるだけで、得るものがない。やっていて不毛に感じた。
B - Picture Frame
これもやるだけ。
ポイント
前の問題と違って、普通の問題。模範解答は、最初に # で埋めておいた配列の真ん中に a[i][j] をコピーするという。
C - Chocolate Bar
半分だけ全探索する。あとで $H, W$ は swap するものとし、横方向に最初に切り出す(全探索)。残りの長方形を「半分」にする方法は 2 通りあるが、どちらも試す。 $O(H + W)$ で済む。
ポイント
残った長方形を「半分」にする方法を両方試す必要がある。その 2 つの長方形を比べても意味がない。
D - 3N Numbers
priority_queue の問題。仮に、上と下を区切る位置を決め打ちしたとすれば、上は大きいものから順番に $N$ 個、下は小さいものから順番に $N$ 個、貪欲法で和を取ればよろしい。
決め打ちの場所がずれると、今までのトップ $N$ 個が $1$ つだけずれるだけである。こういうのは priority_queue を使えばよろしい。
ポイント
どうしても植木算的なミスは出てしまう。
Others
A - sample: 2, tle: 2.000, time: 00:19, from_submit: 43:27
B - sample: 2, tle: 2.000, time: 01:42, from_submit: 41:44
C - sample: 6, tle: 2.000, time: 16:55, from_submit: 24:50
D - sample: 3, tle: 2.000, time: 24:50, from_submit: 00:00
C は自分でサンプルを足して実行した。