yukicoder - No.183
No.183 たのしい排他的論理和 (EASY)
スイッチの押し方全て調べると O(2N) となり N = 5000 では到底無理なのでなんかいい方法があるはず.
1 ≦ Ai ≦ 214 = 0100 0000 0000 0000 であるから
XOR の結果としては最大 215 - 1 = 0111 1111 1111 1111 までありうる.
そこで MAX = 215 として dp テーブル dp[MAX] を用意し,
整数 j を作ることができる場合 dp[j] = true となるようにする.
初期状態 dp[0] = true として開始し,Ai を読み込むごとに
0 ≦ j < MAX に対して dp[j] = true なら dp[j XOR Ai] = true とする.
i 回目のループを回し終えた時点で,
dp テーブルには i 番目までの整数を用いて作れる整数が格納される.
コードで書くなら
for (int i = 0; i < N; i++) { cin >> tmp; //A[i] 読み込み for (int j = 0; j < MAX; j++) if (dp[j]) dp[tmp ^ j] = true; }
上記の操作を AN まで行い,dp テーブルに立っているフラグの本数を数えればそれが答えになる.
時間計算量は O(MAX * N) なのでギリギリ間に合う.
例(サンプル 2)
入力:
6 1 1 4 5 1 4
i | Ai | dp[0] | dp[1] | dp[2] | dp[3] | dp[4] | dp[5] | dp[6] | dp[7] | |
---|---|---|---|---|---|---|---|---|---|---|
0(初期) | - | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | |
2 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | |
3 | 4 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | |
4 | 5 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | |
5 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | |
6 | 4 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
よって答えは最後の行のフラグの本数で 4.
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cmath> #include <string> #include <vector> #include <algorithm> #include <queue> #include <map> #include <functional> #include <set> #include <numeric> #include <stack> #include <utility> #include <time.h> //#include "util.h" using namespace std; typedef unsigned uint; typedef long long ll; typedef unsigned long long ull; //呪文 template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const pair<_KTy, _Ty>& m) { cout << "{" << m.first << ", " << m.second << "}"; return ostr; } template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const map<_KTy, _Ty>& m) { if (m.empty()) { cout << "{ }"; return ostr; } cout << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { cout << ", " << *itr; } cout << "}"; return ostr; } template <typename _Ty> ostream& operator << (ostream& ostr, const vector<_Ty>& v) { if (v.empty()) { cout << "{ }"; return ostr; } cout << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { cout << ", " << *itr; } cout << "}"; return ostr; } template <typename _Ty> ostream& operator << (ostream& ostr, const set<_Ty>& s) { if (s.empty()) { cout << "{ }"; return ostr; } cout << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { cout << ", " << *itr; } cout << "}"; return ostr; } #define PI 3.14159265358979323846 #define EPS 1e-6 #define MIN(a,b) ((a)<(b)?(a):(b)) #define MAX(a,b) ((a)>(b)?(a):(b)) #define all(x) (x).begin(), (x).end() int yuki0183() { // A_i は 2^14 = 100000000000000 までとりうるので // XOR の結果は最大 2^15 - 1 = 111111111111111 までありうる const int MAX = 1 << 15; // dp[i] が true なら i をつくることができる bool dp[MAX] = { 0 }; // 0 は初期状態 dp[0] = true; int N; cin >> N; int tmp; for (int i = 0; i < N; i++) { cin >> tmp; for (int j = 0; j < MAX; j++) if (dp[j]) dp[tmp ^ j] = true; } int cnt = 0; // フラグの本数をカウント for (int i = 0; i < MAX; i++) if (dp[i]) cnt++; cout << cnt << endl; return 0; } int main() { //clock_t start, end; //start = clock(); yuki0183(); //end = clock(); //printf("%d msec.\n", end - start); return 0; } // 実験用コード (2^N の総当り) int yuki0183_2() { int x; int a[6] = { 1, 1, 4, 5, 1, 4 }; set<int> st; for (int i = 0; i < (1 << 6); i++) { cout << i << " : "; x = 0; for (int b = 0; b < 6; b++) { if (i & (1 << b)) { cout << a[b] << " "; x ^= a[b]; } } cout << " : " << x << endl; st.insert(x); } cout << st.size() << " : " << st << endl; return 0; }
作問者の解説を見たら想定解だったのでよかった.