torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder SRM 616, Division 2, Level 2 : ColorfulCoinsEasy

問題概要

 ある国の通貨体系では、コインは次の condition を満たす。

  • コインの価値は相異なる
  • 価値 1 のコインが存在する
  • 任意の二種類のコインについて、片方の価値は他方のそれを割り切る

 更に、コインはその見た目に関して次の condition を満たす。

  • 同じ種類のコインは同じ色である
  • 違う種類のコインは異なる色である

 今、無限の残高をもつクレジットカードを持っていて、ATM を用いて任意の金額をコインを取り出すことができる。ただし、ATM はコインの枚数の総和が最も少なくなるようにコインを排出する。ATM を一回だけ利用して、全て種類のコインの色を特定することができるかどうかを求めよ。

解法

 コインの種類を N 表記します。
 まず、全ての種類のコインの色を特定できる⇔全てのコインについて、1 以上かつ相異なる枚数で取り出すことができる です。
 更に、ATM のコインの排出枚数の内訳は、価値の高いコインから順に使えるだけ使う、という手順で決定できます。残り金額が p で、今着目しているコインの価値が p のとき、使える枚数は p / v で、その後残る金額 p' は p mod v です。一種類のコインついて除算だけでシミュレートできるので、引き出す金額を決めたとき、一回あたり O( N ) でシミュレートできます。
 金額を決めたときの支払いの内訳をある程度高速に求められるので、引き出し金額を複数試して条件を満たすものが存在するかを調べることができます。そのような金額を存在すれば "Possible" を返し、ある程度大きい値まで試しても見つからなければ "Impossible" を返すようにすると解くことができます。*1

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

class ColorfulCoinsEasy
{
public:
	string isPossible(vector <int> values)
	{
		reverse( ALL( values ) );

		REP( i, 0, 15 * 20000 + 1 )
		{
			if ( ok( values, i ) )
			{
				return "Possible";
			}
		}
		return "Impossible";
	}

	bool ok( const VI &values, int p )
	{
		const int N = values.size();

		VI counts( N );
		REP( i, 0, N )
		{
			counts[i] += p / values[i];
			p %= values[i];
		}

		return 0 < *min_element( ALL( counts ) ) && set<int>( ALL( counts ) ).size() == N;
	}
};

*1:解の上界がよく分からなかったので適当に決めてしまいました