「2011年4月」の編集履歴（バックアップ）一覧に戻る

2011年4月 - (2011/05/06 (金) 16:09:28) の編集履歴(バックアップ)

---

2011/5/6

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1032
む、難しい。
一番簡単な方法は深さ優先探索である。
各再帰関数では、履修済みデータから現在選ぶことのできる科目を一つ選択しそれを選び、それを履修済みにして次の再帰へ行く。
という方法である。

この時、深さ優先探索で履修単位を基準にメモ化をしておくと計算量が抑えられる。
探索の途中で過去に通ったのと同じ履修単位の組み合わせになったら、そこで探索を打ち切るという方法である。

もっと簡単で賢い方法があるのではないか？
深さ優先探索はお馬鹿な方法なのではないか？

という疑問があるためにこの問題は難しくなる。

深さ優先探索+メモ化探索でチャレンジ、見事玉砕。
この問題の統計データを見るにほとんどがタイムリミットエクスパッション、時間切れ、私もその中の一人と。
うーん、どうやって解けばいいのかな？

見方を変えてみよう。
単位の取り方は全体で2＾20通りの組み合わせ。
これで、可能な単位の取り方不可能な単位の取り方というものを考えていけばいいのである。
つまり、幅優先探索、ということだろうか？
2＾20は約１０４万通り*実現可能な組み合わせかのチェックを導入する。

以下玉砕コード。

<stdio.h>

<set>

<vector>

<algorithm>
void setMap();
int saiki(int deep,int sum);

struct setCourse{

int size;
int d;
bool subjects[21];
bool operator<(const setCourse sc)const{
	for(int i=0;i<size;i++){
		if(subjects[i]<sc.subjects[i]) return true;
		if(subjects[i]>sc.subjects[i]) return false;
	}
	return false;
}
void setData(bool* ss,int s,int deep){
	size=s;
	for(int i=0;i<s;i++) subjects[i]=ss[i];
	d=deep;
}

};

int n,u;
std::set<setCourse> scs;
bool subjectOK[21];
int subjectC[21];
std::vector<int> subjectSet[21];
int ans;
std::set<setCourse>::iterator sit;

int main(){

scanf("%d %d",&n,&u);
while(n!=0 || u!=0)
{
	setMap();
	scanf("%d %d",&n,&u);
}

}

void setMap(){

scs.clear();
int m,t;
ans=200;
for(int i=0;i<n;i++){
	subjectOK[i]=false;
	scanf("%d %d",&subjectC[i],&m);
	subjectSet[i].clear();

	for(int j=0;j<m;j++){
		scanf("%d",&t);
		subjectSet[i].push_back(t);
	}
}
printf("%d\n",saiki(0,0));

}

int saiki(int deep,int sum){

if(sum>=u){
	ans=deep<ans ? deep:ans;
	return deep;
}
setCourse sc;
sc.setData(subjectOK,n,0);
sit=scs.find(sc);
if(sit!=scs.end()) return (*sit).d;


std::vector<int>::iterator it;
bool nextOK;
int d=200;
for(int i=0;i<n;i++){
	if(subjectOK[i]==true) continue;
	nextOK=true;
	it=subjectSet[i].begin();
	while(it!=subjectSet[i].end()){
		if(subjectOK[(*it)]==false){
			nextOK=false;
			break;
		}
		it++;
	}
	if(nextOK==false) continue;
	subjectOK[i]=true;
	d=std::min(d,saiki(deep+1,sum+subjectC[i]));
	subjectOK[i]=false;
}

sc.setData(subjectOK,n,d);
scs.insert(sc);
return d;

}

2011/5/6

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1014
ｎ個ある源泉からｍ個ある都市へパイプラインを引く問題。
源泉から都市への距離と都市間の距離が与えられるので、源泉から全ての都市へ最短距離でパイプラインをつなげよという問題。
ｎ個の源泉同士が距離0の辺でつながったグラフだと考え、後は源泉と都市をプリム法でつなげていけば解ける。

