torus711 のアレ

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

TopCoder SRM 570, Division 2, Level 1 : Chopsticks

概要

長さの異なる N 本の箸がある。
友人を招待したいが、各友人には同じ長さの箸のペアを一膳として箸を提供したい。
最大で何人の友人を招待することができるか求めよ。

解法

各長さについてその数を数え、2 で割った(端数切捨て)結果の総和をとります。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ITER( c ) __typeof( (c).begin() )
#define IREP( c, it ) for ( ITER(c) it = c.begin(); it != c.end(); ++it )

#define fst first
#define snd second

class Chopsticks
{
public:
	int getmax( vector <int> length )
	{
		map<int,int> count;

		REP( i, 0, length.size() )
		{
			count[ length[i] ]++;
		}

		int res = 0;

		IREP( count, it )
		{
			res += (*it).snd / 2;
		}

		return res;
	}
};