PKU演習問メモ(4/7)

No. Title 分類・解法
1146 ID Codes Straight forward
1753 Flip Game Brute force
2159 Ancient Cipher String manipulation,Straight forward
2080 Calendar Straight forward
1154 LETTERS DFS
1159 Palindrome String manipulation,Dynamic Programming
1207 The 3n + 1 problem Straight forward
1107 W's Cipher String manipulation
1287 Networking Prim's algorithm
1315 Don't Get Rooked DFS


空きコマ中に学校からの更新。


以下問題概要、解説、ソースコードなど。

1146 ID Codes

問題概要

英小文字で与えられたID番号がある。与えられた文字列と同じ文字からなり、辞書順で与えられた文字列の次に来るものを出力せよ。そのような文字列が存在しない場合は"No successor"と出力せよ。

解法

C++の人はnext_permutationで。JavaとかC#の人は深さ優先探索などで。

1753 Flip Game

問題概要

4x4のマスにオセロの駒が置かれている。次の規則で駒をひっくり返すとき、全ての駒の色を揃えるのに必要な最小の手数を求めよ。不可能な場合は"Impossible"と出力せよ。

  • ある駒を選ぶ。その駒と、その駒の上下左右の駒を全て反転する。
解法

総当たり。2^16通りしかないので間に合う。このゲームには「ライツアウト」と言う名前がついていて必勝法があることが知られている。最短手数を求める方法はどうなんだろう。。。


確か上の一列を決めつければあとは一意にひっくり返す方法が定まったような。

ソースコード
int dy[]={-1,0,1,0,0},dx[]={0,1,0,-1,0};

int main()
{
  char b[4][5],t[4][5];
  rep(i,4)cin>>b[i];

  int ans=inf;
  rep(i,1<<16)
  {
    rep(j,4)strcpy(t[j],b[j]);
    rep(y,4)rep(x,4)if(1<<(y*4+x)&i)rep(d,5)
    {
      int ny=y+dy[d],nx=x+dx[d];
      if(ny<0||nx<0||ny&>=4||nx>=4)continue;
      t[ny][nx]=t[ny][nx]=='w'?'b':'w';
    }
    int cnt=0; rep(y,4)rep(x,4)if(t[y][x]=='w')cnt++;
    if(cnt==0||cnt==16)
    {
      int bit=0;
      for(int k=i;k;k>>=1)bit+=k&1;
      ans=min(ans,bit);
    }
  }
  if(ans!=inf)cout<<ans<<endl;
  else cout<<"Impossible"<<endl;

  return 0;
}

2159 Ancient Cipher

問題概要

アルファベットを別のアルファベットに対応させる暗号化を置換暗号と呼び、文字列の順序を入れ替える暗号化を順列暗号と呼ぶことにする。アルファベットの対応は1対1でなければならない。
与えられた文字列1から文字列2へ、置換暗号を施し、順列暗号を施すことで変換することが可能かを答えよ。文字列の長さは100を超えないものとする。


substitution cipher, permutationを直訳した。きちんとした訳語があるのか不明。

解法

置換暗号と順列暗号を施した前後で、「文字数の分布」は変化していない。
すなわち、1回出現する文字の種類の数、2回出現する文字の種類の数……は同一であり、
逆に文字数の分布が同一の時には対応する文字列を結ぶような暗号が考えられる。


よって文字数の分布を比較してやればよい。

ソースコード
int main()
{
  char s1[101],s2[101]; gets(s1); gets(s2);

  int c1[256]={0},c2[256]={0};
  for(int i=0;s1[i];i++)c1[s1[i]]++;
  for(int i=0;s2[i];i++)c2[s2[i]]++;
  map<int,int> S1,S2;
  rep(i,256){
    if(c1[i])S1[c1[i]]++;
    if(c2[i])S2[c2[i]]++;
  }
  cout<<(S1==S2?"YES":"NO")<<endl;

  return 0;
}

学校でやってたらコンパイラにgets使うなっておこられた。

2080 Calendar

問題概要

グレゴリオ暦閏年は4で割り切れる年でかつ、100で割り切れない年であるが、400で割り切れる場合は例外的に閏年である。
2001年1月1日からの経過日数が与えられる。このとき年月日と曜日を求めよ。


2010年は閏年ではない。

解法

