問題概要
複数の棒があり、 番の棒の長さは である。これらの棒を使ってできるだけ多くの正方形を作りたい。ただし、1 つの辺には丁度 1 本の棒を使わなければならない。作ることができる正方形の最大数を求めよ。
解法
同じ長さの棒を 4 本組み合わせることで、一つの正方形を構成することができます。従って、 の要素になりうる各値について、 に現れる回数を数え、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; } };