ARC017に参加しました
ようやく修論発表も無事（？？？）終わり、少し余裕が出来たのでARC017に参加。今回こそはCを解くと意気込んでいました。
A - 素数、コンテスト、素数
N(17≤N≤1,000,000)が与えられるので、Nが素数かどうか判定する。
コピペをやるだけ。
始めsqrt(1,000,000)とか考えてたけど、冷静に考えてO(n)で普通にいけた。
B - 解像度が低い。
要素数 N(1≤N≤300,000)の配列Aと整数K(1≤K≤N) が与えられる。Aの中でK個連続で単調増加になっている部分は何個あるか？
A[i]番目までに単調増加になっている個数seq[i]を覚えておく。A[i]番目とA[i+1]番目を見て、A[i+1]の方が大きかったらその数に1を足し、そうでなかったら1をseq[i+1]とする。あとはK<=seq[i]となる個数を数えれば良い。
ここまでは簡単なのですが、僕の実装方法が悪くてn=1とk=1のコーナーケースが発生しており、2WA。
C - 無駄なものが嫌いな人
大きさ X(1≤X≤109) のナップサックと N(1≤N≤32) 個の品物がある。i 番目の品物の大きさは wi(1≤wi≤5*10^7) である。N 個の品物から、大きさの総和が無駄なくぴったり X となる選び方が何通りあるか？
始め、再帰で枝狩りしまくればいけるかと思ってやったけどさすがに2^32は強く普通にTLE。
終了前10分くらいで2^16ならいけるんじゃ？と半分全列挙を思いつく。
しかし、実装出来る訳もなく終了。
意気込んでいたCは解けず、88位と微妙な順位で終わってしまいました。
コンテスト終了後にCの半分全列挙を実装してみました。
半分全列挙とは全パターンを列挙することができないようなサイズの問題に対し、半分ずつ列挙することで全ての列挙を可能にするアルゴリズムです（from 蟻本）。
今回の場合、2^32は無理ですが、半分ずつ列挙すると2^16 * 2で半分からなる組み合わせが全て列挙でき、あとは片方の要素に対し二分探索を使うことで時間内におさめることが出来ます。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <vector> #include <algorithm> #include <string> #include <map> #include <set> #include <queue> #include <stack> #include <climits> #include <sstream> #include <functional> #include <complex> using namespace std; #define len(array) (sizeof (array) / sizeof *(array)) #define rep(i, s, e) for(int i = s;i < e;i++) #define Rep(i, e) for(int i = 0;i < e;i++) #define rrep(i, e, s) for(int i = e;s <= i;i--) #define Rrep(i, e) for(int i = e;0 <= i;i--) #define vrange(v) v.begin(), v.end() #define vrrange(v) v.rbegin(), v.rend() #define vsort(v) sort(vrange(v)) #define vrsort(v) sort(vrrange(v)) #define arange(a) a, a + len(a) #define asort(a) sort(arange(a)) #define arsort(a, t) sort(arange(a), greater<t>()) #define afill(a, v) fill(arange(a), v) #define afill2(a, v, t) fill((t *)a, (t *)(a + len(a)), v) #define fmax(a, b) (a < b? b : a) #define fmin(a, b) (a > b? b : a) #define fabs(a) (a < 0? -a : a) #define pb push_back #define rg(i, s, t) s <= i && i < t //#define X real() //#define Y imag() //typedef unsigned int ui; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> P; //typedef complex<double> p; const int INF = (int)2e9; const int MOD = (int)1e9 + 7; const double EPS = 1e-10; //const int dx[] = {1, -1, 0, 0, 1, -1, -1, 1}; //const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1}; //const int weight[] = {0,1,10,100,1000,10000,100000,1000000,10000000}; //priority_queue< int, vector<int>, greater<int> > q; // #define MAX_N 1000 void doIt(){ int n, x, w[33]; cin >> n >> x; Rep(i, n){ cin >> w[i]; } // sort(w, w+n, greater<int>()); map<int, int> grpA[2], grpB[2]; int prev = 0, now = 1, ptr; grpA[prev][0]++; map<int, int>::iterator it; Rep(i, n/2+1){ it = grpA[prev].begin(); grpA[now].clear(); while(it != grpA[prev].end()){ grpA[now][(*it).first + w[i]] += (*it).second; grpA[now][(*it).first] += (*it).second; it++; } prev = 1 - prev; now = 1 - now; } ptr = prev; prev = 0; now = 1; grpB[prev][0]++; rep(i, n/2+1, n){ it = grpB[prev].begin(); grpB[now].clear(); while(it != grpB[prev].end()){ grpB[now][(*it).first + w[i]] += (*it).second; grpB[now][(*it).first] += (*it).second; it++; } prev = 1 - prev; now = 1 - now; } it = grpA[ptr].begin(); ll ans = 0; while(it != grpA[ptr].end()){ // printf("itA = %d\n", (*it).first); if(grpB[prev].count(x - (*it).first)) ans += (*it).second * grpB[prev][x - (*it).first]; it++; } cout << ans << endl; } int main() { doIt(); return 0; }
上位の方々のコードを参考に実装。
今まで知らなかったんですが、map