年は西暦9999年を超えない(nは400万程度)ので日付を受け取る変数はintでおk.
なおかつナイーブに年を引き算していって間に合う。あとはミスに気をつける。

ソースコード
int day[12]={31,28,31,30,31,30,31,31,30,31,30,31};
char dname[7][15]={"Sunday","Monday","Tuesday","Wednesday",
		   "Thursday","Friday","Saturday"};

bool isleap(int y)
{
  return y%400==0||y%100!=0&&y%4==0;
}

int main()
{
  int n;
  while(cin>>n,~n){
    int year=2000,m=0,nmod=(n+6)%7;

    while(n<=365+isleap(year))n-=365+isleap(year++);//年
    while(n&<=day[m]+(isleap(year)&&m==1))
      n-=day[m++]+(isleap(year)&&m==1);//月
    cout<<year<<"-"<<(m+1<=9?"0":"")<<m+1<<"-"<<
      (n+1<=9?"0":"")<<n+1<<" "<<dname[nmod]<<endl;
  }
  return 0;
}

1154 LETTERS

問題概要

nxmマスのボードにアルファベットの大文字が書かれている。
ボードの左上から出発し、同じ文字は2度以上辿らないように上下左右に動いていくとき、訪れることのできる最大のマスの数を求めよ。

解法

n,mは20以下、アルファベットは26文字であるので普通の深さ優先探索で十分間に合う。
(それでも全てのアルファベット並べたケースは結構大きいかも?)

ソースコード
int h,w;
char bd[20][21];
bool u[256];

int rec(int y,int x)
{
  int ret=0;
  rep(d,4){
    int ny=y+dy[d],nx=x+dx[d];
    if(!ck(ny,h)||!ck(nx,w))continue;
    if(u[bd[ny][nx]])continue;
    u[bd[ny][nx]]=1;
    ret=max(ret,rec(ny,nx));
    u[bd[ny][nx]]=0;
  }
  return 1+ret;
}

int main()
{
  cin>>h>>w;
  rep(i,h)cin>>bd[i];

  u[bd[0][0]]=1;
  cout<<rec(0,0)<<endl;
  return 0;
}

1159 Palindrome

問題概要

元の文字列に何個か任意の文字を挿入して回文になるようにしたい。このとき必要な挿入する文字数の最小値を求めよ。

解法

元の文字列と、元の文字列を反転した文字列の最短共通部分列を取ればいいとぺりむさんに教わったので言われたとおりに書いた。

最短共通部分列を求める動的計画法の表であるが、5001*5001のintの配列を取るとMLEになるので、最新の二列分だけ保持するか、short型で宣言(2byteなのでおよそ50MB)する。

ソースコード
int l;
char str[5001],rstr[5001];
short dp[5001][5001];

int main()
{
	cin>>l>>str;
	strcpy(rstr,str); reverse(rstr,rstr+l);
	
	rep(i,l+1)dp[0][i]=dp[i][0]=i;
	
	for(int i=1;i<=l;i++)for(int j=1;j<=l;j++)
		dp[i][j]=min((str[i-1]==rstr[j-1]?1:2)+dp[i-1][j-1],
			min(dp[i][j-1],dp[i-1][j])+1);
	
	cout<<dp[l][l]-l<<endl;
	
	return 0;
}

1207 The 3n + 1 problem

問題概要

入力に対しnが1になるまで
n:=3*n+1(if n is odd)
n:=n/2(otherwise)
の操作を行うとき、現れる数字の数をa[i]とする。
二つの自然数が与えられる時aのiとjの間の項の最大値を求めよ。

解法

実装すればいい……んだけどj>iのケースが含まれるという謎仕様。
プログラムコンテストで一旦どんな能力を見たかったというのだろう。他に見るべきものあるだろう。

1107 W's Cipher

問題概要

鍵k1,k2,k3と暗号文が与えられる。これは次のような暗号化をした文字列である。これを復号せよ。
a-iの文字をグループ1、j-rをグループ2、その他(s-zと_)をグループ3とする。
グループ1の文字をそれぞれk1ずつ左にずらす。(グループ1番目がk1番目の文字になる)
グループ2, 3についても同様の操作を行う。
ki<=100とする。

解法

グループ毎にそれぞれの文字の出現場所を記憶しておき、ずらす。
配列に入れたら何か添え字がややこしくなったorz
kiは文字列長より長くなりうるので%演算子で剰余を取る場合負にならないよう気をつける。

