Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 145

5AC1WA。コンテストでDP通したのは(ちょっと前のフィボナッチ階段を除いて)初めてかも。うれしい。超うれしい。

各問題

A - Circle

円の面積は半径×半径×πなので、半径がr倍になると面積はr*r倍になります。よってr*rを出力すればよいです。

B - Echo

単純に与えられた文字列を半分に割って比較すればいいだけです。なお、文字列の長さが奇数のときは、半分に割れないので無条件で"No"です。 (多分それを考慮する必要はないように実装にできると思いますが)

C - Average Length

Nが最大8なので、全部計算しても余裕で間に合います。計算しましょう。 c++ならnext_permutationで楽できます。

D - Knight

慌てず騒がずグラフにプロットしてよく見てください。パスカルの三角形です。二項係数です。 あとは与えられた座標が、パスカルの三角形でどの位置に来るかを割り出せばよいです。

まず、取りうる座標は必ずx+yが3の倍数になります。(そもそもそうならないときは0を出力) 例えば、3回ジャンプしたときはジャンプ先の座標が(3, 6), (4, 5), (5, 4), (6, 3)のように、`x + y == 9'の位置に並びます。 その法則性から、位置が判別できると思います。

E - All-you-can-eat

時間を重さ、美味しさを価値に置き換えれば、ほぼほぼ典型のナップサックDPです。

ただし、「注文が時間内に間に合えば、食べるのにどれだけ時間がかかっても良い」という条件があるので、DP配列の時間に当たる部分を充分に大きく取って(制約から、6000ちょっと取っておけば余る)、漸化式のところで「料理を注文する時間がT以上にならないこと」という条件を追加する必要があります。

また、先に時間のかかる料理を食べてしまうと損することは明らかなので、料理を食べる時間Aでソートしておく必要があります。(私はこれに気づけず1WA出しました)

F - Laminate

さっぱりわかりませんでした・・・。

まとめ

DもEもど典型にひとひねり加わっている問題で、こういうのが解けると気持ちがいいです。 最近DPを集中して練習していた成果も出て、いうことなしです。

久しぶりの青パフォで、レートも大幅回復しました。来週土日両方コンテストありますし、なんとかそこで水色復帰したいものです。

f:id:mdstoy:20191117140610p:plain