<stdio.h>

<set>

<algorithm>;

void setMap();
void saiki(int no,int sum);
int map[101][101];
std::set<int> connects;
int n,m,ans;
bool endFlag;

int main()
{

scanf("%d %d",&n,&m);
while(n!=0 || m!=0){
	setMap();
	scanf("%d %d",&n,&m);
}

}

void setMap(){

connects.clear();
endFlag=false;
ans=2000000000;
for(int i=0;i<n+m;i++){
	for(int j=0;j<m;j++)map[i][j]=0;
}
for(int i=0;i<n;i++)connects.insert(i);
for(int i=0;i<n;i++){
	for(int j=0;j<m;j++){
		scanf("%d",&map[i][j]);
	}
}
for(int i=0;i<m-1;i++){
	for(int j=i+1;j<m;j++){
		scanf("%d",&map[i+n][j]);
		map[j+n][i]=map[i+n][j];
	}
}


saiki(0,0);
printf("%d\n",ans);

}

void saiki(int no,int sum){

connects.insert(no);
if(connects.size()==(unsigned int)(n+m)){
	endFlag=true;
	ans=std::min(sum,ans);
	return;
}

std::set<int>::iterator it;
it=connects.begin();
int t=10000,nextNo=-1;
while(it!=connects.end()){
	for(int i=0;i<m;i++){
		if(connects.find(i+n)==connects.end() && map[*it][i]>0){
			if(t>map[*it][i]){
				t=map[*it][i];
				nextNo=i+n;
			}
		}
	}
	it++;
}

if(nextNo>0){
	saiki(nextNo,sum+t);
	if(endFlag==true) return;
}

}

2011/5/4

http://rose.u-aizu.ac.jp/onlinejudge/ProblemInfo.jsp?id=0528
最長一致文字列問題。
有名問題なので考え方を偶々知っており楽楽解答。

この問題の難しいところは回答者リストのランキング。
私のコードは実行速度0.0017秒でメモリ800ｋｂ使用という普通の解き方。

メモリ使用量ほぼ0、コード実行速度0.0000という人がいること。
どうやって計算量抑えたんだ？
メモリ使用量低減は状態遷移マシーンで解いて落としたのだと思う。
計算量はどうしたんだろ、かなり謎である？
この問題計算量を落とせばメモリが増え、メモリを抑えると計算量が増えるイメージあるんだけどな。
難しそう。
とりあえず私のコード。

<stdio.h>

<string.h>

int main()
{

char t1[4001],t2[4001];
int memo[2][4001];
int len1,len2;
int num;


while(scanf("%s",t1)!=EOF){
	scanf("%s",t2);
	len1=strlen(t1);
	len2=strlen(t2);
	num=0;
	for(int i=0;i<len1;i++)memo[0][i]=0;
	for(int i=1;i<=len2;i++){
		memo[i%2][0]= t2[i-1]==t1[0] ? 1:0;
		for(int j=1;j<len1;j++){
			if(t2[i-1]==t1[j]){
				memo[i%2][j]=memo[(i+1)%2][j-1]+1;
				num=memo[i%2][j]>num ? memo[i%2][j]:num;
			}else{
				memo[i%2][j]=0;
			}
		}
	}
	printf("%d\n",num);
}

}

2011/5/3

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0202
リンク先問題を解くコード。
少しだけ塩らしい高速化をしてるが基本的にはオーソドックスなメモ化探索で解法。
高速化も適当なのでコード実行速度は普通の6/95位。
１位の人は僕の３倍速いけどどうやって計算してるんだろ？
少し気になる。
これ１次元だから楽勝だけど、ｎ次元のメモ化とかどうするのか想像もつかないなあ。
実務だったらｎ次元のメモカだよなあ。

<stdio.h>

<algorithm>

