kmjp's blog

競技プログラミング参加記です

TopCoder SRM 829 : Div1 Hard UpdownNumbers

方針はたちやすい。
https://community.topcoder.com/stat?c=problem_statement&pm=17591

問題

D桁の正整数のうち、S次updown数であるものはいくつあるか。
ある整数がS次updown数であるとは、S次up数でもありS字down数でもあることを意味する。
S次up数とは、D桁の整数からS桁抜き出したとき、前から順に狭義単調増加になる部分があることを意味する。
S次up数とは同様に狭義単調減少となる部分があることを意味する。

解法

LIS/LDSを作るときに、「k要素のLISを作れるときにk個目の要素の最小値」を管理するような数列を作る。
狭義単調増加の場合、この数列は各要素distinctであるはずである。
そのため、これをbitmaskで表現すれば、LIS側で10bit、LDS側で10bit使えば、上記配列をLIS/LDS双方管理できる。
あとは、D桁分0~9のそれぞれを選んだ時にどうなるかを総当たりしていけばよい。

const ll mo=1000000007;

ll from[1<<10][1<<10];
ll to[1<<10][1<<10];

int Utable[1<<10][10];
int Dtable[1<<10][10];

class UpdownNumbers {
	public:
	int count(int D, int S) {
		
		ZERO(Utable);
		ZERO(Dtable);
		int m1,m2;
		int mask,i,j;
		FOR(mask,1<<10) {
			FOR(i,10) {
				for(j=i;j<10;j++) if(mask&(1<<j)) break;
				if(j==10) Utable[mask][i]=mask^(1<<i);
				else Utable[mask][i]=mask^(1<<j)^(1<<i);
				
				for(j=i;j>=0;j--) if(mask&(1<<j)) break;
				if(j==-1) Dtable[mask][i]=mask^(1<<i);
				else Dtable[mask][i]=mask^(1<<j)^(1<<i);
			}
		}
		
		ZERO(from);
		from[0][0]=1;
		int first=1;
		while(D--) {
			ZERO(to);
			FOR(m1,1<<10) FOR(m2,1<<10) if(from[m1][m2]) {
				FOR(i,10) {
					if(first&&i==0) continue;
					(to[Utable[m1][i]][Dtable[m2][i]]+=from[m1][m2])%=mo;
				}
			}
			first=0;
			swap(from,to);
		}
		ll ret=0;
		FOR(m1,1<<10) FOR(m2,1<<10) if(from[m1][m2]) {
			if(__builtin_popcount(m1)>=S&&__builtin_popcount(m2)>=S) 
				ret+=from[m1][m2];
			}
		}
		
		return ret%mo;
	}
}

まとめ

方針はすぐたってもコード量がちょっと膨らんで面倒だった。