Toy と帽子と ADP BE

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

トヨタ自動車プログラミングコンテスト2023#4(AtCoder Beginner Contest 311)

4完

各問題

A - First ABC

素直に各文字が出現したかどうかを確認するboolを3つ用意して、全部trueになったらそこが答えとしました。

ビット演算とか使えば記述量を減らすことは可能ですが、まあ誤差だし変なはまり方するリスクを負う必要もないので。

B - Vacation Together

単純に初日から順に数えていけばよいです。暇でない人がいるところで最大かどうか確認してから、リセット。最終日が含まれる時だけ注意。

C - Find it!

DFSで閉路検知したら戻りがけに通過順を保存していけばよいです。

D - Grid Ice Floor

DFSで移動していけばよいです。停止したところは覚えておいて二度目は使わない(使うと無限ループする)ことに注意。あと、通過したマスでも停止したマスでなければそこから再移動する必要があるので、通過と停止を分けて考える必要があります。

E - Defect-free Squares

二次元累積和をとってごにょごにょしましたが、1/3ほどがWAで原因が特定できないまま時間切れ...。

DPか累積和か迷って累積和で頑張る方を選びましたが、DPがあたり方針だった模様。

まとめ

E、第一感DPだったので、それを信じるべきだったか...。