void setSo();
void calc(int,int);

bool so [1000001];
bool sums[1000001];

int main(){

int n,x;
setSo();
scanf("%d %d",&n,&x);
while(n!=0 && x!=0){
	calc(n,x);
	scanf("%d %d",&n,&x);
}

}

void calc(int n,int x){

int foods[31];
for(int i=0;i<n;i++){
	scanf("%d",&foods[i]);
}
std::sort(foods,foods+n);
int p,max=0;
sums[0]=true;
for(int i=1;i<=x;i++){
	sums[i]=false;
	p=0;
	while(foods[p]<=i && p<n){
		if(sums[i-foods[p]]==true){
			sums[i]=true;
			break;
		}
		p++;
	}
	if(sums[i]==true && so[i]==true){
		max=i;
	}
}
if(max>0){
	printf("%d\n",max);
}else{
	printf("NA\n");
}

}

void setSo(){

for(int i=2;i<1000001;i++)
	so[i]=i%2;
int k;
for(int i=3;i<1000001;i+=2){
	if(so[i]==true){
		k=i*2;
		for(int j=i*3;j<1000001;j+=(k)){
			so[j]=false;
		}
	}
}
so[0]=true;
so[1]=false;
so[2]=true;

}

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0212&lang=jp
？？？
この問題解き方すら思いつかない。
探索でやったら組み合わせ数が爆発するし？
貪欲法はダメみたいだし。
ナップザックやメモ化が使えるとも思えないし。

2010/5/3

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2007
リンク先問題賢い方法を記述するとめんどくさくなりそうなので最悪の方法で解いてみた。
これより遅いタイムがあるらしいがこれより悪い方法を思いつかない。
私よりコード実行速度の遅い人はどんなコードを上げたのだろう？
気になる。
全探索より遅い方法なんて想像もつかない。

<stdio.h>

<algorithm>
int calcTuriSen(int s);
void setMap(int n);

int main()
{

int n;
scanf("%d",&n);
while(n!=0){
	setMap(n);
	scanf("%d",&n);
	if(n==0) break;
	printf("\n");
}

}

void setMap(int n){

int d[4],ans[4];
int sum,coinSum;
int ansSum=1000;
for(int i=0;i<4;i++) scanf("%d",&d[i]);


for(int i=0;i<=d[0];i++){
for(int j=0;j<=d[1];j++){
for(int k=0;k<=d[2];k++){
for(int l=0;l<=d[3];l++){
	sum=(i*10+j*50+k*100+l*500);
	if(sum-n>=0){
		coinSum=-(i+j+k+l);
		coinSum+=calcTuriSen(sum-n);
		if(coinSum<ansSum){
			ansSum=coinSum;
			ans[0]=i;
			ans[1]=j;
			ans[2]=k;
			ans[3]=l;
		}
	}
}
}
}
}
int coins[]={10,50,100,500};
for(int i=0;i<4;i++){
	if(ans[i]>0){
		printf("%d %d\n",coins[i],ans[i]);
	}
}

}

int calcTuriSen(int s){

int ans=0;
ans=s/500;
s%=500;
ans+=s/100;
s%=100;
ans+=s/50;
s%=50;
ans+=s/10;
s%=10;
ans+=s/5;
s%=5;
ans+=s;
return ans;

}

2011/4/30

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0116
リンク先問題を解くコード。
相当高速化したつもりのコードが下記。
しかし世の中の壁は厚かった。
実行速度２６位普通である。
どこかもう少し高速化できるらしい。

<stdio.h>
int map[503][503];

