Entries

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

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

SRM284 DIV2 HARD - SnakeCount (この記事を編集する[管理者用])

Source

TopCoder SRM284 DIV2 HARD (1000pt)
Problem Statement

問題概要

蛇は,長さ3マス以上20マス以下の,4方向で隣接した一本の線.
自分と斜め方向に隣接しているのは良いか,他の蛇っぽいのと斜め方向で隣接しているのは蛇ではない.
蛇の数は幾つか.
盤面は50*50以下.

解法

実装問題.問題文をちゃんと読んで,その通りに実装するのみ.

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 dx[8]={1,-1,0,0,1,-1,1,-1};
int dy[8]={0,0,1,-1,1,-1,-1,1};

int x,y;
int mp[60][60];

// 上下左右で繋がっているfromが書かれたマスを,全部toに置き換えます
void nul(int i,int j,int from,int to){
  int k;
  if(mp[i][j]!=from) return;
  mp[i][j]=to;
  rep(k,4) nul(i+dx[k],j+dy[k],from,to);
}

class SnakeCount {
public:
int number(vector <string> image) {
  int i,j,k,c,mx;
  int head[5000], dame[5000], num[5000];
  int res;

  // 0の枠をつけるため,縦と横のサイズを+2します
  x=image.size()+2; y=image[0].size()+2;
  rep(i,x) rep(j,y) mp[i][j]=0;
  rep(i,x-2) rep(j,y-2) if(image[i][j]=='1') mp[i+1][j+1]=1;

  // 上下左右の身で移動できる区間にユニークな数字を割り振ります (3からなのはてきとーです)
  // 00101110    00304440
  // 00101010 -> 00304040
  // 01001001    05004006
  mx=3;
  rep(i,x) rep(j,y) if(mp[i][j]==1) nul(i,j,1,mx++);

  // head[i]は 蛇i の 頭(尻尾)候補の数 (4方向で,自分と隣接しているのが1マスしかないものの数)
  // dame[i]は 蛇i は 2つ叉に分かれていたり,他の蛇にくっついているとtrue
  // num[i] は 蛇i の 長さ
  rep(i,mx) head[i]=dame[i]=num[i]=0;

  rep(i,x) rep(j,y) if(mp[i][j]){
    num[mp[i][j]]++;
    
    // 隣接4マスで, 自分と接しているマスの数を求める
    c=0; rep(k,4) if(mp[i+dx[k]][j+dy[k]]==mp[i][j]) c++;
    if(c>=3) dame[mp[i][j]]++;
    if(c==1) head[mp[i][j]]++;

    // 隣接8マスで, 他の蛇と接しているかチェックします
    c=0; rep(k,8) if(mp[i+dx[k]][j+dy[k]] && mp[i+dx[k]][j+dy[k]]!=mp[i][j]) c++;
    if(c>=1) dame[mp[i][j]]++;
  }

  res=0;
  rep(i,mx){
    if(num[i]<3 || num[i]>20 || head[i]!=2 || dame[i]) continue;
    res++;
  }

  return res;
}

};

SPOJ 5973 - Selecting Teams [SELTEAM] (この記事を編集する[管理者用])

Source

Codechef Snackdown Onsite
SPOJ 5973 [SELTEAM]

問題概要

n人の人から,最大でk人選んでチームを作る.
チームの中から,好きなだけメンバーを選んで,レギュラーを決める.
レギュラーの中から1人だけキャプテンを決める.
さて,この決め方は何通りあるか,mod 8388608で求める問題.
nとkは100000以下.

解法

これは酷い気づきのゲーム.
キャプテンは誰か,何人チームにするか,各メンバーについてレギュラーにするかどうか,を考えると,答えは
 n * Σ[i=0..k] C(n-1,i) 2^i (Cは2項係数)
となる.
ところで,8388608は実は2^23なので,後半の和は途中で切れる.
なのでそこまで計算するだけ.

