Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

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

問題概要

R*Cのチェス盤を考える.(R, Cは10^9以下)
ハイパーナイトというコマは,
 上下のどちらかにaだけ,左右のどちらかにbだけ動く
 上下のどちらかにbだけ,左右のどちらかにaだけ動く
という8通りの動き方ができる.
ただし,盤面の外へは移動できない.
そこから1ターンでk通りの移動できるマスは何個あるかを求める問題.
aとbは等しくない.
2*max(a,b)はmin(R,C)より小さい.

解法

どの移動ができるかどうかで,盤面は25通りの場所に分類される.
それぞれ何通り移動できるか,それに含まれるマスの数はいくつかを調べる.

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

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

#define ll long long

class HyperKnight {
public:
ll countCells(ll a, ll b, ll x, ll y, ll k) {
  ll i, j, area, can;
  ll d, ni, nj;
  ll di[8] = {-2,-2,-1,-1,1,1,2,2};
  ll dj[8] = {-1,1,-2,2,-2,2,-1,1};
  ll wX[5], wY[5];
  ll res[10] = {};

  if(a > b) swap(a, b);

  wX[0] = wX[4] = wY[0] = wY[4] = a;
  wX[1] = wX[3] = wY[1] = wY[3] = b-a;
  wX[2] = x - 2*b;
  wY[2] = y - 2*b;

  rep(i,5) rep(j,5){
    area = wX[i] * wY[j];
    can = 0;
    rep(d,8){
      ni = i + di[d];
      nj = j + dj[d];
      if(ni < 0 || nj < 0 || ni >= 5 || nj >= 5) continue;
      can++;
    }
    res[can] += area;
  }

  return res[k];
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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