void setMap(int h,int w){

char t;
for(int i=1;i<=h;i++){
	for(int j=1;j<=w;j++){
		scanf(" %c",&t);
		if(t=='.'){
			map[i][j]=1;
		}else{
			map[i][j]=0;
		}
	}
}
for(int i=0;i<=h;i++)map[i][0]=map[i][w+1]=0;
for(int i=0;i<=w;i++)map[0][i]=0;

int lp,rp,cp,sum=0,max=0;
for(int i=1;i<=h;i++){
	for(int j=1;j<=w;j++){
		if(map[i][j]!=0) map[i][j]=map[i-1][j]+1;
	}
	for(int j=1;j<=w;j++){
		if(map[i][j]!=0){

			cp=map[i][j];
			lp=rp=1;
			while(map[i][j-lp]>=cp) lp++;
			while(map[i][j+rp]>=cp) rp++;
			sum=cp*(rp+lp-1);
			max=max<sum ? sum:max;
		}
	}
}
printf("%d\n",max);

}

int main()
{

int w,h;
scanf("%d %d",&h,&w);
while(h!=0 && w!=0){
	setMap(h,w);
	scanf("%d %d",&h,&w);
}

}

2011/4/25

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1049
リンク先問題を時折思い出して解法を考えるも全く計算量を落とす方法が分からない。
家の数が9件なら中学生でも着眼点一つで解ける。
10軒だと難しい。
計算量を落とす方向でコードを色々いじくってみる。
大体のデータで正しい答えを出すが、たまに間違った答えを出すコードとか出来たけど、必ず正しい答えを出すコードじゃないと駄目だしな。

<stdio.h>

<list>

<algorithm>

<set>

int calcLen(std::list<int> homePerm,int n);
void setMap(int n);
int map[10][10];
int ans;

int main(){

int n;
while(scanf("%d",&n)!=EOF){
	setMap(n);
}

}
int calcLen(std::list<int> homePerm,int n){

int hp[10];
int lens[10];
int i=0;
std::list<int>::iterator it;
it=homePerm.begin();
while(it!=homePerm.end()){
	hp[i]=(*it);
	it++;
	i++;
}


for(int i=0;i<n;i++) lens[i]=0;
for(int i=0;i<n;i++)
{
	for(int j=0;j<i;j++)
	{
		lens[i]=std::max(lens[i],lens[j]+map[hp[i]][hp[j]]);
	}
}
return lens[n-1];

}

void saiki(std::list<int> homePerm,int n,int deep){

if(n==deep){
	if(ans==-1){
		ans=calcLen(homePerm,deep);
	}else{
		ans=std::min(ans,calcLen(homePerm,deep));
	}
	return ;
}
int tempAns=-1;
std::list<int> homePermCand[11][100];

int ansCount[11];
for(int i=0;i<11;i++) ansCount[i]=0;

std::list<int>::iterator it;
std::list<int>::iterator it2;
int t;

bool endFlag=false;
int tempPerm[11];
it=homePerm.begin();
for(int i=0;it!=homePerm.end();i++){
	tempPerm[i]=(*it);
	it++;
}

bool skipFlag;
for(int k=0;k<n;k++)
{
	skipFlag=false;
	for(int l=0;l<deep;l++){
		if(k==tempPerm[l]) skipFlag=true;
	}
	if(skipFlag==true) continue;
	it=homePerm.begin();
	endFlag=false;
	while(endFlag==false)
	{
		it2=homePerm.insert(it,k);
		t=calcLen(homePerm,deep);
		if(tempAns==-1){
			tempAns=t;
			homePermCand[k][ansCount[k]]=homePerm;
			ansCount[k]++;
		}else if(tempAns==t){
			homePermCand[k][ansCount[k]]=homePerm;
			ansCount[k]++;
		}else if(tempAns>t){
			tempAns=t;
			homePermCand[k][0]=homePerm;
			ansCount[k]=1;
		}
		
		homePerm.erase(it2);
		if(it==homePerm.end()){
			endFlag=true;
		}else{
			it++;
		}
	}
}
for(int k=0;k<deep;k++){
for(int i=0;i<ansCount[k];i++){
	saiki(homePermCand[k][i],n,deep+1);
}
}

}

