Toy と帽子と ADP BE

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

AtCoder Beginner Contest 205

4完。

崖にたどり着くスピードの差で負けました・・・。

各問題

A - kcal

何も考えずに計算問題を解けばいいです。実数解ですが、100で割るだけなので誤差も気にしなくてよいです。

B - Permutation Check

長さNの配列を用意して(いわゆるバケツ)受け取ったAを埋めていって全部埋まったか確認するもよし、受け取った配列をソートして前から順列になっているか確認するもよしです。(自分は後者で実装)

C - POW

根性で場合分けをします。(おい) powの単調性を使ってうまくやれば、そんなにエグいことにはなりません。(公式解説参照)

自分はうまくやらなかったので20行くらい書きました・・・。

D - Kth Excluded

(以下は自分がひねり出した解答であり、おそらく想定解ではありません・・・)

いずれとも異なる正整数の「かたまり」の左端に位置する数を値、そこがいずれとも異なる正整数のうち何番目に当たるかをキーしたmapを作ります。例えばA=(3, 5, 6, 7)なら、(1, 2), (4), (8, 9,...)なのでm[1]=1, m[3]=4, m[4]=8のようにします。あ、前準備としてAのソートが必要です。

このmapに対してKでupper_boundしてイテレータを一つ戻すと、ほしいK番目の数の「かたまり」にたどり着けるので、後は計算をします。例えば、K=2ならm[3]がヒットして、そこから一つ戻ったm[1]が1から始まる1番目なので、2番目は2という具合です。(伝われー

ていうか、ソースにすると至ってシンプルなので、そちらを参照してください。

atcoder.jp

E - White and Black Balls

どう考えても時間計算量が足らーん、と一時間ほどのたうちまわってコンテストが終わりました。

F - Grid and Tokens

みてません。

まとめ

Cがきれいに解けなかったのと、おそらくDが想定解ではなくいらぬ苦労をしてしまったため、時間をかけてしまい緑パフォに・・・。

まあ大きなミスはしていないので及第点かなぁといったところです。

f:id:mdstoy:20210613233148p:plain