忍者ブログ
01 May

[PR]

×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

24 January

SRM605 div2 250,500

問題文

Easy

http://community.topcoder.com/stat?c=problem_statement&pm=12950
文字列Sのうちどこか1文字消すとき何通りの文字列ができるか。

Meidium

http://community.topcoder.com/stat?c=problem_statement&pm=12821

長方形の盤面が黒か白に塗られている。
1行分の色を反転する操作を何回かしたときにできる
最大の正方形の面積を求めよ。


感想

Easy

文字が変わった回数をカウントして、プラス1。

Medium

全探索で間に合うみたいだからごり押し。

Hard

解けません(´・ω・`)



#include<iostream>
#include<string>

using namespace std;

class AlienAndPassword{
public:
	int getNumber(string S){
		int cnt=0;
		for(int i=1;i<S.size();i++){
			if(S[i-1] != S[i]) cnt++;
		}
		return cnt+1;
	}
};


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

using namespace std;

class AlienAndGame{
public:
	int getNumber(vector<string> board){
		int MAX;
		int ans=1;
		MAX = min(board[0].size(),board.size());
		
		for(int length=1;length<=MAX;length++){
		
		for(int i=0;i<board.size()-length+1;i++){
			for(int j=0;j<board[0].size()-length+1;j++){
			
				int fuga=0;
				
				for(int k=0;k<length;k++){
					int hoge=0;
					for(int l=0;l<length-1;l++){
						if(board[i+k][j+l] == board[i+k][j+l+1])
							hoge++;
					}
					if(hoge+1==length)fuga++;
				}
				if(fuga==length)ans=length;
			}
		}}
		return ans*ans;
	}
};

PR
19 January

SRM604 div2 500

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12952

ゴールである(x,y)座標が与えられる。
kターン目には上か右に3^k分進まなければならないとすると、(kは0から)
ゴールには辿り着けるか返せ。

感想

本番の時は2^kならXOR?とかで解けるのにとか思っていましたが、
3^kでも同じようなものだとChallengeの時に気づきました。


#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class PowerOfThreeEasy {

	public: string ableToGet(int x, int y) {
		while(1){
			if((x%3==0&&y%3==1)||(x%3==1&&y%3==0)){
				x/=3;
				y/=3;
			}
			else{
				if(x==0&&y==0)return "Possible";
				return "Impossible";
			}
		}
	}

};


13 January

安定結婚問題

安定結婚問題

詳しくはWikipediaを見てもらいたい。
大雑把に言うと、男女それぞれ異性の好みのランキングのリストを渡された時、
浮気しないようなペアを作ってくださいみたいな問題。
そのペアをブロッキングペアというらしい。

これはGale-Shapleyアルゴリズムを用いて解くことができる。
Shapleyさんはノーベル経済学賞受賞してるっぽい。

暇だったので0から書いてみた。
考えながら書いてたらぐちゃぐちゃになった。
間違ってる可能性大。


#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <climits>
#include <algorithm>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#define N 4
#define M 20
//N要素数
//M=シャッフルする回数

using namespace std;
bool check(int v[N]){
	for(int i=0;i<N;i++){
		if(v[i]==N)return true;
	}
	return false;
}
void showList(int manRank[N][N],int womanSuki[N][N]){
	cout << "男性希望リスト" << endl;
	for(int i=0;i<N;i++){
		cout << i << ":";
		for(int j=0;j<N;j++){
			cout << manRank[i][j];
			if(j!=N-1)cout << ",";
		}
		cout << endl;
	}

	cout << "女性希望リスト" << endl;
	int womanRank[N][N];
	for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				womanRank[i][womanSuki[i][j]]=j;
		}
	}
	for(int i=0;i<N;i++){
			cout << i << ":";
			for(int j=0;j<N;j++){
				cout << womanRank[i][j];
				if(j!=N-1)cout << ",";
			}
			cout << endl;
		}
}
void showMatch(int manMarriage[N],int womanMarriage[N]){
	cout << "男性-女性" << endl;
	for(int i=0;i<N;i++){
		cout << i << "-" << manMarriage[i] << endl;
	}
}

int main(){
	int manRank[N][N];
	int womanSuki[N][N];
	srand((unsigned) time(NULL));
	for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				manRank[i][j]=j;
				womanSuki[i][j]=j;
			}
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			int hoge;
			int c1=rand() % N;
			int c2=rand() % N;
			hoge = manRank[i][c1];
			manRank[i][c1]=manRank[i][c2];
			manRank[i][c2]=hoge;
			c1=rand() % N;c2=rand() % N;
			hoge = womanSuki[i][c1];
			womanSuki[i][c1]=womanSuki[i][c2];
			womanSuki[i][c2]=hoge;
		}
	}
	showList(manRank,womanSuki);
	//誰と結婚しているか
	int womanMarriage[N];
	int manMarriage[N];
	//プロポーズ回数
	int manDraft[N];
	for(int i=0;i<N;i++){
		womanMarriage[i]=N;
		manMarriage[i]=N;
		manDraft[i]=0;
	}

	//独身男性がいる限りループ
	int cnt=0;
	while(check(manMarriage)){

		for(int i=0;i<N;i++){
			if(manMarriage[i]==N){//iが未婚男性の場合
				int hope = manRank[i][manDraft[i]];//希望女性
				if(womanMarriage[hope]==N){//希望女性が未婚
					manMarriage[i]=hope;			//結婚
					womanMarriage[hope]=i;
					manDraft[i]++;
				}
				else{//希望女性が既婚
					if(womanSuki[hope][i]<womanSuki[hope][womanMarriage[hope]]){//女性にとって今プロポーズされた男性の方が良い時
						manMarriage[womanMarriage[hope]]=N;//NTRれた人は未婚に
						womanMarriage[hope]=i;				//結婚しなおし
						manMarriage[i]=hope;
						manDraft[i]++;
					}
					else{//NTR失敗
						manDraft[i]++;//プロポーズカウント
					}
				}
			}
		}
	}
	showMatch(manMarriage,womanMarriage);
	return 0;
}


12 January

SRM604 div2 easy

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12953

空でない文字列がいくつか渡される。
文字列を二分割してそれを入れ替えた時同じものに
なるものをカウントして返せ。

例:"tokyo","kyoto"
tokyo = to + kyo → kyo + to = kyoto
このようなのをカウント。

解法

Constraintsは文字列の数、文字列の長さがそれぞれ50である。
よって全探索でも50^3程度にしかならない。


反省

今回が本番初参戦だった。
開催が遅かったので30分寝過ごしてしまった。
練習の時、早く解くことを意識はしていたものの、時間制限を設けず
やっていたので本番で焦ってしまった。
初チャレンジもよく確認せず突っ込み-25点と
いろいろと惨敗だった。

なんだかんだやっぱり本番は楽しかったのでまた頑張りたい。



#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class FoxAndWord {

	public: int howManyPairs(vector<string> words) {
		int cnt=0;
		for(int i=0;i<words.size()-1;i++){
			for(int j=i+1;j<words.size();j++){

				if(words[i].size() == words[j].size()){
				for(int k=0;k<words[i].size();k++){
					if(words[i].substr(k+1) + words[i].substr(0,k+1) == words[j]){
						cnt++;
						break;
					}
				}}
			}
		}

		return cnt;
	}

};

09 January

SRM603 div2 medium

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12939

要素数がNの配列Aがある。その中からN/2個のペアを作る。
そのペアの中で積がX以上になる個数を求めよ。
なお、Xは負の数であることが保証されている。

解法

最初、A中に負の数の個数が何個あるか求めてから
個数が奇数か偶数かとかで場合分けしようとしたが、
ソートしてから、前から二個ずつペアにしていき、
その積がXを超えている個数をカウントしていけば解けることに途中で気づいた。
the productの意味を積だと知らず、少し手間取った。
英語は大事。



#include<iostream>
#include<vector>
#include<map>
#include<functional>
#include<algorithm>
#include<string>
#include<climits>

using namespace std;

class SplitIntoPairs{
public:
	int makepairs(vector<int> A,int X){
		sort(A.begin(),A.end());
		int cnt=0;
		for(int i=0;i<A.size()-1;i+=2)
			if((long long)A[i]*A[i+1] >= X)cnt++;
		return cnt;
	}
};