Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-03-16

[][][][] SRM475 300 RabbitStepping 01:41 はてなブックマーク -  SRM475 300 RabbitStepping - 練習帳

テーマ:±1 のズレで心が折れないようにする訓練

問題(要ログイン)

 http://www.topcoder.com/stat?c=problem_statement&pm=10878&rd=14156

要約

 N 個のマス横に並んでおり,白,黒,赤いずれかに塗られている。そこに r 羽のウサギが等確率で配置され,次のアルゴリズムを繰り返す

  • ウサギが左右どちらに移動する。移動方向は乗っているマスの色と位置に応じて決まる。
  • もし同じマスにウサギが 2 羽いたら 2 羽とも除外される
  • 一番右端のマスが除外される(移動のルールからこのマスにウサギはいない)
  • 以上のステップをマスが 2 個になるまで繰り返す

 ウサギの移動方向は次のルールで決まる。

  • 左端のマスにいる場合は右へ
  • 右端とその左隣にいる場合は左へ
  • それ以外の場合
    • マスが白色なら左へ
    • マスが黒色なら右へ
    • マスが赤色の場合
      • 最初の移動の場合は左へ
      • 2 回目以降の移動場合その直前のステップにいたマスに戻る

 最終的に残るウサギの数は0,1,2匹のどれか。最終的に残るウサギの数の期待値を求めよ。

 最初のマスの数 N は 2 以上 17 以下,ウサギの数 r は 1 以上 N 以下

方針

 ウサギの初期位置の可能性は高々 2^N で,各々の場合を検査するのに愚直にやっても O(N^2) ,N は 17 なので全探索できる。

コード(c++)

#include <string>
#include <iostream>

using namespace std;

int countone(int n){
  int ans = 0;
  while(n > 0){
    if(n & 1) ans++;
    n = n >> 1; 
  }
  return ans;
}

class RabbitStepping {
public:
  int check(string field, int pos){
    int n = (int ) field.size();
    int now = pos;
    int prev = -1;
    for(int i = 0; i < n - 2; i++){
      int buf = 0;
      for(int j = 0; j < n - i; j++){ 
	if(now >> (n - j - 1) & 1){
	  if(j == 0){
	    buf ^= 1 << n - j - 2; // go to right
	  }else if (j == n - i - 1 || j == n - i - 2){
	    buf ^= 1 << n - j; // go to left
	  }else{
	    if(field[j] == 'W'){
	      buf ^= 1 << n - j;
	    }else if(field[j] == 'B'){
	      buf ^= 1 << n - j - 2;
	    }else{
	      if(i == 0){
		buf ^= 1 << n - j;	
	      }else if(prev >> (n - j) & 1){
		buf ^= 1 << n - j - 2;
	      }else{
		buf ^= 1 << n - j;
	      }
	    }
	  }
	}
      }
      prev = now;
      now = buf;
    }
    return countone(now);
  }

  double getExpected(string field, int r) {
    int n = (int) field.size();
    int count = 0;
    int ans = 0;
    for(int i = 0; i < 1 << n; i++){
      if(countone(i) != r) continue;
      ans += check(field, i);
      count++;
    }
    return (double)ans/count;
  }

分析

 countone関数と等価なものはgccのビルトイン関数としてある事をSigmarさんのブログ*1で知りました

Built-in Function: int __builtin_popcount (unsigned int x)

Returns the number of 1-bits in x.

http://gcc.gnu.org/onlinedocs/gcc-4.5.2/gcc/Other-Builtins.html

TopCoderではgcc4.02を用いているので*2使えます。

 この問題で考えたいのはどうしたら 1 回で正しいコードを書けるか。特にこの問題の場合プラスマイナス 1 のミス,符号のミスなどをしそうな場所が至る所にあります。プログラミングコンテストに慣れている方のノウハウを是非教えて頂きたいです。

 上のコードの場合,ウサギの位置を2進数で表示し,int型のひとつの変数に納めています。その時右端を LSB としているので,問題の指示文通り右端のマスを削ってしまうと,1ステップ進むごとにマスを表す桁の位置がずれてしまいます。そこで上のコードでは削られた部分は 0 で pudding しています。これにより左から j 番目のウサギが右に進む場合には

buf ^= 1 << n - j - 2;

左に進む場合は

buf ^= 1 << n - j;

とステップの回数 i によらずに書く事が出来ます。「右に進む」「左に進む」を機械的に上の式に変換できるので楽をできました。両者が見かけ対称でないように見えますが,これは本来

buf ^= 1 << (n - j - 1) - 1;

buf ^= 1 << (n - j - 1) + 1;

と書かれるべきものです。左右から番号を振ると

