Toy と帽子と ADP BE

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

AtCoder Beginner Contest 204

4完3WA。

阪神タイガースばりのオセロ状態を続けております。(時事ネタ*1

各問題

A - Rock-paper-scissors

xとyが異なる場合は余ったものを、同じ場合は同じものを出力します。

なお、こんなん効率のいい実装を考えてる間に書けるわーとかいってif文書きまくりました。

B - Nuts

入力一つずつ10より大きいかどうかを判定して、大きければA-10を答えに加算、大きくなければ無視を繰り返します。

判定せずにmax(0, A-10)を加算していくのもありかと思います。

C - Tour

令和ABCのCは全探索のC、ということで、各都市からたどり着ける都市をDFSで全探索すればよいです。ループには気をつけましょう。(←ちょっとハマった人)

D - Cooking

DPで、合計何分なら構築可能かを調べます。N=100, T=1000なので、最大でも100000分で、10^2 * 10 ^ 5のテーブルになるので、間に合う量です。

あとは、Tの合計値の半分(切り上げ)から順に多い方にあり得るかあり得ないかを調べて、最初にあり得たところが答えです。

貪欲を書いて2WAと、DP解のときN=1に引っかかって1WA・・・。

E - Rush Hour 2

やること自体はそんなに難しくなさそうなのですが、最適な待ち時間を求める方法がわからず・・・。(総当りするとTLE)

最終的に三分探索に手を出しましたが、これも(かなり工夫しないと)ダメらしいので、ダメです。

F - Hanjo 2

ちょっと見て、PG BATTLEにこんな問題なかったっけ?とおもいきや、横幅が広すぎてむりー、となってました。

まとめ

Eが解けなかったのも厳しいですが、Dで貪欲に手を出して時間をロスしてしまうのがもっと厳しい、というかダメ。精進が足りません。

f:id:mdstoy:20210606231041p:plain

*1:阪神の方は今日16で記録が止まりましたが