tookunn’s diary

主に競技プログラミング関係

京セラプログラミングコンテスト2021(AtCoder Beginner Contest 200) D - Happy Birthday! 2

問題

atcoder.jp

考察

数列Aから異なる部分数列B,Cを探してB,Cそれぞれの総和のmod200が同じものを出力する問題。

重要な点としては

  • 数列Aから見つかる部分数列は2^N-1通り
  • 部分数列の総和のmod200は200通り
  • 数列Aの長さがある長さ以上になったら、総和のmod200が被る部分数列が存在する

数列Aから見つかる部分数列は2^N-1通りあるので、単純に部分数列を全探索するのは無理そう。

部分数列は2^N-1通りあるが、その部分数列の総和のmod200は0~199の200種類のため
総和のmod200が同じものは結構ありそう。

数列AのN個の要素すべてを見なくても良さそうだが、見る必要がある要素、必要がない要素はどう判断するか。

部分数列の総和のmod200が必ず被るようになる数列を考える。

数列Aから見つかる部分数列は2^N-1通り存在し、部分数列の総和のmod200についてはそれぞれ異なる場合でも高々200通りのみ。

つまり、部分数列が201通り以上存在する場合は、部分数列の総和のmod200が被るものが必ず存在するということ。
(こういうのに鳩ノ巣原理という名前がついているらしい)

2^N-1が201通り以上になる数列には必ず総和のmod200が被る部分数列が存在するので、
数列Aの長さNが8以上の場合は必ず被る部分数列が存在する。

N >= 8の場合は数列Aの先頭から長さ8までの要素のみを見て、被る部分数列を探索する。
N < 8の場合は数列A全体の要素を見て、被る部分数列が存在するのか、存在するなら被る部分数列を探索する。

最大でも長さが8の数列の部分数列を列挙すれば良い。
8個(もしくは8個以下)の要素をそれぞれ部分数列に含める、含めないを探索していくので最大2^8-1(255)通りの部分数列を列挙して
総和のmod200を取りつつ、既に列挙した中に総和のmod200が同じものが存在していれば、該当する2つの部分数列を出力する。