かんプリンの学習記録

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

ABC200 D - Happy Birthday! 2

問題はこちら

問題概要

{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にしてはむずい.デバッグめんどい.鳩ノ巣原理あたまいい.