かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC200 D - Happy Birthday! 2

ABC 動的計画法 解説 競技プログラミング

問題はこちら

問題概要

{N}個の正整数からなる数列{A}が与えられる．{1\leq B_i < B_{i+1}\leq N}と{1\leq C_i < C_{i+1}\leq N}を満たす異なる数列{B,C}であって{\sum_{i=1}^{|B|}A_{B_i}\equiv \sum_{i=1}^{|C|}A_{C_i} \mod 200}を満たすものが存在するか判定し，存在するならば{1}つ出力せよ．

{2\leq N \leq 200\\ 1\leq A_i\leq 10^9}

解説

{A}の要素を「{B}に振り分ける」，「{C}に振り分ける」，「どちらにも振り分ける」とすればいけそう．{\sum B-\sum C\mod 200}を管理するDPをすればいい．ただし，{3}つの振り分け方のうち少なくとも{2}つを行う必要がある．

結局，持つべき状態は「{A}の何番目を見てるか」「{\sum B-\sum C\mod 200}」「{3}つの振り分け方のどれを使用したか」．

経路復元も頑張ってする．経路復元の例

計算量は{M}をmodとして{O(NM)}

提出プログラム

https://atcoder.jp/contests/abc200/submissions/22448830

感想

Dにしてはむずい．デバッグめんどい．鳩ノ巣原理あたまいい．