AtCoder Beginner Contest 062

更新日時:

AtCoder Beginner Contest 062

ソースコード

解法のメモ

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 を使えばよろしい。

ポイント

どうしても植木算的なミスは出てしまう。

その他

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 は自分でサンプルを足して実行した。

コメントする