AtCoder Grand Contest 008 C - Tetromino Tiling
問題概要
I,O,T,J,L,S,Zの7つの型のブロック(テトロミノ)を入力された個数の範囲内で組み合わせて縦2マス、横2Kマスの長方形を作る時のKの最大値を求める。
解法
上で言った6つの型のテトロミノを以下そのアルファベット名で呼称する。
まず、作成する長方形の縦は2マスで固定であることに留意すると、T,S,Zの3つの型のいずれかを1つでも使用すると目的の長方形は作成不可能であることが分かるため、今回注目するのは残りの4つの型となる。
次に、同じく縦が2マスという条件から、全てのOは使用可能であることが分かる。
後は、残ったI,J,Lについての場合分けをする。図を載せ説明するのが面倒だと思っていたらAtCoderの解説はやっぱりすごいので僕の思っていた通りの図が載っていた。解説を見ると分かるが、この3つの型を使用してできる長方形は最終的に4種類に限定される。
よって、I,J,Lがそれぞれ何個あるかによって場合分けをしてあげて、AC。