SRM573,574 Div1Medium

今日から真面目に問題を解くことにする。

573Med(450)
解法：どうみてもDijkstraやるだけ
解法は自明だが、#includeし忘れたりiとh間違えたりpriority_queueの型間違えたりしててどうしようもなかった。どう考えても演習量足りない。質より量の練習をすべきかもしれない。

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<string>
using namespace std;
class SkiResorts{
	public:
	long long ijk[50][50];
	bool v[50][50];
	int ABS(int a){return max(a,-a);}
	long long minCost(vector<string>A,vector<int>b){
		int n=A.size();
		priority_queue<pair<long long,pair<int,int> > >Q;
		for(int i=0;i<50;i++)
			for(int j=0;j<50;j++)ijk[i][j]=999999999999999LL;
		for(int i=0;i<n;i++){
			Q.push(make_pair(-ABS(b[0]-b[i]),make_pair(0,i)));
			ijk[0][i]=ABS(b[0]-b[i]);
		}
		while(Q.size()){
			int at=Q.top().second.first;
			int h=Q.top().second.second;
			Q.pop();
			if(v[at][h])continue;
			v[at][h]=true;
			//printf("%d %d: %lld\n",at,h,ijk[at][h]);
			for(int i=0;i<n;i++){
				if(A[at][i]=='Y'){
					for(int j=0;j<n;j++){
						if(!v[i][j]&&ijk[i][j]>ijk[at][h]+ABS(b[j]-b[i])&&b[j]<=b[h]){
							ijk[i][j]=ijk[at][h]+ABS(b[j]-b[i]);
							Q.push(make_pair(-ijk[i][j],make_pair(i,j)));
						}
					}
				}
			}
		}
		long long ret=999999999999999LL;
		for(int i=0;i<n;i++)ret=min(ret,ijk[n-1][i]);
		if(ret==999999999999999LL)return -1;
		else return ret;
	}
};

574Med(450)
解法：どうみてもbitDPやるだけ
コーナーケースが存在することに気がつかないとWAしてしまう。あとは自明。

public class PolygonTraversal{
	public long count(int a,int []b){
		if(b.length==2)return 0;
		long dp[][]=new long[1<<a][a];
		int at=0;
		for(int i=0;i<b.length;i++){
			b[i]--;
			at|=(1<<b[i]);
		}
		dp[at][b[b.length-1]]=1;
	//	System.out.println(at+" "+b[b.length-1]);
		for(int i=0;i<(1<<a);i++){
			for(int j=0;j<a;j++){
				if(dp[i][j]==0)continue;
			//	System.out.println(i+" "+j);
				int L=(j+1)%a;
				int R=(j+a-1)%a;
				while(true){
				//	System.out.println(L);
					if((i&(1<<L))>0){
						break;
					}else L=(L+1)%a;
				}
				while(true){
				//	System.out.println(R);
					if((i&(1<<R))>0){
						break;
					}else R=(R+a-1)%a;
				}
				L=(L+1)%a;
				R=(R+a-1)%a;
				if((R-L+a)%a+1>=a-2)continue;
				for(int k=L;;k=(k+1)%a){
					if((i&(1<<k))==0)dp[i|(1<<k)][k]+=dp[i][j];
					if(k==R)break;
				}
			}
		}
		long ret=0;
		for(int i=0;i<a;i++)if((b[0]+1)%a!=i&&(b[0]+a-1)%a!=i)ret+=dp[(1<<a)-1][i];
		return ret;
	}
}

Div1Med Solved
34 -> 36 (+2)