SRM 245 DIV1 Hard SandTimers

問題 Editorial

問題

それぞれ一定の時間だけを測れる砂時計timersが与えられる。
砂時計は最初か他のどれかの砂時計の砂が落ち終わった時にのみひっくり返すことができる。
砂時計をひっくり返すタイミングで、"Start"や"Stop"と言うことができて、"Start"と言った時から"Stop"と言うまでで時間を測ることができる。
ただし、"Stop"と言うのは最初からmaxTime以内でなければいけない。
[1..maxInterval]の時間の中で測ることができない時間を返せ

• 1 <= |timers| <= 3
• 1 <= timers[i] <= 20
• 1 <= maxInterval <= maxTime <= 360

解答

なんか適当にやったら通った。
まず(ある時間を * 砂時計の各残り砂)の360*20^3のDPで、その状態からできるかが判定できる。
適当にBFSして最初から到達可能な砂の状態を列挙し、それぞれに対してそれStopの時間を全部DPで判定する。
計算時間があぶないような気もするがほんの少し定数倍高速化したら最悪1.938sで通った

コード

#include <string>
#include <vector>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define pb(x) push_back(x)
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef vector<int> vi;

int dp[361][22][22][22];
struct SandTimers {
	vi timers;
	int rec(int t, int s1, int s2, int s3) {
		if(dp[t][s1+1][s2+1][s3+1] != -1) return dp[t][s1+1][s2+1][s3+1];
		int r = 0;
		if(t == 0) {
			r = s1 == 0 || s2 == 0 || s3 == 0;
		}else {
			if(s1 == 0 || s2 == 0 || s3 == 0) {
				rep(i, 8) {
					r |= rec(t-1,
						(((i >> 0) & 1) && timers.size() >= 1 ? timers[0] - max(0, s1) : max(0, s1)) - 1,
						(((i >> 1) & 1) && timers.size() >= 2 ? timers[1] - max(0, s2) : max(0, s2)) - 1,
						(((i >> 2) & 1) && timers.size() >= 3 ? timers[2] - max(0, s3) : max(0, s3)) - 1);
				}
			}
			r |= rec(t-1, max(0, s1)-1, max(0, s2)-1, max(0, s3)-1);
		}
		return dp[t][s1+1][s2+1][s3+1] = r;
	}
	vector <int> badIntervals(vector <int> timers_, int maxInterval, int maxTime) {
		timers = timers_;
		mset(dp, -1);
		vi ok(maxInterval+1);
		vi q, next;
		next.pb(484 * 1 + 22 * 1 + 1);
		int n = timers.size();
		rep(t, maxTime) {
			q.swap(next);
			static bool chk[10648];
			mset(chk, 0);
			while(!q.empty()) {
				int st = q.back(); q.pop_back();
				int s1 = st / 484 % 22 - 1, s2 = st / 22 % 22 - 1, s3 = st % 22 - 1;
				if(s1 == 0 || s2 == 0 || s3 == 0) {
					rer(i, 1, maxInterval)
						if(t + i <= maxTime && rec(i, s1, s2, s3)) ok[i] = 1;
					rep(i, 8) {
						int ns =
							((i & 1) && n >= 1 ? timers[0] - max(0, s1) : max(0, s1)) * 484 +
							((i & 2) && n >= 2 ? timers[1] - max(0, s2) : max(0, s2)) * 22 +
							((i & 4) && n >= 3 ? timers[2] - max(0, s3) : max(0, s3)) * 1;
						if(!chk[ns]) chk[ns] = 1, next.pb(ns);
					}
				}
				{
					int ns = max(0, s1) * 484 + max(0, s2) * 22 + max(0, s3) * 1;
					if(!chk[ns]) chk[ns] = 1, next.pb(ns);
				}
			}
		}
		vi r;
		rer(i, 1, maxInterval) if(!ok[i]) r.pb(i);
		return r;
	}
};