読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

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

TopCoder, SRM 627, Division 2, Level 1 : ManySquares

問題概要

 複数の棒があり、i 番の棒の長さは sticks_i である。これらの棒を使ってできるだけ多くの正方形を作りたい。ただし、1 つの辺には丁度 1 本の棒を使わなければならない。作ることができる正方形の最大数を求めよ。

解法

 同じ長さの棒を 4 本組み合わせることで、一つの正方形を構成することができます。従って、sticks の要素になりうる各値について、sticks に現れる回数を数え、4 で整数除算した値を足し合わせることで全体の答えが求まります。

コード

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

class ManySquares
{
public:
	int howManySquares( vector <int> sticks )
	{
		int res = 0;
		REP( i, 0, 1000 )
		{
			res += count( ALL( sticks ), i + 1 ) / 4;
		}
		return res;
	}
};