
deque<int> insert( deque<int> v, int n, int size ){
  int a=0;
  for(int i=v.size()-1 ; i>= max(0, (int)v.size()-size) ; i--){
    a += v[i];
  }

  a %= 10;

  v.push_back(a);

  if( v.size()> n ){
    v.pop_front();
  }
  return v;

}

class EasySequence {
public:
  int find(vector <int> A, vector <int> B) {
    
    if(A.size() > B.size()){
      for(int i=0 ; i<=A.size()-B.size() ; i++){
	vector<int> v;

	for(int j=i ; j<i+B.size() ; j++){
	  v.push_back(A[j]);
	}
	
	if(v==B) return i;
	
      }
    }
    
    if(A == B)return 0;
    
    int An = A.size();
    int Bn = B.size();
    
    deque<int> AA, BB;
   
    for(int i=0 ; i<A.size() ; i++)
      AA.push_back(A[i]);
    	  

    for(int i=0 ; i<B.size() ; i++)
      BB.push_back(B[i]);
    
    
    while( AA.size() < BB.size())
      AA = insert(AA, Bn, An);
    
    
    if( AA == BB) return 0;
    
    clock_t start, end;
    start = clock();
    int cnt = AA.size()-BB.size();
    while(1){
      
      AA = insert( AA,Bn,An );
      cnt++;
      if( AA.size() == BB.size()){
	if( AA==BB ) return cnt;
      }
      else{
	deque<int> AAA;
	for(int i=AA.size()-BB.size() ; i<AA.size() ; i++){
	  AAA.push_back( AA[i] );
	}      
	if( AAA==BB) return cnt;
      }

      // 1.9秒超えたら終わり
      end = clock();
      if( (end-start)/CLOCKS_PER_SEC > 1.9) return -1;
    }

  }
};

2011-07-28

TopCoder SRM 458 DIV 2

Problem 500

int n;

// int aの下からn桁分のbitをdequeに入れて返す
deque<int> bitDigits(int a, int dig){
	deque<int> arr;

	for(int i=0 ; i<dig ; i++){
		arr.push_front(a%2);
		a/=2;
	}
	return arr;
}


class BouncingBalls {
public:
  double expectedBounces(vector <int> x, int T) {
    double result;
	n = x.size();

	ll time = 2LL*T;

	double ans=0;

	sort(x.begin(), x.end());

	for(int i=0 ; i< (1<<n) ; i++){
		deque<int> d = bitDigits(i, n);
		
		int cnt=0;

		for(int j=0 ; j<d.size() ; j++){
			int p = d[j];
			int pnum = x[j];

			
			if(p == 0){
				for(int k=j-1 ; k>=0 ; k--){
					if( d[k] == 1 && pnum - x[k] <= time ) cnt++;
				};
			}
			else{
				for(int k=j+1 ; k<d.size() ; k++){
					if( d[k] == 0 && x[k] - pnum <= time ) cnt++;
				};
			}
			
		}
	
		ans += (double)cnt/2;

	}

    return ans/(1<<n);
  }
};

Problem 950

これ絶対950じゃねぇよ

ll calc(int x, int y1, int y2, int z1, int z2){
	z1 = max(z1, x*x+1);

	if(z2 < z1 ) return 0;

	ll a1 = min( (ll)y2, (ll)floor( (double)z2/x ) );
	ll a2 = max( (ll)y1, (ll)ceil(  (double)z1/x ) );
	a2 = max( a2, (ll)x );

	return max(0LL, a1-a2+1);
}


class ProductTriplet {
public:
  long long countTriplets(int minx, int maxx, int miny, int maxy, int minz, int maxz) {
	ll ans = 0;

	for(ll x=minx ; x*x < maxz && x<=maxx ; x++){
		ans += calc(x, miny, maxy, minz, maxz );
	}

	for(ll y=miny ; y*y < maxz && y<=maxy ; y++){
		ans += calc(y, minx, maxx, minz, maxz );
	}

	for(ll a = max(minx,miny) ; a*a <= maxz && a<= min(maxx, maxy) ; a++){
		if(minz <= a*a) ans++;
	}
	return ans;
  }
};