SPOJ 5975 - Travelling Knight [TRKNIGHT] (この記事を編集する[管理者用])

Source

Codechef Snackdown Onsite
SPOJ 5975 [TRKNIGHT]

問題概要

2n*2nのチェス盤があって,最初左上にナイトの駒がある.
0ターン以上,Kターン以下動いて,ナイトが何処かの隅にある動き方は何通りあるかmod 1000007で求める問題.
nは12以下,Kは大きい.

解法

行列べき乗.
盤面の対称性を利用して行列のサイズを減らす.
それでも制限時間が結構厳しめな気がした.
いつも,行列べき乗問題って制限時間に苦しめられてる気がするのだけど,皆どうやって高速なの書いているのだろう….

SPOJ 5980 - Matrix Game [MATGAME] (この記事を編集する[管理者用])

Source

Codechef Snackdown
SPOJ 5980 [MATGAME]

問題概要

2人でゲームをする.順番に行動し,行動できなくなったら負け.
最初,各要素が1以上50以下のN*Mの行列が与えられる.
各ターン,正の要素の有る行を1つ選んで,その行の一番左の数字を1以上好きな数だけ減らす.
先手必勝か,後手必勝かを判定する問題.
行と列はそれぞれ50以下.

解法

各行の状態は高々50^2しかないので,grundy numberを計算する.
上手く計算すると,各行でO(50^2)ぐらいの時間計算量でgrundy numberを計算できる.

SPOJ 5979 - Yet Another Permutations Problem [YAPP] (この記事を編集する[管理者用])

Source

Technovanza
SPOJ 5979 [YAPP]

問題概要

1~Nのpermutationのうち,全ての区間[i,j]に対して,その区間内の最大値が両端のどちらかにないといけない.
そのようなpermutationの数を求める問題.
Nは1000000000以下,数はmod 1000000007で答える.

解法

両端のどちらかがNでないといけない.
それを除いた,両端のどちらかがN-1でないといけない.
と考えていくと,それぞれ両端がどちらかという分だけ自由度があって,2^(N-1)が答え.

SPOJ 5978 - Frequent Prime Ranges [FRQPRIME] (この記事を編集する[管理者用])

Source

Technovanza
SPOJ 5978 [FRQPRIME]

問題概要

[2,N]の部分区間で,その中に素数をK個以上含むものは何個存在するかを求める問題.
Nは100000以下,Kは10000以下.

解法

尺取りメソッドでカウントしていく.
intではオーバーフローすることとか,Kが0のこともあるのとかに注意.

SPOJ 5969 - Finding Maximum [FINDMAX] (この記事を編集する[管理者用])

Source

Codechef Snackdown Onsite
SPOJ 5969 [FINDMAX]

問題概要

各要素が1以上K以下からなる整数列を考える.
左からなぞって最大値を求めるとき,現在までの最大値より厳密に大きいものと出くわしたら値を更新する.
長さNと値の更新回数がP回となるような数列はいくつあるかmod 1000000007を求める問題.
Nは100以下,Kは300以下.

解法

状態数O(NPK)のDPで,時間計算量もO(NPK)でやって,1回計算したら全てのクエリに対する答えが出てるようにする.

SPOJ 5977 - Weird Function [WEIRDFN] (この記事を編集する[管理者用])

Source

Codechef Snackdown Onsite
SPOJ 5977 Weird Function [WEIRDFN]

問題概要

 F[1] = 1
 F[i] = (a*M[i] + b*i + c)%1000000007
ただし,
 M[i]はF[1]~F[i-1]の中央値.
F[1]+F[2]+…+F[n]を求める問題.
nは200000以下.

解法

ヒープを2つ用意して,片方には,中央値より小さいものを入れておいて,大きいものをすぐ取り出せるようにしておく.
もう片方は,中央値より大きいものを入れておいて,小さいものをすぐ取り出せるようにしておく.
2つのピープ大きさのバランスが崩れたら,多い方から取り出して,小さい方に入れる.
そんな感じで解いた.

