Google Code Jam 2014, Round 1B, B : New Lottery Game

問題文

http://code.google.com/codejam/contest/2994486/dashboard#s=p1

問題概要

　正整数 A, B, K が与えられる。a < A, b < B, a & b < K なる a, b の順序対の個数を求めよ。*1
　

解法

　解の存在範囲が大きいので、愚直に全列挙することはできません。より効率的な解法を考えます
　まず、a < A を満たす a の総数だけ考えてみましょう。上位の桁からそこに何を入れるかを順に決めていくとします。このとき、ある桁に入れる値の自由度は過去の選択に依存していて、

• 過去に対応する A の桁の値未満の値を入れたことがある -> なんでもよい
• それ以外のとき -> 対応する A の桁の値以下の値しか入れられない

となります。この情報だけがあればよいので、次のような動的計画法

• dp[ i 桁決めた ][ A 未満が確定した ] := 総数

を考えることができます。b < B なる b の総数についても同様の DP が考えられます。
　残るは K に関する制約ですが、これも考え方は同じです。a & b による値が K 未満となればよいので、a, b の二進表記での該当する桁に入れる値（ 0 or 1 ) を全部試して、K の対応する桁の値と比較します。先程の a, b を決める DP も二進表記に書き換えられるので、全体では次のような DP になります。

• dp[ （二進表記で）i 桁決めた ][ a < A が確定したか ][ b < B が確定したか ][ a & b < K が確定したか ] := 総数

　dp[ i ][ j ][ k ][ l ] かの遷移は a, b の該当する桁に何を入れるかを全て試すので 2 * 2 = 4 通りで、それぞれの値を c, d とし、 A, B, K の対応する桁の値を ta, tb, tk とすると

• dp[ i + 1 ][ j || c < ta ][ k || d < tb ][ l || ( c & d ) < tk ] を更新

となります。
　求めたいのは「ほげほげ未満」の制約を満たすものの個数なので、表を埋め終わった後の dp[ 総桁数 ][ 1 ][ 1 ][ 1 ] に答えが求まっています。総桁数は入力を二進表記できればよいので 以上の整数ですが、上位に桁が余っても問題無いので適当に 32 とかにしておけば大丈夫です。

コード

using LL = long long;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define AALL( a, t ) (t*)a, (t*)a + sizeof( a ) / sizeof( t )

constexpr int L = 32;
LL dp[ L + 1 ][2][2][2];

LL solve( const int A, const int B, const int K )
{
	fill( AALL( dp, LL ), 0 );
	dp[0][0][0][0] = 1;

	REP( i, 0, L )
	{
		const int idx = L - 1 - i;
		const int ta = ( A >> idx ) & 1, tb = ( B >> idx ) & 1, tk = ( K >> idx ) & 1;

		REP( j, 0, 2 )
		{
			REP( k, 0, 2 )
			{
				REP( l, 0, 2 )
				{
					REP( a, 0, 2 )
					{
						REP( b, 0, 2 )
						{
							if ( !j && ta < a || !k && tb < b || !l && tk < ( a & b ) )
							{
								continue;
							}

							dp[ i + 1 ][ j || a < ta ][ k || b < tb ][ l || ( a & b ) < tk ] += dp[i][j][k][l];
						}
					}
				}
			}
		}
	}

	return dp[L][1][1][1];
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int t;
	cin >> t;

	REP( i, 0, t )
	{
		int a, b, k;
		cin >> a >> b >> k;

		cout << "Case #" << i + 1 << ": " << solve( a, b, k ) << endl;
	}

	return 0;
}

*1:& は bitwise and を表す