TopCoder SRM471 Div1（ノーコンテスト）

TopCoder 参加記録

24:00開始だとちょっと眠くなる。

Result

No Contest.


良かったのか悪かったのかｗ
多分2問通ってたろうからレートは上がってたと思うけど。


……Practice Roomで500も通った。ちょっと勿体無いなｗ

Easy PrimeSequences

問題

素数のうち、2で割った（余りは切り捨てる）商がまた素数になるものがある。（7->3など）
ある数が素数でなくなるまで2で割り続けて列を作るとき、この列の長さを「数Xに対する列の長さ」と呼ぶことにする。（23->11->5->2なら長さ4）


N以下の整数で、列の長さがD以上になるような数のうち最も大きいものを返せ。
そのような数が存在しないときは-1を返せ。
2≦N≦1000万
1≦D≦10とする。

試行錯誤

問題文読解に手間取る。うーん？列の長さがD以上で最大になるような数を求めよってことか？
サンプルもそんな感じっぽい。


書いてみる。列の長さを求める関数は適当にメモ化。
あれ？最後のサンプル合わないぞ。もう一回問題文を読み直そう。


どうも単に列の長さがD以上になる数らしい。見つけたらすぐにループを抜けるよう変更。おｋサンプルあった。最大ケースも余裕だよね送信。


最大ケー……ス100万じゃなくて1000万じゃねーか！！ばか！！
リサブミット。しぬる。200点は確保できたのでそこまで痛手ではないはず。

Medium ThirteenHard

問題

N個の都市があり、各都市間の距離が隣接行列の形で与えられるとき、以下の条件を満たしながら都市0から都市N-1に移動するときの最短時間を求めよ。
移動が不可能なときは-1を返せ。

  • 各移動にかかる時間をT[0],T[1],...,T[m]とすると、すべての0≦i≦j≦mなるi,jに対してT[i]+T[i+1]+...+T[j]が13の倍数にならない。

ただし、N≦25とする。

試行錯誤

今までの経路の長さを持ちながら探索だと思うけど、それらはmod 13でだけ考えればよい。
となると13!以下ぐらいにはなるのか？ん、いや違う。
新しい移動をi+1回目とすると、今までの区間の移動が合法なら、調べるのは

  • T[i+1]
  • T[i]+T[i+1]
  • T[i-1]+T[i]+T[i+1]

……

  • T[0]+T[1]+...+T[i+1]だけでよい。

↑そして、上の値を記憶しておく。

ということは経路のなかに0-12が出現したかどうかだけ覚えればいいからビットDP（ダイクストラ）になるのか。面白いなー。


書いた。全然値が合わない。
経路の合法性判定間違ってたのを探し出すのに20分くらいかかった。


提出しようと思ったらサーバが落ちて終了。
プラクティスで提出したら通ってたよ！100位くらいにはなってたんじゃないか？勿体無いね！

ソースコード
int dp[25][1<<13];

class ThirteenHard {
	public:
	int D(char c)
	{
		if('A'<=c&&c<='Z')return c-'A'+1;
		return c-'a'+27;
	}
	
	int calcTime(vector <string> city) 
	{
		int n=city.size();
		rep(i,n)rep(j,1<<13)dp[i][j]=inf;
		
		dp[0][0]=0;
		priority_queue<pair<int,pi> > Q; Q.push(mp(0,mp(0,0)));
		
		while(!Q.empty())
		{
			int cc=Q.top().first;
			int cur=Q.top().second.first,bit=Q.top().second.second;
			Q.pop();
			
			if(cur==n-1)break;
			
			rep(i,n)if(city[cur][i]!='#')
			{
				int d=D(city[cur][i]),nbit=1<<d%13,nc=cc-d;
				if(d%13==0)goto FAIL;
				
				//bit ck
				rep(j,13)if(bit&1<<j)
				{
					if((j+d)%13==0)goto FAIL;
				}
				
				rep(j,13)if(bit&1<<j)
				{
					nbit|=1<<(j+d)%13;
				}
				
				if(dp[i][nbit]<=-nc)goto FAIL;
				dp[i][nbit]=-nc;
				Q.push(mp(nc,mp(i,nbit)));
				
				FAIL:;
			}
		}
		
		
		int ans=inf;
		rep(i,1<<13)ans=min(ans,dp[n-1][i]);
		return ans==inf?-1:ans;
	}
};