Hatena::Grouptopcoder

shnyaの参戦記録

2011-05-29練習

SRM 433 Div1 Medium 02:48  [http://www.topcoder.com/stat?c=problem_statement&pm=10191&rd=13695:title=SRM 433 Div1 Medium] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10191&rd=13695:title=SRM 433 Div1 Medium] - shnyaの参戦記録

あれ?簡単じゃね?とか思ってやったら数が合わずに断念。

斜めの場合を考慮できてなかった模様。

結局下記URLを読んで解き方を理解しました。

http://d.hatena.ne.jp/ogiekako/20100103/p3

http://topcoder.g.hatena.ne.jp/wata_orz/20090122/1232607135

自分で解いたわけじゃないけど、忘れないようにはっておきます。

class SettingTents {
public:
  int countSites( int N, int M ) {
    int res = 0;
    for(int i = 1; i <= max(N,M); i++){
      for(int j = 0; j < i; j++){
        res += max(0, (N - i + 1)) * max(0, (M - i + 1));
        for(int k = 1; 2 * k < i; k++){
          if((i - 2 * j) * k % i == 0){
            int h = max(i-2*k,abs(i-2*j));
            if(h<= N && i <= M) res += (N-h+1)*(M-i+1);
            if(h<= M && i <= N) res += (M-h+1)*(N-i+1);
          }
        }
      }
    }
    return res;
  }
};