SRM564 Div1 Easy "KnightCircuit2"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10968
訳
チェスのナイトという駒は一方向へ1マス、もう一方向へ2マス分ジャンプするように動く。
正式には、ナイトがマス(x, y)にあるとすると、次の8個のマスへ移動できる。
(x+1, y+2), (x+1, y-2), (x-1, y+2), (x-1, y-2),
(x+2, y+1), (x+2, y-1), (x-2, y+1), (x-2, y-1)
当然ナイトがボードの角にあったときなど、
上記のうちいくつかのマスはボードからはみ出している可能性がある。
そのようなマスへはジャンプする事はできない。
knight-circuit(ナイトの回路) とはスタートとゴールが同じマスの
チェスボードのマスの配列である。
knight-circuitの隣り合うマスは(a, b)-ナイトが一回のジャンプで
移動できるものでなくてはならない。
knight-circuitは各セルを好きな回数、訪れてもよい。
knight-circuitのサイズとは、そこに含まれる異なるセルの数である。
あなたは長方形のチェスボードの幅wと高さhが与えられる。
与えられたボードから得られる、knight-circuitのサイズの最大値を返せ。
knight-circuitのスタートのマスは自由に選べるものとする。
制約
1 <= w, h <= 45000
考えた事
Div2 Hardと違って、ナイトの移動力が(1, 2)と固定されているため、そこを利用して考えてみる。
まずマスのw, hの小さいほうをa、大きいほうをbとすると、aが1である場合、ナイトは全く移動できない。aが2である場合、ナイトは前に前に進む事しか出来ない。aが3である場合、bが3のとき以外は全てのマスを訪れる事ができる。
・・・ま、Editorialsをチラ見しちゃったからでけた
ソースコード
class KnightCircuit2 { public: int maxSize(int w, int h){ if( w > h ) swap( w, h ); if( w == 1 ) return 1; if( w == 2 ) return (h + 1) / 2; if( w == 3 && h == 3) return 8; return w * h; } };