Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2454-776c18a3
この記事にトラックバックする(FC2ブログユーザー)

SRM599 DIV1 MEDIUM - FindPolygons (この記事を編集する[管理者用])

Source

TopCoder SRM599 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

各頂点が格子上の単純な多角形のうち,周の長さが $L$ (整数)のもので,
 (1) 頂点数が最も小さいもの
 (2) その中で,最も長い辺と最も短い辺の長さの差が最も小さいもの
を考える.
最も長い辺と最も短い辺の長さの差を求める問題.
ただし,そのような多角形が存在しないならそれを指摘する.
$1 \leq L \leq 5000$

解法

まず,$L$ が奇数ならそのような多角形は存在しない.
なぜなら, $a^2 + b^2 = c^2$ を満たす整数 $a,b,c$ を考えると,奇数の数は $0$ か $2$ 個であるから,一周回って戻ってきて,周長が奇数になることはない.
また,$L \geq 4$ かつ $L$ が偶数なら,四角形は作れて,$L$ が $4$ の倍数なら正方形,そうでないなら,縦の長さが $1$ だけ長い長方形が作れる.
よって,三角形が作れるかどうかを探索し,最も長い辺と短い辺の長さの差が小さい三角形を見つける問題になる.
そこそこうまく探索すると間に合う.
$L$ が $5000$ 通りしかないので,間に合わない場合は,答えを埋め込んでも良い.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int GCD(int a,int b){int r; while(a){r=b; b=a; a=r%a;} return b;}

class FindPolygons {
public:
double minimumPolygon(int L) {
  int i, j, k;
  int a, b, c, fin;
  int d[3], x[3], y[3];
  int res = 1000000000;
  vector<int> dx[5001], dy[5001];
  map<int,int> mp;

  if(L==2 || L%2) return -1;

  REP(i,1,5001) mp[i*i] = i;

  REP(i,1,5001){
    dx[i].push_back(i); dy[i].push_back(0);
    dx[i].push_back(0); dy[i].push_back(i);
  }
  
  REP(i,1,5001){
    REP(j,i+1,5001){
      k = i*i + j*j;
      if(mp.count(k)==0) continue;
      k = mp[k];
      dx[k].push_back(i); dy[k].push_back(j);
      dx[k].push_back(j); dy[k].push_back(i);
    }
  }

  REP(i,1,L) REP(j,i,L){
    k = L-i-j;
    if(k < j) continue;
    if(res <= k-i) continue;

    fin = 0;

    rep(a,dx[i].size()) if(!fin) rep(b,dx[j].size()) if(!fin) rep(c,dx[k].size()) if(!fin){
      if(dx[i][a] != dx[j][b] + dx[k][c] && dx[j][b] != dx[i][a] + dx[k][c] && dx[k][c] != dx[i][a] + dx[j][b]) continue;
      if(dy[i][a] != dy[j][b] + dy[k][c] && dy[j][b] != dy[i][a] + dy[k][c] && dy[k][c] != dy[i][a] + dy[j][b]) continue;

      d[0] = GCD(dx[i][a], dy[i][a]);
      d[1] = GCD(dx[j][b], dy[j][b]);
      d[2] = GCD(dx[k][c], dy[k][c]);
      x[0] = dx[i][a] / d[0];
      y[0] = dy[i][a] / d[0];
      x[1] = dx[j][b] / d[1];
      y[1] = dy[j][b] / d[1];
      x[2] = dx[k][c] / d[2];
      y[2] = dy[k][c] / d[2];
      if(x[0]==x[1] && x[0]==x[2] && y[0]==y[1] && y[0]==y[2]) continue;

      res = min(res, k-i);
      fin = 1;
    }
  }
  
  if(res >= 1000000000){
    if(L%4) res = 1;
    else    res = 0;
  }
  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2454-776c18a3
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。