Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM526 DIV1 EASY/DIV2 MEDIUM - DucksAlignment (この記事を編集する[管理者用])

Source

TopCoder SRM526 DIV1 EASY (250pt)
TopCoder SRM526 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

50*50以下の盤面に,何匹かアヒルがいる.
各行には高々1匹のアヒルしかおらず,各列にも高々1匹のアヒルしかいない.
1回の手順で,1匹のアヒルを上下左右に1マス動かすことができる.
縦か横に,すべてのアヒルを連続するように並べるための最小手数を求める問題.

解法

縦に並べるか,横に並べるか,両方試せばよいが,実は各行各列に1匹しかいないことから,片方だけでいいことがわかる.
x座標y座標別々に考えて,一致させるには中央値に移動すればよく,連続させるには,中央値を中心になるように連続させれば良い.

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 ab(int x){if(x<0) return -x; return x;}

class DucksAlignment {
public:
int minimumTime(vector <string> in) {
  int i, j;
  int x, y;
  int px[100], py[100], n = 0;
  int res = 0;

  x = in.size();
  y = in[0].size();
  rep(i,x) rep(j,y) if(in[i][j]=='o') px[n] = i, py[n] = j, n++;

  sort(px, px+n);
  sort(py, py+n);
  
  rep(i,n) res += ab(px[i] - px[n/2]);
  rep(i,n) res += ab(py[i] - (py[n/2] - n/2 + i));

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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