TopCoder SRM318 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文について説明する。

Joshはいくつかの1インチの棒を見つけた。彼はこの棒を辺とする長方形を作成し、しかもできるだけ面積を大きくしたいと思っている。ただ、棒をくっつけるのはOKだが、棒を折って短い棒を作ることは認めていない。例えば11本の棒があったとき、2*3の長方形を作成するのに10本の棒を使うが、このとき面積が最大になる。Nという棒の本数が与えられたとき、その本数で作成できる長方形の面積の最大値を求めよ。

私の解答はこちら。

public class BiggestRectangleEasy {

 public int findArea(int N) {
  int n = N/2;
  boolean isEven = n%2 == 0;
  if( isEven ){
   return n/2*n/2;
  }else{
   return (n/2)*(n/2+1);
  }
 }

}

得点は237.46/250、中央値もほぼ同じ点数。辺の長さの総和が一定のとき、長方形の面積が最大というのは、縦横の本数が同じになるという性質を利用した(a+bが一定の時、abの最大値を求める問題と同じになる)。次は、縦横の辺の長さの求め方であるが、棒の本数をいったんN以下で最大の偶数に直し、それを2で割る。さらにその値が2で割り切れるか否かで場合分けしている。上の例で考えてみると、11は10になり、縦横1辺ずつの総和は5、したがって、これを5/2=2.5の前後の整数である2、3に割り振ればよいと考えていることになる。点数は高くないが、数学的性質を用いて綺麗に解くことができる問題と思います。