torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 597, Division 2, Level 1 : LittleElephantAndDouble

概要

N 項からなる数列が与えられる。
数列の任意の要素を二倍する操作を任意回できる。
全ての要素を同一にすることができるか?

解法

二進数で考えると、二倍する操作は 1 bit の左シフトと言い換えることができます。
二進法で扱うと都合が良いので、全て二進数で考えます。

問題は「列中の各要素を何度か左シフトして、全ての要素を等しくできるか?」と言い換えられます。
左シフトでは、立っている bit の数と相対的な位置関係が変わりません。
従って、二つの値を等しくできるならば、次のことが言えます。

  • 長さの等しい連続する部分列であって、立っている bit を全て含むものの内、一致するものがある

このような bit 列が含まれるとき、より右に含む方を適当な回数左シフトすることで、他方を作れます
そのような列があるかどうかは、末尾の 0 を全て消去することで整数での同値性と一致します。

まとめると、全ての要素をその末尾にある 0 の個数だけ右シフトして、全ての要素が等しいかどうかを調べればよいということになります。

コード

#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()

class LittleElephantAndDouble
{
public:
	string getAnswer( vector <int> A )
	{
		FOR( a, A )
		{
			a >>= __builtin_ctz( a );
		}
		return set<int>( ALL( A ) ).size() == 1 ? "YES" : "NO";
	}
};