Toy と帽子と ADP BE

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

AtCoder Beginner Contest 183

5完1WA。

各問題

A - ReLU

ReLU関数の定義どおりプログラムを書けばいいです。

B - Billiards

えーと、y座標の比を求めて、x座標に適用します。算数の問題自体はすぐ解けたんですけど、実装に意外に手こずってしまった・・・。

C - Travel

c++ならnext_permutationを使えば瞬殺ですね。[2, n]の配列(0-indexedにしたいので実際は[1, n)にしますが)をnext_permutationで回して、おのおの計算していけばいいです。

D - Water Heater

開始時刻と終了時刻を保持するの配列の配列を作って、時刻1から順に必要なお湯の量をシミュレートすればよいです。必要なお湯の量について、開始時刻になった人についてはその人のPを足し、終了時刻になった人についてはその人のPを引きます。それが一度でもWを超えてしまったらNoです。

E - Queen on Grid

DPが見えますが、単純にやるとTLEします。(しました)

というわけで、縦横斜めの3方向それぞれについて、累積和を持ちながらDPをやると線形になって間にあいます。

F - Confluence

dsu (Union-Find)を使うのはそうとして、クラスに属している生徒の管理を効率よくやる方法が見つからず、TLEどまりでした。

DとEで時間がかかりすぎたのが痛かった・・・。

まとめ

(自分の中では)ちょっと難し目のDPを通せて5完できたので、いい感じです。ただ、Dに時間がかかりすぎたのが反省点ですね。

遅すぎたため、レートは微増止まりでした。いやしかし、あのDP通してこれなの?!

f:id:mdstoy:20201115225817p:plain