AGC 008 C - Tetromino Tiling - ykmakuのブログ

問題

解法

まずT,S,Z型は使えません.
また，O型はそれ単体で横の長さが2の長方形になので必ず求めたい長方形に含めることができます.
結局I,J,L型の組み合わせを考えればいいです.

同じ型を２つ組み合わせることで横の長さが4の長方形ができます.(それぞれII型，JJ型，LL型と呼ぶことにします.)
これとは別にI,J,L型を１個ずつ使うと横の長さが6の長方形ができます.
この長方形をIJL型と呼ぶことにするとIJL型は高々1個だけ使うことにして良いです.
なぜならIJL型が2つあると横の長さの合計は12ですが，これはI,J,Lを2個ずつ使った場合の横の長さの合計に等しいので， IJL型2個はII型JJ型LL型の組1つ分と同一視できるからです.

以上から，IJL型を使うか使わないかで場合分けをして横の長さが大きい方を出力すれば良いです.

感想

そんなに難しくないはずなんだけど，J型とL型を組み合わせて長方形を作れると勘違いしたせいでWAを量産してしまった.
こういうアホなミスをなくしていきたい.

#include <iostream>


using namespace std;

typedef long long int ll;


int main()
{
	ll i,o,t,j,l,s,z;
	cin>>i>>o>>t>>j>>l>>s>>z;

	ll ans = 0;
	ans += 2*o;

	ll ijl = min(min(i,j),l);
	ll res = 0;
	if(ijl>0){ // ijlを１個使う
		res += 6 + ((i-1)/2)*4 + ((j-1)/2)*4 + ((l-1)/2)*4;
	}

	ans += max(res,(i/2)*4 + (j/2)*4 + (l/2)*4);
	cout << ans/2 << endl;

	return 0;
}