AtCoder ARC #112 : F - Die Siedler

modを取るところまでは行けたのだが。
https://atcoder.jp/contests/arc112/tasks/arc112_f

問題

N種類のカードがあり、それぞれ何枚かを持っている。
ここで、以下の処理を行える。

• M種類のカードセットがあり、いずれかを購入して全カードを手持ちに加える
• i番目のカードがi*2枚以上あるとき、i%N+1番目のカード1枚と交換する

最終的な手持ちカード枚数を最小何枚まで減らせるか。

解法

後者の手順は、行える時は常に行うのが良い。
そうすると、i番目のカードは(i*2)枚以下となる。

下からi桁目が(2*i)進数であるような数の処理系において、各桁にカード枚数を当てた数を考えると、この数は手持ちカードに1対1で対応する。
また、M=2^N*N!-1とすると、N番目のカード2N枚を1番目のカードに交換する処理は、数にMを加える処理とみなせる。

そうすると、初期状態に対応する数をC、各カードセットjに対応する数をV[j]とすると、到達可能な数は
(C + k * GCD(M, V[0], V[1], ...)) mod (M+1)
となる。あとは、この形で到達できる数のうち、対応するカード枚数が最小となるものを選ぼう。

Mの約数は割と小さいか大きいかのいずれかなので、GCDも小さいか大きい。

• GCDが大きいとき、M/GCDが小さいとkの取りえる値は小さいので、kを総当たりする
• GCDが小さいとき、カードの持ち方をBFSで総当たりすれば、すぐにC = D (mod GCD)となるような数Dを満たすカードの持ち方に到達する。

int N,M;
ll A[17];

int hoge(ll v) {
	int ret=0;
	for(int i=1;i<=N;i++) {
		ret+=v%(i*2);
		v/=(i*2);
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	A[0]=1;
	for(i=1;i<=16;i++) A[i]=A[i-1]*(2*i);
	
	cin>>N>>M;
	ll v=0;
	FOR(i,N) {
		cin>>x;
		v+=x*A[i];
	}
	ll g=A[N]-1;
	
	FOR(y,M) {
		ll w=0;
		FOR(x,N) {
			cin>>i;
			w+=i*A[x];
		}
		g=__gcd(g,w);
	}
	
	if(A[N]/g<=10000000) {
		int ret=10101010;
		FOR(i,A[N]/g+2) {
			ret=min(ret,hoge(v));
			v+=g;
			if(v>=A[N]) v-=A[N]-1;
		}
		cout<<ret<<endl;
	}
	else {
		deque<pair<ll,int>> D;
		for(i=1;i<=N;i++) D.push_back({A[i-1],100+i});
		while(D.size()) {
			ll cur=D.front().first;
			int nex=D.front().second;
			D.pop_front();
			if(cur%g==v%g) {
				cout<<nex/100<<endl;
				return;
			}
			for(i=nex%100;i<=N;i++) D.push_back({cur+A[i-1],(nex/100+1)*100+i});
			
		}
		
	}
	
	
}

まとめ

後半パートに考えが至らず。
タイトルはボードゲームかな？