2011-07-14

TopCoder SRM 459 DIV 2

Problem 500

// -inf to 0
int bottom;

// area[k] -> k to k+1
int area[1001];
int point[1001];

vector<string> split(const string& str, const string& delimiter) {
    // delimiter(2 文字以上も可) を空白に置換
    string item(str);    
    for(unsigned pos = item.find(delimiter); pos != string::npos; pos = item.find(delimiter, pos)) {
        item.replace(pos, delimiter.size(), " ");
    }
    // 分解
    stringstream buf(item);

    // 読み取り
    vector<string> result;
    while(buf >> item) {
        result.push_back(item);
    }

    return result;
}



class Inequalities {
public:
  int maximumSubset(vector <string> inequalities) {

	  for(int i=0 ; i<= 1000 ; i++){
		  area[i] = point[i] = 0;
	  }
	  bottom = 0;

	  for(int i=0 ; i<inequalities.size() ; i++){
		 vector<string> vs = split( inequalities[i], ",");

		 int p = atoi(vs[2].c_str());

		 if( vs[1] == "=" ){
			 point[p]++;
		 }

		 else if( vs[1] == ">=" ){
			 for(int j=p ; j<=1000 ; j++){
				 point[j]++;
				 area[j]++;
			 }
		 }
		 else if( vs[1] == "<=" ){
			 bottom+=1;

			 point[p]++;
			 for(int j=p-1 ; j>=0 ; j--){
				 point[j]++;
				 area[j]++;
			 }

		 }

		 else if( vs[1] == ">"){
			 area[p]++;
			 for(int j=p+1 ; j<=1000 ; j++){
				 point[j]++;
				 area[j]++;
			 }
		 }
		 else{
			 bottom++;
			 for(int j=p-1 ; j>=0 ; j--){
				 point[j]++;
				 area[j]++;
			 }
		 }
	  }

	  int maxp=0;
	  for(int i=0 ; i<=1000 ; i++){
		  maxp = max( maxp, max( point[i], area[i] ));
	  }

	  return max( maxp, bottom );

  }
};

Problem 1000

double dpa[51][51];
double dpb[51][51];

int num1[51];

class ParkAmusement {
public:
  double getProbability(vector <string> landings, int startLanding, int K) {
    double result;

	for(int i=0 ; i<51 ; i++){
		for(int j=0 ; j<51 ; j++){
			dpa[i][j] = dpb[i][j] = 0;
		}
	}

	for(int i=0 ; i<landings.size() ; i++) dpa[0][i] = 1;
	dpb[0][startLanding] = 1;


	for(int i=0 ; i<landings.size() ; i++){
		int a=0;
		for(int j=0 ; j<landings.size() ; j++){
			if( landings[i][j] == '1') a++;
		}
		num1[i] = a;
	}

	for(int i=0 ; i<K ; i++){
		for(int j=0 ; j<landings.size() ; j++){
			if( num1[j] == 0 ) continue;

			for(int k=0 ; k<landings.size() ; k++){
				if(landings[j][k] == '1'){
					dpa[i+1][k] += dpa[i][j]/num1[j];
					dpb[i+1][k] += dpb[i][j]/num1[j];
				}
			}
		}
	}

	double numerator = 0, denominator = 0;

	for(int i=0 ; i<landings.size() ; i++){
		if( landings[i][i] == 'E' ){
			numerator += dpb[K][i];
			denominator += dpa[K][i];
		}
	}

    return numerator/denominator;
  }
};

2011-06-20

TopCoder SRM 329 DIV 2

Problem	Check	Points
250	o	230ぐらい
500	x
1000

500解けなすぎる・・・

Problem 250

