https://yukicoder.me/problems/no/1017
解説
https://yukicoder.me/submissions/458766
今までの経験からして、これ系で行けそうというものはあるが、制約がちょっと厳しいのと、構築する必要がある。
なにも思いつかんけど、難易度がREDじゃないというときは、何か性質を見抜くべきと考えよう。
つまり、自明な所から考えてみる。
まず同じ数が1ペアでもあれば、それを+と-にして他を全部0にすれば答えが作れる。
よって、考えるべきは、すべて異なる数が与えられた場合である。
この場合、割と作れそうな感じがするが、ここからの思考が難しい。
んー、分からん!
(解説読み中…)
どんなパターンでも22種類くらいあれば構築可能とのこと。
N=22という基準は鳩ノ巣原理で端的に言える。なるほど。明白だ。
そういう問題どっかで見たな。
ではなく、端的に換言すると、こういうのを早く思い出せ(反省)。
まあ、結論としては配列Aの先頭22個を取り出してN≦22の問題として改めて解くことを考える。
こちらの問題もまあまあ実装に困るのだが、半分全列挙を知っていればO(3N/2)がアルゴリズムとしては一番わかりやすい。
とりあえず、O(N2N)の解法を紹介しておく。
O(N2N)ですべての部分集合について総和を計算する。
それで以下の配列を構築する。
msks[tot] := 総和がtotとなる部分集合mskの集合
説明がちょっとわかりにくいが、コードを見て補完してほしい。
この時、「totが最も小さくて、個数が2個以上のmsks[tot]の1番目の集合と2番目の集合は必ず共通項を持たない」。
これはなぜかというと、共通項をもし持つのであれば、それをどちらの集合からも削除して、totがより小さいものにできるためである。
なので、totが最小のmsks[tot]の1番目と2番目を取ってくれば、それが+にする集合と-にする集合となるので、
それを+,-にして他を0で答えると答え。
int N, A[151010]; vector<int> msks[4010101]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> A[i]; int M = min(22, N); rep(msk, 0, 1 << M) { int sm = 0; rep(i, 0, M) if (msk & (1 << i)) sm += A[i]; msks[sm].push_back(msk); } rep(tot, 1, 4010101) if (1 < msks[tot].size()) { int plus = msks[tot][0]; int minus = msks[tot][1]; printf("Yes\n"); rep(i, 0, M) { if (i) printf(" "); if (plus & (1 << i)) printf("%d", A[i]); else if (minus & (1 << i)) printf("-%d", A[i]); else printf("0"); } rep(i, M, N) printf(" 0"); printf("\n"); return; } printf("No\n"); }