SPOJ 5976 - Traversing Grid [TRGRID] (この記事を編集する[管理者用])

Source

Codechef Snackdown Onsite
SPOJ 5976 [TRGRID]

問題概要

長方形のグリッドを左上からまだ通ってない端のマスを時計回りにぐるぐると中心に向かって歩く.
最後に向いている向きはどちらか.

解法

行数,列数どちらが多いか,行数,列数は奇数か偶数かで適当に場合分けして答える.

SPOJ 5972 - Maximum Sum Sequences [MAXSUMSQ] (この記事を編集する[管理者用])

Source

Codechef Snackdown Onsite
SPOJ 5976 [TRGRID]

問題概要

長さ100000以下の整数列が与えられる.
その連続する部分の和の最大値と,その最大値となるような区間の数を求める問題.
整数の値は-1000から1000まで.

解法

1回数列をなぞるだけで計算可能.数列を全部保存する必要すらない.
今までの和が0未満なら和を0にリセットしながら,最大値を記録する.
そのとき,最大値をとった時,今まで和が0になった回数だけ,区間の数を増やす.

SPOJ 5833 - XOR Rounds [XORROUND] (この記事を編集する[管理者用])

Source

Codechef Snackdown
SPOJ 5833 [XORROUND]

問題概要

500要素以下の整数列が与えられる.それが円周上に順番に並んでいるとする.
時間1たつごとに,各要素は,自分と両隣のビット演算のXORを取ったものに変わる.
時間K後の整数列を求める問題.

解法

最終的に各要素を何回XOR取れば良いのかというのを行列べき乗で計算することを考える.
それを単純に計算すると要素数をnとしてO(log(K)*n^3)になるけど,対称性を考慮するとO(log(K)*n^2)になる.
行列の掛け算は,対称性を考慮すると,1行目だけ計算すれば,他はその結果から求まる.

SPOJ 5832 - AND Rounds [ANDROUND] (この記事を編集する[管理者用])

Source

Codechef Snackdown
SPOJ 5832 [ANDROUND]

問題概要

20000要素以下の整数列が与えられる.それが円周上に順番に並んでいるとする.
時間1たつごとに,各要素は,自分と両隣のビット演算の&を取ったものに変わる.
時間K後の整数列を求める問題.

解法

自分と左右K個の&を取ったものが答え.
各ビットごとに計算するとして,自分か左右K個に0が1つでもあれば0にする.
1~i個までの0のものの数を最初に求めておけば,各ビットごとの計算はO(n)でできる.

SPOJ 5917 - Factorial length [LENGFACT] (この記事を編集する[管理者用])

Source

SPOJ 5917 [LENGFACT]

問題概要

n!の桁数を求める問題.nは5*10^9以下.

解法

nが大きいときはスターリングの近似公式を用いる.

SPOJ 5725 - 123 Sequence [KSEQ] (この記事を編集する[管理者用])

Source

Kurukshetra OPC 2010
SPOJ 5725 [KSEQ]

問題概要

123からなる単調非減少の数列で,全ての要素間の差(の絶対値)が与えられている.
 差が0の要素のペアの数は X
 差が1の要素のペアの数は Y
 差が2の要素のペアの数は Z
さて,そのような123からなる単調非減少の数列は何個あるかを求める問題.
X, Y, Zは10^8以下.

解法

場合分け問題.
0の数をa,1の数をb,2の数をcとすると
 2x = a(a-1) + b(b-1) + c(c-1)
 y = ab + bc
 z = ac
となるa, b, cの数を求めれば良い.
zが0でなければ,満たすa, cのペアを全部試す.
zが0でyが0でなければ…,などと場合分けして残りのパターンも調べる.

SPOJ 1437 - Longest path in a tree [PT07Z] (この記事を編集する[管理者用])

Source