void setMap(int n){

for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
		//データの読み込み
		scanf("%d",&map[i][j]);
	}
}
for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
		//より遠ざけたい人を基準に
		map[i][j]=map[j][i]=std::max(map[i][j],map[j][i]);
	}
}
ans=-1;
std::list<int> homePerm;

homePerm.clear();
if(n==1){
	printf("0\n");
}else{
for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
		if(i!=j){
			homePerm.clear();
			homePerm.push_back(i);
			homePerm.push_back(j);
			saiki(homePerm,n,2);
		}
	}
}
printf("%d\n",ans);
}

}

2011/4/13

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1049
リンク先は恐ろしく正答率の低いプログラマ向けの問題。
長期間一人しか正答者がいなかった難問。
正答者の数が増えたのは最近である。
統計情報を見ても不正解でグラフが真っ赤。

といっても世間的にはそんなに難しくはない問題なのかも。
本当に実力のある人は北京大学のオンラインジャッジとか、Google主催のオンラインジャッジ（ネット上でプログラマ向けの大会や問題集を扱ってるサイト）にいるから世間的にはたいしたことないのだろう。

AOJには実力のあるプログラマがそんなにいないから正解率が低いにすぎない。
AOJに集まる人にとっては難問だった、程度にすぎないのかも。

私もこの問題に挑戦。
この問題世間的には簡単に分類されるのだろうけど、私には難しく答えが出せない。

正しい答えを出すところまではいってるはずなんだけど、実行時間が長すぎて不正解を喰らう。
コードを効率化する方法がわからない。

家の数が１０軒でも全探索で10！*45程度の計算量　３６０万*45回の計算量になる。
どうやって計算量を落とせばいいんだ？

<algorithm>

<stdio.h>
void setMap(int n);

int main(){

int n;
while(scanf("%d",&n)!=EOF){
	setMap(n);
}

}

void setMap(int n){

int map[10][10];
for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
		//データの読み込み
		scanf("%d",&map[i][j]);
	}
}
for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
		//より遠ざけたい人を基準に
		map[i][j]=map[j][i]=std::max(map[i][j],map[j][i]);
	}
}
int lens[10];//ある並びで家が並んだ時の各人の家の位置
int *hp=new int[n];/各人の家の並び順
int min=2100000000;//21億
for(int i=0;i<n;i++) hp[i]=i;

do{
	for(int i=0;i<n;i++) lens[i]=0;
	//各人の家が特定の並び順になった時、家をぎちぎちに詰めた場合の最短の長さを求める処理
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<i;j++){
			lens[i]=std::max(lens[i],lens[j]+map[hp[i]][hp[j]]);
		}
	}
	min=std::min(lens[n-1],min);
}while(std::next_permutation(hp, hp+n));//家の全ての並び順を求める
printf("%d\n",min);//答え
delete [] hp;

}

2011/4/4

http://dixq.net/rp/
今日からリンク先を参考にSTG作りを開始。
今日はボードの表示まで完了。

良いサイトである。
設計図をきちんと引いてゲームを作るとどれだけうれしいかが実感できる導入。
多人数で開発を分担できるプログラム開発とは何かが分かる設計。
ゲーム作りのみならず、プログラムを書く時cppファイルをどう分けていくかというアプリ開発の基本が身に付く感じ。
しかも段階を追って学習できるので、C++の基礎が終わっている人なら一人でも学習できる親切設計。
学習に必要な時間も決して長くはない。
解説が高校生でもわかるほどにやさしい。
これで無料！
驚くばかりにいい感じのサイトである。

名前　堀江伸一
住所　兵庫県加古川市加古川町南備後79-16

2011/4/5

http://dixq.net/rp/
今日は敵を表示させてみようまでコードを書く。
うーん理解しながら勉強すると時間がかかるなあ。
前半結構手間の多い処理記述が中心だけど、全ては後半楽をするための処理。
なのだ。