AtCoder Beginner Contest 181, D : Hachi

問題文

　https://atcoder.jp/contests/abc181/tasks/abc181_d

問題概要

　数字からなる列 $S$ が与えられる．$S$ を並べ替えて作れる文字列を整数として読んだとき，$8$ の倍数を作ることはできるか？

制約

• $1 \leq |S| \leq 2 \times 10^5$

解法

　$8$ の倍数判定は，ぐぐるなどして https://mathtrain.jp/baisuhantei などを見ると下 3 桁が $8$ の倍数であるかどうかを調べればよいことが分かります．3 桁程度ならば全通り試すことができます．よって，

• $\mathit{ dfs }( i, j ) := \text{$i$ 桁決めて $j$ を作れるか？}$

といったような関数で DFS をすることで探索することができます．この DFS を実装するにあたっては，各数字がいくつあるかを数えておいて，残っているならば使う，といったことをする必要があります．
　計算量としては，各数字がいくつ出現するかを数えるパート（あるいは，入力を読むこと自体にかかる時間）が一番重くて，$\Theta( N )$ 時間となります．

コード

int L;
int counts[ 16 ];

bool dfs( const int i = 0, const int x = 0 )
{
	if ( i == min( L, 3 ) )
	{
		return x % 8 == 0;
	}

	bool res = false;
	REP( j, 10 )
	{
		if ( counts[j] )
		{
			--counts[j];
			res |= dfs( i + 1, x * 10 + j );
			++counts[j];
		}
	}
	return res;
}

int main()
{
	IN( string, S );
	L = SZ( S );

	for_each( ALL( S ), [&]( const char c ){ ++counts[ c - '0' ]; } );

	cout << ( dfs() ? "Yes" : "No" ) << endl;

	return 0;
}