ソースコード
int k[3];
int n[3],p[3][99];
char str[99],ans[99];

char sft(int g,int cur)
{
	return str[p[g][(cur+n[g]*k[g]-k[g])%n[g]]];
}

int main()
{
	while(cin>>k[0]>>k[1]>>k[2],k[0])
	{
		cin>>str;
		int l=strlen(str);
		rep(i,3)n[i]=0;
		
		rep(i,l)
		{
			if('a'<=str[i]&&str[i]<='i')p[0][n[0]++]=i;
			else if('j'<=str[i]&&str[i]<='r')p[1][n[1]++]=i;
			else p[2][n[2]++]=i;
		}
		
		ans[l]=0;
		int cur[3]={0};
		rep(i,l)
		{
			char c;
			if('a'<=str[i]&&str[i]<='i')c=sft(0,cur[0]++);
			else if('j'<=str[i]&&str[i]<='r')c=sft(1,cur[1]++);
			else c=sft(2,cur[2]++);
			ans[i]=c;
		}
		cout<<ans<<endl;
	}
	return 0;
}

1287 Networking

問題概要

与えられたp個の地点を全て直接または間接的につながっているようケーブルで結びたい。ケーブルの接続の仕方の候補はm個で、開始地点の番号、終端地点の番号、距離で与えられ、全ての地点が結ばれる方法が存在することが保証されている。
この時全ての地点をつなげるために必要な最小のケーブルの長さを答えよ。

解法

プリム法。サンプルを見ればわかるが、エッジの重複がありうるので、同じ地点間を結ぶ候補は入力の際に一番短いものだけをもつようにしておく。

ソースコード
int main()
{
	int p,r;
	while(cin>>p,p)
	{
		cin>>r;
		int d[p][p]; rep(i,p)fill(d[i],d[i]+p,inf);
		rep(i,r)
		{
			int a,b,c; cin>>a>>b>>c; a--,b--;
			d[b][a]=d[a][b]=min(d[a][b],c);
		}
		
		bool V[p]; fill(V,V+p,0);
		priority_queue<pi> Q; Q.push(mp(0,0));
		int ans=0,vis=0;
		while(!Q.empty())
		{
			int cur=Q.top().second,c=Q.top().first;
			Q.pop();
			
			if(V[cur])continue;
			V[cur]=1; vis++; ans-=c;
			if(vis==p)break;
			
			rep(i,p)if(!V[i]&&d[cur][i]!=inf)
			Q.push(mp(-d[cur][i],i));
		}
		cout<<ans<<endl;
	}
	return 0;
}

1315 Don't Get Rooked

問題概要

nxn(n<=4)のチェス板に駒の進めないマスがいくつかある。このチェス板にルークを互いに取れないように置くときに、置くことの出来る最大の個数を求めよ。


問題のタイトルはチェスの駒のルークとだまされる(?)のrookedを掛けているのかな?英語不得手なのでよくわからない。

解法

探索空間は非常に狭いので深さ優先探索などで。マスが16個しかないからパターンを全列挙しても通る気がする。というかそっちのほうが簡単に書ける気がしてきたorz

ソースコード
int n,ans;
char bd[4][5];

bool ck(int y,int x)
{
	if(bd[y][x]=='X')return 0;
	for(int i=y;i>=0&&bd[i][x]!='X';i--)if(bd[i][x]=='O')return 0;
	for(int i=y;i<n&&bd[i][x]!='X';i++)if(bd[i][x]=='O')return 0;
	for(int j=x;j>=0&&bd[y][j]!='X';j--)if(bd[y][j]=='O')return 0;
	for(int j=x;j<n&&bd[y][j]!='X';j++)if(bd[y][j]=='O')return 0;
	return 1;
}

void rec(int y,int x)
{
	if(x>=n)x=0,y++;
	if(y>=n)
	{
		int cnt=0;
		rep(i,n)rep(j,n)if(bd[i][j]=='O')cnt++;
		ans=max(ans,cnt);
		return;
	}
	
	if(ck(y,x))
	{
		bd[y][x]='O';
		rec(y,x+1);
		bd[y][x]='.';
	}
	rec(y,x+1);
}

int main()
{
	while(cin>>n,n)
	{
		rep(i,n)cin>>bd[i];
		ans=0; rec(0,0);
		
		cout<<ans<<endl;
	}
	return 0;
}