 |   |   |   ...   |   |
 0   1   2   ...  n-2 n-1
n-1 n-2 n-3  ...   1   0

なので,0-indexedの場合 n-1 が不変な和です。

右端を LSB としている弊害はもう一つあり,変数 j は桁の高い方から低い方に走査しているので,あらゆる所で n-j が現れてしまいます。ウサギの位置をbool pos[17]などの配列で管理すると上の2つの問題は解消されます。

2010-01-12

[][][][] SRM168 07:05 はてなブックマーク -  SRM168 - 練習帳

・SRM164は迷宮入りしたため一度放置

234.61/250

#include <cstring>
#include <vector>
#include <iostream>

using namespace std;

class NumberGuesser{
public:
int guess(string leftOver){
  int n=0;
  for(int i=0;i<3;i++){
    n+=leftOver[i]-'0';
  }
  return 9-n%9;	
}
};

・適当に数字を入れ替えた2つの数について差をとれば必ず9の倍数になる。

2010-01-08

[][][][] SRM165 07:47 はてなブックマーク -  SRM165 - 練習帳

132.50/250

・そのままだとi*(i-1)がオーバーフローを起こす

→下のコードだとmax_calcを用いてiの動く範囲を制限してiが大きくなりすぎないようにしているが、iはlong long int型にしたほうが良い。

→top coderをやっていて初めてオーバーフローを考慮しないといけない設計に出くわした


#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

class ParallelSpeedup{
public:

int numProcessors(int k, int overhead){
	int min_temp=k;		
	unsigned int work=0;
	int ans=1;

	int max_calc=(int)( pow ( (double)2*k/overhead, ( (double)1/3) ) +1);

	if(k>2){
	for(int i=1;i<max_calc;i++){</pp>
		work=i*(i-1)*overhead/2+(int)ceil( ( ( double ) k )/i);
		if(min_temp > work){
			min_temp=work;
			ans=i;
		}		
	}
	}
	return ans;
}
};

2010-01-03

[][][][] SRM166 08:30 はてなブックマーク -  SRM166 - 練習帳

・タイムは諦めてベクタやソートを使う練習と割り切る

→大小関係の作成のためにわざわざ新しくベクタ(binary_order)を作る必要はない、sortの多重定義で第3引数に大小判定に用いる関数を指定するものがある。

・大小判定のif文の使い方がひどい

90.62/250

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
	struct binary_order{
		int num;
		binary_order(int n) : num(n){};
	};

	int binary(int n){
		int ans=0;
		while(n>1){
			if(n%2){ans++;}
			n=n/2;
		}
		ans+=n;
		return ans;
	}


	bool operator<(const binary_order &x, const binary_order &y){
		if(binary(x.num)<binary(y.num)){</pp>
			return 1;
		}else if(binary(x.num)==binary(y.num) && x.num< y.num ){
			return 1;
		}else{
			return 0;
		}
	}

class BinaryCardinality{
public:
vector <int> arrange(vector <int> numbers){
	vector<int> ans;
	int len=numbers.size();
	
	vector<binary_order> v;
	binary_order* p=NULL;
	for(int i=0;i<len;i++){</pp>
		p=new binary_order(numbers[i]);
		v.push_back(*p);
	}
	
	sort(v.begin(),v.end());
	
	for(int i=0;i<len;i++){</pp>
		ans.push_back(v[i].num);
	}
	return ans;


}
};

2010-01-02

[][][][] SRM167 08:19 はてなブックマーク -  SRM167 - 練習帳

新年一発目

170.03/250

#include <vector>
#include <string>

using namespace std;

class Animation{
public:

vector <string> animate(int speed, string init){
	vector<string> ans;
	ans.clear();
	int len=init.length();
	int const max_time = 1+(len+1/speed);
	string buffer;
	buffer.clear();
	
	for(int i=0;i<max_time+1;i++){</pp>
		buffer.clear();
		
		for(int j=0;j<len;j++){</pp>
			if((j-speed*i>=0&&init[j-speed*i]=='R') ||  (j+speed*i<len &&init[j+speed*i]=='L') ){</pp>
				buffer.push_back('X');
			}else{
				buffer.push_back('.');				
			}
		}
		ans.push_back(buffer);	
		const string empty(len,'.');
		if(buffer==empty){
			break;
		}
	}
	return ans;
}
};

直感で問題を選んだら番号がかなり飛んでしまった。

エラーがまったくでなかったのは初めてかもしれない