情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

AtCoder Beginner Contest 099

AtCoder Beginner Contest 099の解説です。
ABC099 旧版:
abc099.contest.atcoder.jp
ABC099 beta:
https://beta.atcoder.jp/contests/abc099/beta.atcoder.jp

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 099
rated 1200
6/10(日) 21:00 ～ 22:40 (100分)
100-200-300-400 (4問)
ペナルティ: 5分

方針

全完

A - ABD

要するに、1 \leq N \leq 999ならABC、1000 \leq N \leq 1998ならABDです。
なので1 \leq N \leq 999ならABCと、それ以外ならABDと表示すれば良いです。

B - Stone Monument

まず、西からi本目の塔の高さは1 + 2 + \cdots + iなので、i + 1本目の塔とi本目の塔の高さの差は(1 + 2 + \cdots + i + (i + 1)) - (1 + 2 + \cdots + i) = i + 1になります。
つまり、b-aに対し東側の塔の本来の高さは1 + 2 + \cdots + b - a = \frac{(b - a)(b - a + 1)}{2}であったことが分かるので、雪に埋もれている部分は\frac{(b - a)(b - a + 1)}{2} - bとなります。

C - Strange Bank

解説は良く分からないのでDPで
まず、取り方は1,6,9,36,81,216,729,1296,6561,7776,46656,59049の全12通りです。
次に、これを取った時を考えます。
例えば、今10円で、まず1円を取ったら残りは9円ですよね。
この時、9円からの最小のとり方が分かっていれば、10円の時も分かるのではないかと考えます。
今、x円持っているときの最小のとり方をf(x)としましょう。f(0)=0です。
この時、f(x)=\min(f(x-1), f(x-6),\cdots,f(x-59049))+1です。
ということは、後はf(1)から順にf(N)まで求めれば答えが分かります。
計算量は、取り方が指数の逆、つまり\log Nの定数倍の範囲になるのでO(N \log N)です。

D - Good Grid

まず、N=1の時色を変える必要が無いので答えは0です。
そうでない時を考えます。
この時、まず(0, 0)の位置の色を決め打ってみましょう。
そうすると、(0,3),(0,6),\cdots,(1,2),(1,5),\cdotsの色も(0,0)と同じ色になるので自動的に確定します。
ということは、O(CN^2)で色を決め打てます。
これを同様に(0,1)と(1,1)で決め打つと、全ての場所において色を決め打った時の違和感の大きさが確定します。
後はこの3か所について、それぞれどの色にすると違和感が最小になるか求めることで答えが出せます。
これはO(C^3)ですから、最終的にO(CN^2+C^3)で答えが求まりました。

結果

oooo 4完(1000点) 65:14(0WA)
224位

感想

C問題が難しかった……愚直が次々落とされるので。
ただ、こういう問題は得てして漸化式を作れることが多いのでやってみると行けるかもしれません。
後、D問題は愚直だとO(C^3N^2)ですが、これは色決め打ちしたときの全マス検索なので、
こういう複数決め打ち→全部調べるは、逆に各々調べる→複数決め打ちにすると計算量が減ることが多いです。