Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2009-12-23

[][][] SRM456 13:15 はてなブックマーク -  SRM456 - 練習帳

実践2回目

Rating:872→983

Level1:224.00/250

Level2:0/500

Level3:0/1000

challenge:Level1を2人落として:50*2

合計324.00、room内8位

Level2を途中で諦めたのを激しく後悔する。「簡単にあきらめない」って精神衛生を保つ上でも重要だと痛感した。

(直接minStepを計算しようとする→簡単に諦める→探索でやろうとする→アルゴリズムはできる→それをコーディングする能力がない→簡単に諦める→終了後直接計算が実は簡単であることに気づく)

次回SRM457は日本時刻1/4,21:00~(予定)

Regisrationは同日18:00~

2009-12-21

[][][][] SRM163 10:31 はてなブックマーク -  SRM163 - 練習帳

173.04/250

#include <string>
#include <iostream>

using namespace std;

class Rochambo{
public:

int wins(string opponent){
	int ans=0;
	int len=opponent.length();

	for(int i=0;i<len;i++){</pp>
		if(i<=1 && opponent[i]=='S'){
			ans++;
		}else if(i>=2){
			if(opponent[i-2]==opponent[i-1]){
				if( opponent[i-1]==opponent[i]){
					ans++;	
				}
			}else{
				if(opponent[i-1]!=opponent[i] && opponent[i-2]!=opponent[i]){
					ans++;
				}
			}
		}	
	}
	return ans;
}
};

・3回目以降は具体的な手の出し方をプログラムに乗せなくてもいいんですね。見たまんまif分で分けています。

2009-12-20

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

116.63/250

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

using namespace std;

class PaperFold{
public:

int retVal(int a,int b){
    return max( (int)ceil(log10( (double)a/b)/log10(2)) ,0);
}

int numFolds(vector <int> paper, vector <int> box){

    int ans= min(retVal(paper[0],box[0])+retVal(paper[1],box[1]) ,retVal(paper[0],box[1])+retVal(paper[1],box[0]) ) ;

    cout << ans;

    return (ans<=8)? ans : -1;
}
};

・どこでどのような型になるかを意識せず苦労する。

→直感とコンピュータ内での計算はずれることがあるのでcoutなどで逐次検証する。

・(int)/(int)は(int)、(double)/(int)は(double)

・丸め誤差とか大丈夫だろうか・・・

・ceil関数(cmath)は

double ceil ( double x );

float ceil ( float x );

long double ceil ( long double x );

・max関数(cmath)は

template <class T>

const T& max(const T&, const T&);

だから

retValにおいて、ceil関数に入れた後int型に変換しないといけない

2009-12-19

[] endl,stringstream 07:32 はてなブックマーク -  endl,stringstream - 練習帳

・coutだと、「endl」か「flush」を使用した時点で、画面に出力され内部のバッファはクリアされる。したがって、その後、coutを使用してもそれまでの文字列が一緒に出てくることない。しかし、stringstreamは内容を出力しても、バッファはクリアされない。

・これを回避するには、なんらかの方法でss内のバッファをクリアしなければいけない。それが、

ss.str("");

である。str()というメンバ関数は、引数に指定された文字列でss内のバッファを上書きする。つまり、空の文字列で上書きすることによって、バッファをクリアするのである。

http://ppwww.phys.sci.kobe-u.ac.jp/~akusumoto/program/detail.php?d=c/10-other/sstream_trapより)

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

139.25/300

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

using namespace std;