SPOJ 1437 [PT07Z]

問題概要

ノード数10000以下の木が与えられるので,最長距離の2点間の距離を求める問題.

解法

2回DFSする.
適当なノードからの距離を全部求めて,それで一番遠かったノードからの距離を全部求めて,一番遠かったノード間の距離が答え.

SPOJ 1417 - University Employees [EMP] (この記事を編集する[管理者用])

Source

SPOJ 1417 [EMP]

問題概要

ある大学に勤務している人は,本当のことしか言わない人と,嘘しか言わない人の2種類の人がいる.
勤務している人誰に聞いても,
 自分より長く働いている人はN人未満である
 自分より給料が多い人はM人以上である
ということを言う.
さて,NとMが与えられたとき,この大学に勤務している人は合計で何人なのか求める問題.また解がないならそれを指摘する.
働いている期間,給料,は同一の人がいないものとする.

解法

ちょっと考えてみるとわかるはず.
A+B problem.

SPOJ 1108 - Card Trick [CTRICK] (この記事を編集する[管理者用])

Source

Nordic Collegiate Contest 2006
PKU 3032
SPOJ 1108 [CTRICK]

問題概要

1~nのカードが適当な順番で重なっている.
n回だけ以下の操作を繰り返す,k回目は
 上から1枚カードを取って一番下に送るという操作をk回行って,一番上のカードを取り除いたら取り除いたカードはkだった.
さて,最初の配置を求める問題.
PKUではnは13以下,SPOJではnは20000以下.

解法

PKUはどうでも良いからやるだけ.
SPOJも取り敢えず,O(n^2)で愚直にやる解法を送ったら通った.O(n^3)にならないようには気をつける.

UVa 10536 - Game of Euler (この記事を編集する[管理者用])

Source

UVa 10536

問題概要

2人でゲームを行う.
4*4のボードがあって,それぞれ長さ1,2,3のピンを大量に持っている.
各ターン,ピンを上から刺して,1つのマスを潰すか,横から挿して,長さ分のマスを潰すことができる.
潰されたマスを再び潰すことはできない.
最後,16個目のマスを潰すと負け.
盤面が与えられたとき,先手必勝か後手必勝かを判定する問題.

解法

状態が2^16しかないので,DPする.

SRM459 DIV2 HARD - ParkAmusement (別解) (この記事を編集する[管理者用])

Source

TopCoder SRM459 DIV2 HARD (1000pt)
Problem Statement
前書いたこの問題の記事

解説

隣接行列を用いた解法です.
せっかく書いたので貼り付けておきます.
問題の概要などは,前書いたこの問題の記事に書いています.

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

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

// size * size の 0行列 を返します
vector<vector<double> > zero_matrix(int size){
  vector<vector<double> > res(size, vector<double>(size, 0.0));
  return res;
}

// size * size の 単位行列 を返します
vector<vector<double> > identity_matrix(int size){
  int i;
  vector<vector<double> > res = zero_matrix(size);
  rep(i,size) res[i][i]=1;
  return res;
}

// 行列A*Bの結果を返します
vector<vector<double> > matrix_multiple(vector<vector<double> > A, vector<vector<double> > B){
  int i,j,k,size=A.size();
  vector<vector<double> > res = zero_matrix(size);
  rep(i,size) rep(j,size) rep(k,size) res[i][j]+=A[i][k]*B[k][j];
  return res;
}

