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

　Fまで六完。Gも解けなくてはいけない問題でした。

コンテストへのリンク

コンテスト後のツイート

トヨタ自動車プログラミングコンテスト2023#7(AtCoder Beginner Contest 328) Fまで六完。
C 累積和
D stack
E bit DPみたいに連結な集合がSのときの重みを全てもった
F 重み付きUnion-find
G 制約がbitDPだがbit DPじゃ上手くいかなそう→やっぱりbit DPぽいと気付いたがWA

— titia (@titia_til) November 11, 2023

G - Cut and Reorder

　解法ツイートを見てAC。

　bit DPだとは思ったが、どういう遷移なのかパッと分からず時間を浪費してしまった。Aの番号が小さい方から使っていくという、自然な遷移を考えれば良かったのだが。

　一番の難所であるはずの、メモリの制約が特殊だというのも気付いていなかった。適切なbit DPの遷移を思い付いていれば、メモリを節約するDPを思い付くのも難しくはない……とは思うものの、コンテスト中にこれができたかは分からない。