Toy と帽子と ADP BE

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

AtCoder Beginner Contest 234

5完。

各問題

A - Weird Function

問題文通りに関数を定義して、問題文通りに呼び出せばよいです。

B - Longest Segment

全ての点の組み合わせの距離を出して一番長いものを取ればよいです。

C - Happy New Year!

Kを2進数表記して、1を2に変えればよいです。

これ、たまたま気づいちゃったって感じだったんですけど、考察ってどうやってするんでしょ?(おい

D - Prefix K-th Max

priority_queueに、それまでに登場したうちで上位K個を(小さいものが上になるように)保存しておき、次のPがqueueの中の最小の数より小さいなら無視、大きいならそれまでの最小を捨ててPを加えたうえで、最小の数が何かを確認します。

E - Arithmetic Number

これ、上二桁が決まった時点で後ろに続く数は一意に定まるので、等差数の数は相当少ないです。なので、等差数を先に列挙してしまえば後は二分探索で見つかります。

自分は実戦では(等差数が少ないことを考慮した上で)再帰を書いて求めました。

F - Reordering

DPなのはわかるのですが、並び替えがわからんとなってました。

まとめ

Eまで詰まらずに解けたのはよいですが、Fとしては比較的簡単そうに見えるDPが解けなかったのはいかんですね。

f:id:mdstoy:20220108232035p:plain