You are given a String text, each element of which contains a single word. Encrypt the text by removing all vowels ('a', 'e', 'i', 'o', 'u') from every word that contains at least one non-vowel. If a word consists only of vowels, leave it as is. Return the result as a String, where the ith element is the encrypted version of the ith element in text.

bool isVowel(char c){
	return c=='a' || c=='i' || c=='u' || c=='e' || c=='o';
}


bool allVowel(string s){
	for(int i=0 ; i<s.size() ; i++){
		if( !isVowel(s[i]) ) return false;
	}
	return true;
}


class VowelEncryptor {
public:
  vector <string> encrypt(vector <string> text) {
    vector <string> ret(text.size());

	for(int i=0 ; i<text.size() ; i++){
		
		if(allVowel(text[i])) ret[i] = text[i];
		
		else{
			for(int j=0 ; j<text[i].size() ; j++){
				if( !isVowel(text[i][j]) ) ret[i] += text[i][j];
			}
		}
	}

    return ret;
  }
};

Problem 500

In a certain European country, railroad cars consist of 9 compartments, each containing 4 seats. There are two possible numeration methods for the seats: the domestic numeration and the international numeration.

In the domestic numeration, the seats in the first compartment are numbered 1 through 4, the seats in the second compartment are numbered 5 through 8, and so on.

In the international numeration, every seat's number consists of two digits. The first digit is the number of the compartment and the second digit is the number of the seat within that compartment. Compartments are numbered 1 through 9, and the four seats within each compartment are numbered 1, 3, 4, 6 (in the same order as in the domestic numeration).

You are given a int[] tickets containing seat numbers in an unknown numeration. Assuming that every seat number in tickets is in the same numeration, convert them into the international numeration. Return the result as a String containing a single-space separated list of converted numbers in the same order that they are given in the input. If there are several possible return values, return "AMBIGUOUS" (quotes for clarity only). If the input cannot be interpreted as a valid list of seat numbers all in the same numeration, return "BAD DATA" (quotes for clarity only).

int domestic2inter(int n){
	int a=((n/4)+1)*10;

	if(n%4==0) a -= 10;

	switch(n%4){
	case 1:
		a += 1;
		break;
	case 2:
		a += 3;
		break;
	case 3:
		a += 4;
		break;
	case 0:
		a += 6;
		break;
	default:
		a = 10000;
		break;
	}
	return a;
}

bool isDomestic(int n){
	return 1 <= n && n <= 36;
}

bool isInter(int n){
	if( !(1<= n/10 && n/10 <= 9) ) return false;
	if( n%10 == 1 || n%10 == 3 || n%10 == 4 || n%10 == 6) return true;
	return false;
}



class RailroadSeatNumeration {
public:
  string getInternational(vector <int> tickets) {

	  string str;
	  string state = "domes";

	  for(int i=0 ; i<tickets.size() ; i++){
		  if (!isDomestic( tickets[i] )) state="inter";
	  }

	  // domestic OK
	  if(state=="domes"){
		  
		  for(int i=0 ; i<tickets.size() ; i++){
			  if (!isInter( tickets[i] ) ) state= "ok";
		  }

		  // domestic OK && inter OK
		  if(state=="domes") return "AMBIGUOUS";

		  for(int i=0 ; i<tickets.size() ; i++){
			  stringstream ss;
			  ss << domestic2inter(tickets[i]);
			  str += ss.str() + " ";
		  }
		  return str.substr(0, str.size()-1);
	  }

	  // domestic NG
	  for(int i=0 ; i<tickets.size() ; i++){
		  // domestic NG && inter NG
		  if (!isInter( tickets[i] ) ) return "BAD DATA";
	  }

	  for(int i=0 ; i<tickets.size() ; i++){
		  stringstream ss;
		  ss << tickets[i];
		  str += ss.str() + " ";
	  }
	  return str.substr(0, str.size()-1);

  }
};

2011-05-24

WindowsでMathematicaをコマンドラインから実行する

Mathematica

