ハル研究所プログラミングコンテスト2012

ハル研究所プログラミングコンテスト2012の参加記
結果は学生部門5位、総合6位でした。
工夫したこととか書いていきます。
・乱数の種を変えたりして実験したら最適解はトゲを踏んだり待機しないっぽいのでdist[x][y][トゲの周期][アイテム]で探索
・最初BFSしてたけどA*の方が速いのでそっちに切り替え
・ヒューリスティックはトゲを無視した最短路
・よく考えると行動した後の推定値の変動は+0,+1,+2のいずれかなのでヒープを使わず、バケットを4個用意して循環させて使い優先度付きDFSする
その他高速化の工夫
・とりあえずループ展開して条件判定を減らす
・距離テーブルのサイズが大きいので最初に全て初期化した後は更新箇所を記録しておきそこだけ初期化する
・配列が大きくなるならintではなくcharで宣言してキャッシュに載りやすくする（2倍ほど速くなって驚愕）
・hoge[24][24]とかはhoge[24][32]とするとコンパイラがシフトで最適化してくれる
・距離テーブルは一次元配列として宣言する
こんな感じでマクロを使ってアクセスしメモリを詰めて使用する

uchar dist[Constant::FIELD_WIDTH_MAX*Constant::FIELD_HEIGHT_MAX*Constant::SPINE_TURN_CYCLE*(Constant::SPINE_TURN_PAUSE+1)];
#define DIST(x,y,c,p) (dist[(((((x)*height+(y))*Constant::SPINE_TURN_CYCLE)+(c))*(Constant::SPINE_TURN_PAUSE+1))+(p)])

上下左右に移動する場合その中心座標のアドレスを計算しておくと移動先のアドレスは定数オフセットでアクセスできるので演算命令を減らせる。
オフセットは探索前に計算

const int down = Constant::SPINE_TURN_CYCLE*(Constant::SPINE_TURN_PAUSE+1);
const int right = height*Constant::SPINE_TURN_CYCLE*(Constant::SPINE_TURN_PAUSE+1);

中心座標のアドレスを計算したら上下左右のアドレスはオフセットで計算できる

p[-down]
p[-right]
p[right]
p[down]

Facebook Hacker Cup 2013 Qualification Round

Beautiful strings
やるだけ

void lower(string &s){
	REP(i,s.size()){
		if('A'<=s[i]&&s[i]<='Z')s[i] += 'a'-'A';
	}
}
int main(){
	int m;
	cin>>m;
	cin.ignore();
	REP(i,m){
		string s;
		getline(cin,s);
		lower(s);
		map<char,int> c;
		map<char,int>::reverse_iterator it;
		REP(j,s.size()){
			if(s[j]<'a'||'z'<s[j])continue;
			++c[s[j]];
		}
		vector<int> v;
		for(it=c.rbegin();it!=c.rend();++it){
			v.push_back(it->second);
		}
		sort(v.begin(),v.end(),greater<int>());
		int ans=0,b=26;
		REP(j,v.size()){
			ans += b*v[j];
			b--;
		}
		cout<<"Case #"<<i+1<<": "<<ans<<endl;
	}
	return 0;
}

Balanced Smileys
DPするだけ

bool dp[101][101];
int main(){
	int m;
	cin>>m;
	cin.ignore();
	REP(i,m){
		memset(dp,false,sizeof(dp));
		dp[0][0]=true;
		string s;
		bool colon=false;
		getline(cin,s);
		REP(j,s.size()){
			if(s[j]=='('){//+1
				for(int k=0;k<100;k++){
					dp[j+1][k+1] = dp[j][k];
				}
			}else if(s[j]==')'){//-1
				for(int k=1;k<=100;k++){
					dp[j+1][k-1] = dp[j][k];
				}
			}
			if(s[j]!='('&&s[j]!=')'||colon){//0
				for(int k=0;k<=100;k++){
					dp[j+1][k] |= dp[j][k];
				}
			}
			colon = s[j]==':';
		}
		char *ans = dp[s.size()][0]?"YES":"NO";
		cout<<"Case #"<<i+1<<": "<<ans<<endl;
	}	
	return 0;
}

Find the Min
最初のk個の後はk+1周期で同じのが続くのでそれらを計算。
setだと最初のk個で重複があると死ねるからk個前までに使われてるやつをmapで持っといた。
基本は0,1,2,・・・ってな風に小さい値から割り当てていくけど
添え字が進むことによって今見ている値よりも小さい値が使用可能になったらそっちを使う。

int main(){
	int T;
	cin>>T;
	REP(i,T){
		map<ull,int> m;
		vector<ull> v;
		vector<ull> cycle;

		ull n,k;
		ull a,b,c,r;
		cin>>n>>k;
		cin>>a>>b>>c>>r;
		ull val=a;
		REP(j,k){
			v.push_back(val);
			++m[val];
			val =(b*val+c)%r;
		}
		ull cur=0;
		while(m.find(cur)!=m.end())cur++;
		REP(j,k+1){
			if(0<j && --m[v[j-1]]==0){
				m.erase(v[j-1]);
				if(v[j-1]<cur){
					cycle.push_back(v[j-1]);
				}else{
					cycle.push_back(cur);
					while(m.find(++cur)!=m.end());
				}
			}else{
				cycle.push_back(cur);
				while(m.find(++cur)!=m.end());
			}
		}
		cout<<"Case #"<<i+1<<": "<<cycle[(n-k-1)%(k+1)]<<endl;
	}
	return 0;
}