ABC479(AtCoder)参加記

今週の参加記

こんにちは。やっと寒くなってきて嬉しいです。暑いのが苦手なので、過ごしやすくなってきていいですね。朝の空気が澄んでいるので冬は好きです。

AtCoderのABC479に参加してきました。 今週も、少しだけ勝ち！実力通りに解けたので、一旦は満足しています。

今週も、問題を解いた感想と解法への言及を書いておきたいと思います。

結果

考察・所感

A問題、B問題

割愛しても問題ないと思える内容だったので、省略します。サークルのほうでもこの回を担当しましたので、是非そちらもご覧ください。 繰り返しと条件分岐のみで愚直に正解できる問題でした。最近の連続降雨にちなんでB問題のテーマ『B - Longest Rainy Streak』は定められたのかもしれませんね。 だとしたら面白いです。解いている間は気づきませんでした。

C問題

本当にDPを使ってナップザック問題を解くときに似ている問題文ですよね。実際にDPで解いた方は下のclapボタンを連打してください。 $N\le20$ という極めて小さい制約から、状態の全探索が間に合うということに早い段階で気づけたので、bit全探索を書きました。 しばらくぶりでしたが、間違わず書けたことに安心しています。

D問題

簡単に言うと、直接$i$から$j$に直接向かう方法と、離れる方向に行ってから折り返す方法の2種類を考えればよいです。 それぞれ最適な経路が1通りしかありませんから、それを探すためにデータ構造を駆使しようねという問題でした。 難しすぎることはなく、問題文を理解した後は比較的簡単に解けたと思います。

E問題

グラフ問題ですね。 グラフやグリッドは、数直線上でなんやかんやしたり整数をなんやかんやする問題よりも動きがイメージしやすくて理解しやすいです。 今回は木に対してDFSを行った時にノードをメモしておき、それを使って帰りがけを再現するという実装を行ったのがミソです。 これをしないと自力実装は厳しかったと思います。書く量が増えるとバグの数も増えるので、勘弁していただきたいものです。 そしてこういう問題に余裕を持って取り組むためにも、D問題までをスムーズに解けるようになっておきたいですね。

最後に

今週もよく頑張りました。なんだか5完できる週が増えている!この調子で行きたいです。 しかし、本番中に水色相当の難易度の問題を解けたことがないので不安なところです。ミスなく緑色までをなるべく早く解く、が次回の目標です。 ではまた。

関連リンク

今回のコンテスト成績証

https://atcoder.jp/users/Caffeineholic/history/share/abc479

和歌山大学競技プログラミングサークル公式HP

https://wcpc.pages.dev