class ParkAmusement {
public:
double getProbability(vector <string> landings, int startLanding, int K) {
  int i,j,num_path,n;
  double bunshi,bunbo;
  vector<vector<double> > adj, pw;

  // nはノードの数
  n=landings.size();

  // adjは隣接行列, pwは最終的にadj^Kを代入するつもりです
  adj = zero_matrix(n); pw = identity_matrix(n);

  // 1ステップで, i -> jに行く確率を代入して,隣接行列を作ります
  rep(i,n){
    if(landings[i][i]=='E' || landings[i][i]=='P') continue;
    num_path=0;
    rep(j,n) if(landings[i][j]=='1') num_path++;
    rep(j,n) if(landings[i][j]=='1') adj[i][j] += 1.0/num_path;
  }

  // adj^Kを求めて, pwに代入します
  // pw[i][j]はちょうどKステップ使ってiからjに行く確率が代入されます
  while(K--) pw = matrix_multiple(pw,adj);

  // bunboに何処からでもよいからKステップでゴールする確率
  // bunshiにstartLandingsからKステップでゴールする確率      をそれぞれ代入します
  bunshi=bunbo=0;
  rep(i,n) rep(j,n) if(landings[j][j]=='E'){
    bunbo += pw[i][j];
    if(i==startLanding) bunshi += pw[i][j];
  }

  return bunshi/bunbo;
}

};

Aizu 2030 - Ruins (この記事を編集する[管理者用])

Source

ICPC OB/OGの会 模擬アジア地区予選 2006-10-22
Aizu 2030

問題概要

10000以下の自然数a, bが与えられるので,
 a = a1 * a2, b = b1 * b2
と分解して,a1, a2, b1, b2をソートした数列をc1, c2, c3, c4とする.
 (c1 - c2)^2 + (c2 - c3)^2 + (c3 - c4)^2
の最小値を求める問題.

解法

分解の仕方はそれぞれ高々100通りなので全部調べる.

Aizu 2028 - Gather on the Clock (この記事を編集する[管理者用])

Source

ICPC OB/OGの会 模擬アジア地区予選 2005-10-30
Aizu 2028

問題概要

円上に100枚以下のカードが並べられている.カードには1から100までの数字のどれかが書かれている.
1枚のカードを選んで,時計回りに1つ隣のカードに重ねて,その際,2つのカードの数字の差だけ得点を得る.
これを繰り返して得られる最高点を求める問題.

解法

典型的なDP.

Aizu 2025 - Eight Princes (この記事を編集する[管理者用])

Source

ICPC OB/OGの会 模擬アジア地区予選 2005-10-30
Aizu 2025

問題概要

円形にn個の席があって,8人の王子が座る.
隣同士には座れない,nが偶数のときは丁度向かい合わせの席にも座れない.
8人の王子を区別するとき,何通りの座り方があるかを求める問題.
答えは10^14以下.

解法

王子を区別しないとか,席の回転対称性とかを使うと,実質のパターンの数は大して多くない.
最初にnが70以下のときの答えを全探索で計算しておいて(所要時間は1分20秒ぐらいでした),埋め込んで提出した.
普通に解くとしたらDPっぽいのだけど….

UVa 10563 - Least Squares (この記事を編集する[管理者用])

Source

UVa 10563

問題概要

100*80以下の穴あきのグリッドが与えられる.
穴の部分は覆ってはいけないとして,幾つかの正方形を使って全てを覆いたい.
A~Zの色の様々なサイズの正方形がたくさんある.
同じ色の正方形は隣接してはいけない.
この条件で,正方形を敷き詰める方法のうち,辞書順最小のものを求める問題.

解法

greedy.
左上から順番にまだ敷いてないマスを左上端とする正方形を敷いていく.
その時,敷ける正方形の中で一番Aに近いものを採用し,サイズは,これ以上大きくできないか,右端の次のマスがもっと小さい色を敷けるようになるまで広げる.

UVa 10543 - Traveling Politician (この記事を編集する[管理者用])

Source

UVa 10543

問題概要

ノード数50以下の有向グラフが与えられる.
始点から終点まで,使う枝数k以上で,最小限の枝数で移動したい.その枝数を求める問題.
kは16以下,k以上,20個以下の枝で辿り着けないならそれを指摘する.

解法

今のノード,使った枝数を状態としてDFS.

UVa 10503 - The dominoes solitaire (この記事を編集する[管理者用])

