AtCoder Beginner Contest 182, C : To 3

問題文

　https://atcoder.jp/contests/abc182/tasks/abc182_c

問題概要

　各桁に $0$ が出現しない正整数 $N$ が与えられる．$N$ の桁を（全部ではなく）削除して得られる整数で $3$ の倍数を作るとき，削除する桁の最小数を求めよ．

制約

　$1 \leq N \leq 10^{ 18 }$

解法

　桁数が高々 $18$ ということで，これは $2$ の肩に載せることができます．よって，消す桁の組合せをすべて試すことができ，消し方あたり $O( \text{桁数} )$ で $3$ の倍数かどうかを判定することができます．
　整数 $n$ の桁数というのは $O( \log_{ 10 } n )$ なので，計算量としては $O( 2^{ \log N } \log N )$ 時間となります．

コード

constexpr auto INF = LIM<>::max() / 2;

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

	int res = -1;
	REP( s, 1, 1 << L )
	{
		int dsum = 0;
		REP( i, L )
		{
			if ( s & 1 << i )
			{
				dsum += S[i] - '0';
			}
		}
		if ( dsum % 3 == 0 )
		{
			chmax( res, __builtin_popcount( s ) );
		}
	}

	cout << ( res == -1 ? -1 : L - res ) << endl;

	return 0;
}