ABC200D

動的計画法の実装を工夫すると、時間計算量は$O(MN^2) (M=200)$となる。

dpの定義：

$dp[r][s]=和の余りがrとなる正整数の集合がs$

サンプルコード

M=200
n=int(input())
A=[*map(lambda x:int(x)%M,input().split())]
# dpを 辞書型 { 余り:{正整数} } に初期化
from collections import *
dp = defaultdict(set)
dp[0] = set()
for i in range(M):
  for d in dp.copy():
    dd = dp[d]
    for j in range(n):
      # jがdp[d]にあればパス
      if j in dd: continue
      r = (d+A[j])%M
      s = dd | {j} # ddにjを追加
      # dp[r]がdp[d]ならパス
      if s==dp[r]: continue
      # dp[r]がすでにあれば回答、なければsを登録
      if dp[r]:
        print('Yes')
        B = [i+1 for i in dp[r]]
        C = [i+1 for i in s]
        print(len(B),*B)
        print(len(C),*C)
        exit()
      dp[r]=s
print('No')

公式解説では鳩ノ巣原理を前提としたbit全探索が紹介されている。
個人的には、設計は出来たものの、DPなどの実装技術がまったく不足しており、技術力を鍛錬する必要がある。

[Python] 動的計画法 ABC200D

ABC200D