京セラプログラミングコンテスト2021(AtCoder Beginner Contest 200) D - Happy Birthday! 2
問題
考察
数列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つの部分数列を出力する。