class IsHomomorphism{
public:
vector <string> numBad(vector <string> sor, vector <string> tar, vector <int> map){
	int len=map.size();
	vector <string> ans;
	char c[10];
	
	for(int i=0;i<len;i++){</pp>
		for(int j=0;j<len;j++){</pp>
			ss.clear();
			if(map[sor[i][j]-'0']!=tar[map[i[map[j-'0'){
				sprintf(c,"(%d,%d)",i,j);
 				ans.push_back(c);
			}			
		}
	}
	return ans;
}
};

・mapは戻り値がintだから-'0'はいらない

・sor,tarはsor[i][j]で値を取り出すとchar型の変数が返ってくるから-'0'が必要

[][][] SRM455 06:18 はてなブックマーク -  SRM455 - 練習帳

SRM本番、手痛い洗礼を受ける

rating:0→872

Level1:218.10/250→Challengeされ撃墜される

問題の読み違え、南北への動きを完全に無視する。

Level2:229.34/500→Failed System Test

文字列Bが文字列Aより短い場合への対処の仕方が不十分だった。

Level3:0/1000→未完成

pseudo-randomを作るところまではできたが時間がまったく足りない

ということで、得点は入らず。

次回SRM456は日本時刻12/22,23:00~

Regisrationは同日20:00~

2009-12-15

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

142.18/250

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

using namespace std;

class Iditarod{
public:

int time(string s){

int h,m,d=0;
char ap='0';

sscanf(s.c_str(),"%d:%d %[A,P]M, DAY %d",&h,&m,&ap,&d);

//cout << h << '\n' << m << '\n' << d << '\n'; 
if(h==12){
	h=0;
}
if(ap=='P'){
	h+=12;
}

//cout << (d-1)*24*60+(h-8)*60+m << '\n';

return (d-1)*24*60+(h-8)*60+m;

}
int avgMinutes(vector <string> times){
	int sum=0;
	int len=times.size();
	
	for(int i=0;i<len;i++){</pp>
		sum+=time(times[i]);
	}

return (int)(((double)sum /len)+0.5);

}
};

・ミスはほとんどなかったのにこれくらいの点数になるのは、根本的な原因があるはず。

2009-12-13

[][][][] SRM159 13:45 はてなブックマーク -  SRM159 - 練習帳

142.58/250

using namespace std;

class FryingHamburgers{
public:
	int howLong(int p,int h){
		int ans=0;
		int ext=0;
		if(h==0){return 0;}
		if(p>=h){return 10;}
		else{
			ans+=5+5*(h-(h%p))/p;
			ext=p-h%p;
			ans+=5+5*((h-ext)-(h-ext)%p)/p;
		return ans;
		}	
	}
};

・割り算の値が整数のときに繰上げをどうすれば良いかがわからなくなった

[][][][] SRM158 13:09 はてなブックマーク -  SRM158 - 練習帳

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

using namespace std;

class BaseMystery{
public:

int baseChange(char* n,int base){
	int ans=0;
	int value=0;
	
	for(int i=0;n[i]!='\0';i++){	
		if(n[i]<='9'){
			value=(n[i]-'0');
		}else if(n[i]<='J'){
			value=(n[i]-'A'+10);
		}
		if(value<base){</pp>
			ans=ans*base+value;
		}else{
			return -1;
		}
	}
	return ans;
}


vector <int> getBase(string equation){
	vector<int> ans;
	
	char sa[10],sb[10],sc[10];
	int a,b,c=0;
	
	sscanf(equation.c_str(),"%[0-9,A-J]+%[0-9,A-J]=%[0-9,A-J]",sa,sb,sc);

	for(int i=2;i<21;i++){
		a=baseChange(sa,i);
		b=baseChange(sb,i);
		c=baseChange(sc,i);		
		if(a!=-1&&b!=-1&&c!=-1&&a+b==c){
			ans.push_back(i);
		}
	}
	return ans;

}

};

・baseChange関数がひどいコード。資源の再利用をしよとして失敗する例

charを単独で使わないほうがいいのかな

2009-12-10

[] n進数→10進数変換 02:03 はてなブックマーク -  n進数→10進数変換 - 練習帳

charは単なる1バイトの変数だから演算ができるのか

int val(char c){
   if('0'<=c || c<= '9'){
        return c-'0';
   }else if('A'<=c||c<='J'){
        return c-'A'+10;
   }else
        return -1;
   }
}

・bool isalpha(int)やbool isdigit(int)という関数もある

[][][][] SRM157 00:59 はてなブックマーク -  SRM157 - 練習帳

#include <vector>
#include <string>

using namespace std;

class Salary{
public:

double wtime(string b, string e,int wage){
	double ans=0;
	int bs=0;
	int es=0;
	int bt[3]={0};
	sscanf(b.c_str(),"%d:%d:%d",&bt[0],&bt[1],&bt[2]);
	int et[3]={0};
	sscanf(e.c_str(),"%d:%d:%d",&et[0],&et[1],&et[2]);

	bs=bt[0]*3600+bt[1]*60+bt[2];
	es=et[0]*3600+et[1]*60+et[2];
	if(bs<=21600){
		ans+=(min(es,21600)-bs)*wage*1.5;
	}
	if(bs<=18*3600 && es>=6*3600){
		ans+=(min(es,18*3600)-max(bs,21600))*wage;
	}
	if(es>=18*3600){
		ans+=(es-max(bs,18*3600))*wage*1.5;
	}
	return ans/3600;
}


int howMuch(vector <string> arrival, vector <string> departure, int wage){
	double ans=0;

	int len=arrival.size();
		for(int i=0;i<len;i++){</pp>
		ans+=wtime(arrival[i],departure[i],wage);
	}	
	return (int) ans;
}
};

<|

			

		

文字列から数字を取り出す方法 08:19 はてなブックマーク - 文字列から数字を取り出す方法 - 練習帳

SRM157 Div1 Level1より sscanfを用いる(scanfの入力がstringになったもの) c_strは最初の文字へのポインタを返す
int b[3]={0};
const string str="10:30:30";
sscanf(str.c_str(),"%d:%d:%d",&b[0],&b[1],&b[2]);

for(int i=0;i<3;i++){
 cout << b[i] << '\n';
}

2009-12-09

SRM156 Div1 Level1 21:56 はてなブックマーク - SRM156 Div1 Level1 - 練習帳

121.34/300

class BombSweeper{
public:
double winPercentage(vector <string> board){
    int flag=0;
    int win=0;
    int lose=0;
    const int n=board.size();
    string str(n,'.');

    board.insert(board.begin(),str);
    board.push_back(str);
    for(int k=0;k<n+2;k++){</pp>
        board[k].insert(board[k].begin(),'.');
        board[k].push_back('.');
    }
    for(int i=1;i<n+1;i++){</pp>
        for(int j=1;j<n+1;j++){</pp>
            if(board[i][j]=='B'){
                lose++;
            }else{
                flag=1;
                for(int x=-1;x<=1;x++){
                    for(int y=-1;y<=1;y++){
                        if(board[i+x][j+y]=='B'){
                            flag=0;		
                        }
                    }
                }
                if(flag==1){
                    win++;
                }
            }
        }
    }
    return (double) win/(win+lose)*100;
}
};

遅くなる原因

・文字列の挿入の仕方がわからなかった→もうわかった

・error segmentation faultの意味を考えてなかった

・for分の範囲をよく間違える

→バグを見つけるうまい方法を知りたい

2009-12-08

タブ 23:56 はてなブックマーク - タブ - 練習帳

・はてなの使い方がまだ良くわかってない

・タブとかスペースってどう入れるんだろ

→解決、今度はタブの文字数を変えたい

・もっと体裁を整えないと

SRM155 Div1 Level1(改良) 23:39 はてなブックマーク - SRM155 Div1 Level1(改良) - 練習帳

#include <vector>
#include <string>

using namespace std;

class PaternityTest{
public:
int isFather(const string& child, const string& mother,const string& father){
	int f=0;
	const int len=child.length();
	for(int j=0;j<len;j++){</pp>
		if( (child[j]!=father[j]) && (child[j]!=mother[j]) ){
			return 0;
		}else {
			if(child[j]==father[j]){
				f++;
			}
		}
	}
	return f>=len/2;
}

vector<int> possibleFathers(string child, string mother, vector <string> men){
	vector<int> ans;
	for(int i=0;i<men.size();i++){</pp>
		if(isFather(child,mother,men[i])){
			ans.push_back(i);
		}
	}
	return ans;
}
};

SRM155 Div1 Level1 23:17 はてなブックマーク - SRM155 Div1 Level1 - 練習帳

142.17/300

#include <vector>
#include <string>

using namespace std;

class PaternityTest{
public:
	vector<int> possibleFathers(string child, string mother, vector <string> men){
		vector<int> ans;
		
		int len=child.size();
		
		int flag=0;
		int m=0;
		int f=0;
		
		for(int i=0;i<men.size();i++){</pp>
			flag=1;
			m=0;
			f=0;
			for(int j=0;j<len;j++){</pp>
				if(!( (child[j]==men[i][j]) | (  (child[j]!=men[i][j]) & (child[j]==mother[j]) ) ) ){
					flag=0;
					break;
				}else {
				if(child[j]==men[i][j]){
					f++;}
				if(child[j]==mother[j]){
					m++;
				}
				}
			}
			if(f<len/2 || m<len/2){</pp>
				flag=0;
			}
			if(flag){
				ans.push_back(i);
			}
		}
		
		return ans;
	
	}

};

アルゴリズムが決まったらコードを書く前に紙に書こう。

上みたいにforの二重ループにするより中を関数にしたほうがいい。flagを立てずにreturnですぐに戻れる。

motherは半分以上マッチしていると仮定してよいのね・・・

複雑な条件式のところはド・モルガン律で簡単にできる

2009-12-07

SRM153 Div1 Level1 11:14 はてなブックマーク - SRM153 Div1 Level1 - 練習帳

153.07/250

#include <vector>

using namespace std;

class Inventory{
public:
	int monthlyOrder(vector <int> sales, vector <int> daysAvailable){
		
		double accumulate=0;
		int valid=0;
		int size=sales.size();
		for(int i=0;i<size;i++){</pp>
			if(daysAvailable[i]!=0){
				accumulate+=sales[i]*30/daysAvailable[i];
				valid++;
			}
		}
		return -(int)(-accumulate/valid)+1;
	}
};

availavleが0日の日の処理をいい加減にする

切り上げの処理を忘れる

一番最後の切り上げの処理の仕方は悪くない気がする

testしてから気づくのはだめだな・・・

SRM152 Div1 Level1 10:45 はてなブックマーク - SRM152 Div1 Level1 - 練習帳

159.55/250

#include <vector>

using namespace std;

class LeaguePicks{
public:
	vector<int> returnPicks(int position, int friends, int picks){
		vector<int> ans(0,0);
		int j=0;
		for(int i=0;;i++){
			if((j=position+2*i*friends)<=picks){
				ans.push_back(j);
			}
			else{
				break;
			}			

			if((j=2*(i+1)*friends-position+1)<=picks){
				ans.push_back(j);
			}
			else{
				break;
			}			
		}
		return ans;	
	}
};

・iを2倍するのを忘れる→vector関連のエラーが出る→vectorについての知識があやふや→vector関連の方にbugがあると勘違い→iの方に気づかない→時間かかる

SRM151 Div1 Level1 10:18 はてなブックマーク - SRM151 Div1 Level1 - 練習帳

218.02/250

#include <cmath>

using namespace std;

class Archimedes{
public:
	double approximatePi(int numSides){
		return numSides*sin(2*asin(1)/numSides);
	}
};

円に内接するn角形の周の長さからπを近似する問題

いいのかこれ・・・

2009-12-06

&&や|| 23:19 はてなブックマーク - &&や|| - 練習帳

&&や||は前から評価していって、全体の評価が確定した時点でそれ以降の評価をやめる

int false(){ puts("false"); return 0; }
int true(){ puts("true");  return 1;}

main(){
 if( false() && true() ){puts("Hello");}
}
<|

→"false"しか出力されない

			

		

SRM149 Div1 Level1 20:16 はてなブックマーク - SRM149 Div1 Level1 - 練習帳

160.14/250
#include <vector>

using namespace std;

class BigBurger{
public:
 int maxWait(vector <int> arrival, vector <int> service){
  vector<int> waitTime=service;
  waitTime[0]=0;		
  for(int i=1;i<=waitTime.size();i++){
   waitTime[i]=max(0,arrival[i-1]+waitTime[i-1]+service[i-1]-arrival[i]);
  }		
  int ans=0;
  for(int i=0;i<waitTime.size();i++){</pp>
   ans=max(ans,waitTime[i]);
  }
  return ans;
  }
};
テストの仕方とかがうまくなってきた

SRM148 Div1 Level1 19:21 はてなブックマーク - SRM148 Div1 Level1 - 練習帳

#include <string>
#include <vector>
#include 

using namespace std;

class CircleGame {
	private:
		void removeZero(string& work){
			while(true){
				string::size_type p =work.find('0');
				if(p==string::npos){break;}
				work=work.erase(p,1);
			}
		}

    public:
   	    int cardsLeft(string deck) {
            map<char,int> toNum;
            toNum['0']=0;
            toNum['A']=1; toNum['2']=2; toNum['3']=3; toNum['4']=4; toNum['5']=5;
            toNum['6']=6; toNum['7']=7; toNum['8']=8; toNum['9']=9; toNum['T']=10;
            toNum['J']=11; toNum['Q']=12; toNum['K']=13;

            for(int i=0;i<deck.length();i++){</pp>
            	if(deck[i]=='K'){
            		deck[i]='0';
            	}
            }
       		removeZero(deck);
       		bool flag=true;
       		while(flag&&deck.length()!=0){
       		flag=false;
            for(int i=0;i<=deck.length();i++){
            	if(toNum[deck[i+toNum[deck[(i+1)%deck.length()==13){
            		deck[i]='0';
            		deck[(i+1)%deck.length()]='0';
            		flag=true;
            	}
            }
            removeZero(deck);         
            }
        return deck.length();
		}
};
ソースを載せることにした mapの使い方は便利そう、enumだとどうすればいいんだろう stringのfindの使い方は覚えとくとよさそう

SRM146 Div1 Level1 08:32 はてなブックマーク - SRM146 Div1 Level1 - 練習帳

文字列とかvectorがなければ結構いけるのかも 275.72/300

SRM145 Div1 Level1 08:08 はてなブックマーク - SRM145 Div1 Level1 - 練習帳

vector <int> getDivision(vector <int> points) { int total = accumulate(points.begin(), points.end(), 0); } →accumulateという関数の使い方 0からスタートして、pointsの内容をどんどん足していく int d1[10] = {1,2,3,4,5,6,7,8,9,10}; vector<int> v1(d1, d1+10); int prod = accumulate(v1.begin(), v1.end(), 1, times<int>()); →掛け算、 for(int i=0;i<numEmployee;i++){</pp> →個数のミスはしなくなってきた 型変換にはstatic_cast int i=static_cast<int>(56.7); ソートする前の情報を残す方法:indexとペアにしてからソートする make_pair、sortが使える。ソートする前の情報はiの方に残っている vector<pair<int,int> > sorted(numEmployees); for (int i = 0; i < numEmployees; i++) sorted[i] = make_pair(points[i], i); sort(sorted.begin(), sorted.end(), compBonus);//最後はbool compBonus(const pair<int,int>& a, const pair<int,int>& b)へのポインタ、大小関係の定義

2009-12-05

SRM453.5 Div1 Level1 00:45 はてなブックマーク - SRM453.5 Div1 Level1 - 練習帳

目標:

vectorstringの使い方になれる

vector<vector<int> > maze(R ,vector<int>(C,0));

const int w=(int)maze.size();

const int c=(int)maze.size[0]();

→(int)をつけている人が多い、なぜ?

maze[i][j]=-1;で代入できる

0 <= tx && tx < w

→0からスタートだから前者はイコールあり、後者はなし

キーワード:幅優先