Source

UVa 10503

問題概要

ドミノ(両端に数字の書かれた棒)がm個ある.
また,間に丁度n個のドミノが入るように,2つのドミノが置かれている.
接する辺に書かれている数字は同じ数字となるようにn個のドミノを置くことができるかを判定する問題.
mは14以下.

解法

最後に使ったドミノと使った向き,残っているドミノを状態としてDFSすれば良い.

UVa 11770 - Lighting Away (この記事を編集する[管理者用])

Source

World Finals Warmup II (2010-01-23) (blog)
UVa 11770

問題概要

ノード数10000以下,枝数100000以下の有向グラフが与えられる.
iからjへ枝が張ってあれば,スイッチiをONにすると自動的にスイッチjもONになる.
最初全部OFFだったとして,最小で何個のスイッチを手動でONにすれば,全てのスイッチがONになるかを求める問題.

解法

強連結成分分解して,DAGに落として,自分のノードに枝が入ってないものの数を求めれば良い.

UVa 11769 - All Souls Night (この記事を編集する[管理者用])

Source

World Finals Warmup II (2010-01-23) (blog)
UVa 11769

問題概要

3次元平面上の点が25個以下与えられる.
その凸包の表面積を求める問題.
ただし,同じ平面上に4点以上ないとする.

解法

3点を選んで,その3点から作られる平面を考えて,他の点がその平面の片側にしかなければ,その3点から作られる3角形は凸方の表面なので,その面積を足していく.
平面のどちら側に点があるか,というのを判定するのは,2次元のとき符号付き面積を使うのと同じように,符号付き体積を使って計算した.

UVa 11768 - Lattice Point or Not (この記事を編集する[管理者用])

Source

World Finals Warmup II (2010-01-23) (blog)
UVa 11768

問題概要

2次元平面.始点と終点の座標が与えられるので,その線分が通る格子点の数を求める問題.
始点と終点は小数点以下1桁までの実数で,その絶対値は20万以下.

解法

10倍して整数に直してから,通る格子点を列挙する.これはgcdなどを使って計算する.
その格子点のうち,x座標,y座標ともに10の倍数であるものの数をカウントすれば良い.

UVa 11766 - Racing Car Computer (この記事を編集する[管理者用])

Source

World Finals Warmup II (2010-01-23) (blog)
UVa 11766

問題概要

n台の車でレースをしている.
ある瞬間,それぞれの車の前にいる車の台数と,後ろにいる車の台数を報告させた.
自分の横にいる車は,前にも後ろにもカウントしない.
嘘をついているのは最小で何人か求める問題.
nは1000以下.

解法

ある順位以降の車が最大で何人本当のことを言ってるかを記憶するDP.
各順位の車の処理は,前にいる車の数で順位を判定して,その順位に同率で何人並んでいるかで場合分けする.

UVa 11765 - Component Placement (この記事を編集する[管理者用])

Source

World Finals Warmup II (2010-01-23) (blog)
UVa 11765

問題概要

2つのレイヤーがあって,n個のものをどちらかのレイヤーに置く.
あるものはどちらかのレイヤーに置かなくてはならない,と指定されているものもある.
それぞれ,各レイヤーに置くためのコストが設定されている.
また,それぞれのペアについて,別のレイヤーに置いた場合に発生するコストが設定されているものもある.
最小コストを求める問題.
nは200以下.

解法

グラフの最小カットに帰着させて,最大流で解く.
まず,片方のレイヤーにしか置けないものは,違うレイヤーに置くコストを無限大に設定しておく.
最大流のグラフの作り方は,
 始点→各ノード に フロー レイヤー1に置くコスト
 各ノード→終点 に フロー レイヤー2に置くコスト
 各ノード→各ノード に フロー その2つのノードを別々のレイヤーに置いたときに発生するコスト
とすれば良い.

Appendix

Recent Articles

ブログ内検索

Ads


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