Mathematicaのドキュメントセンターの「Mathematica スクリプト」という項には、MACとLinux上でコマンドラインから.mファイルを実行するやり方が載っています。
じゃあWindowsは？できないの？
基本的にはパスを通して呼び出すだけですから、Windowsでできないということはないはず。やってみました。

まずは準備としてcygwinをインストールします。cygwinというのは端的に言えばUnixコンソールをwindows上で動かすもの、という感じでしょうか。Windowsのコマンドプロンプトでもできないことはありませんが、UNIXに慣れているとほとんどのコマンドが異なっていてやりにくいことこの上ないのでやはりcygwinです。

cygwinのインストール方法については検索するといろいろでてきます。こことかを参考にインストールしてみてください。いろいろ聞かれますが全部「はい」とか「OK」とか押してよいです。(結構時間がかかります)

さて、cygwinがインストールできたとしましょう。早速Cygwin(Cygwin bash shell)を起動しましょう。コマンドプロンプトみたいな画面がでてきます。
「pwd」と入力すると「/home/owner」と表示されます。Windowsでいうとこの場所は「C:/cygwin/home/owner」になります。

それではここでMathematicaを立ち上げ、コマンドラインから実行させたい.mファイルを作りましょう。
Mathematicaのメニュー>ファイル>新規作成>パッケージを選び、以下のコードを貼っつけて保存してください。ファイル名はscript.m としましょう。
(既存のnbファイルの拡張子だけをmに変えても実行できないので注意してくださいね)

#!/usr/local/bin/MathematicaScript -script
vals = RandomVariate[MixtureDistribution[
    {1,2},
    {NormalDistribution[1,2/10],
     NormalDistribution[3,1/10]}],
    10,  WorkingPrecision -> 50]
Export["test.txt",vals]

一行目に「#!/usr/local/bin/MathematicaScript -script」と入れるのが重要。
できたscript.mを、「C:/cygwin/home/owner」の位置に移動させます。

cygwin上で「export PATH=$PATH:/cygdrive/c/Program\ Files/Wolfram\ Research/Mathematica/8.0」と入力。このコマンドによってMathKernel.exeの位置をcygwinに読み込ませます。

あとは「MathKernel -script script.m」と入力すれば、MathKernel.exeが立ち上がり一瞬で終了します。
さて、さっきのテストコードには

Export["test.txt", vals]

の1行を入れてあったので、これが出来ているかどうか確認してみてください。
「C:/cygwin/home/owner」の位置にtest.txtが作成されていると思います。

この方法だとcygwinを起動するたびに「export PATH=$PATH:/cygdrive/c/Program\ Files/Wolfram\ Research/Mathematica/8.0」と入力しなければいけません。それが面倒、という人は「C:/cygwin/home/owner」の位置にある.bashrcというファイルをエディタで開き、一番下に以下を追加、保存してください。

export PATH=$PATH:/cygdrive/c/Program\ Files/Wolfram\ Research/Mathematica/8.0

保存してからcygwinを起動すると既にPATHが通った状態になっています。これであなたもwindowsでバッチ処理快適生活です。

ひとまずはこれでWindows上で.mファイルをコマンドラインから実行できました。コマンドラインから引数を渡す方法、また実行権限を与えて実行させる方法はまだ調べ中です。ドキュメントセンター$ScriptCommandLine の項ががほとんど空でどうしたものやら。
実行権限を与える方法は、どうもwindowsの改行コードがCR+LFなのが悪さしているみたいです。一応むりやり解消するようなこともやってみましたが、どうもそれだけでない問題もありそう。

math, programming, and little something to laugh

フォームを継承するとデザイナでエラーが起こる問題

Haskell始めてみた

TopCoder SRM 455 div2

500

TopCoder SRM 458 DIV 2

Problem 500

Problem 950

TopCoder SRM 459 DIV 2

Problem 500

Problem 1000

TopCoder SRM 329 DIV 2

Problem 250

Problem 500

WindowsでMathematicaをコマンドラインから実行する