D - Happy Birthday! 2
・問題URL
https://atcoder.jp/contests/abc200/tasks/abc200_d
・思考
・Aは200で割った余りにしといてよさそう(あんま意味ない)
・Aからいくつかとってできたある数列201種類を持ってくるとその中に200で割った余りが等しいものが存在する
・Nがでかいときも、Aのうち初めの数個全探索すればいいのでは
・キーワード
・鳩ノ巣の原理
・bit全探索
・解法
・N≤8の場合、2⁸=256だから、Aの各要素をB(あるいはC)に入れる/入れないの2⁸通りbit全探索を二重ループにして条件を満たすものを探しても間に合う。B,Cが空の場合とB=Cの場合continue。
・N>8の場合、N=1~8までで数列は2⁸-1=255個出来るから、鳩ノ巣の原理よりこの中で総和を200で割った余りが等しいものが必ず一組は存在する(つまり必ずYES)。よってN=8としてN≤8の時と同じことをすればよい。
・コード
int main() {
int N;
cin >> N;
vector<ll>A(N);
rep(i, N)cin >> A[i];
if (N > 8) N = 8;
bool Q = false;
for (int bit1 = 0; bit1 < (1 << N); bit1++) {
for (int bit2 = 0; bit2 < (1 << N); bit2++) {
vector<int>B, C;
ll b = 0, c = 0;
for (int i = 0; i < N; i++) {
if (bit1 & (1 << i)) {
B.push_back(i);
b += A[i];
}
}
for (int i = 0; i < N; i++) {
if (bit2 & (1 << i)) {
C.push_back(i);
c += A[i];
}
}
if (B.size() == 0 || C.size() == 0)continue;
if (B == C)continue;
if (b % 200 == c % 200) {
cout << "Yes" << endl;
cout << B.size() << " ";
for (auto v : B)cout << v + 1 << " ";
cout << endl;
cout << C.size() << " ";
for (auto v : C)cout << v + 1 << " ";
cout << endl;
Q = true;
break;
}
}
if (Q)break;
}
if (!Q)cout << "No" << endl;
}