Hatena::Grouptopcoder

kuuso1の日記

2014-04-08

SRM591 Div2Med

| 23:43 | SRM591 Div2Med - kuuso1の日記 を含むブックマーク はてなブックマーク - SRM591 Div2Med - kuuso1の日記

同じ長さの文字列A,Bが与えられる。使われている文字はA~I。

同じ位置の文字を除いて、BがAの文字置換で生成されるようにできるのに必要な最小の文字数を求める。

下の例だと後ろ2文字を除いてA->Dと置換すればいいので答えは2。

A: AABC
B: DDDE

9文字なので9!=362880の置換を作って、全部試せばいい。

Aに含まれる文字とBに含まれる文字の対応が付くものだけで探そうとしてハマった。。

(例えば上の例で 'A'->'D','B'->'E'と定義して、'C'は行き先がないので'C'が出てくるところは

 問答無用で省く、という風にして置換を作ると、'A'を省くケースにdfsで到達するためには

 A側も文字の種類!だけ回さないといけないためO(N!*N!)になってた。)

Aに含まれない文字の行き先を考える必要はないので、それは除外してよい。

using System;
using System.Collections;
using System.Collections.Generic;

public class ConvertibleStrings {
	int ans;
	String Source;
	String SourceChar;
	String Trgt;
	public int leastRemovals(string A, string B) {
		int[] UsableChar=new int[9];
		for(int i=0;i<9;i++){
			UsableChar[i]=1;
		}
		HashSet<char> HC =new HashSet<char>();
		for(int i=0;i<A.Length;i++){
			HC.Add(A[i]);
		}
		SourceChar="";
		foreach(char c in HC)SourceChar+=c.ToString();
		
		Trgt=B;Source=A;
		ans=0;
		Dictionary<char,char> D=new Dictionary<char,char>();
		dfs(UsableChar,D,0);

		return A.Length-ans;
	}
	
	void dfs(int[] UsableChar,Dictionary<char,char> D,int now){

		bool chk=true;
		if(now==SourceChar.Length)chk=false;
		
		if(chk==false){
			int ans0=0;
			for(int j=0;j<Source.Length;j++){
				if(D.ContainsKey(Source[j]) && Trgt[j]==D[Source[j]])ans0++;
			}
			ans=Math.Max(ans,ans0);
			return;
		}
	
		for(int j=0;j<9;j++){
			if(UsableChar[j]==1){
				UsableChar[j]=0;
				D.Add(SourceChar[now],(char)('A'+j));
				dfs(UsableChar,D,now+1);
				D.Remove(SourceChar[now]);
				UsableChar[j]=1;
			}
		}
		return;
	}
}

next_permutationがあればループ回すだけだなぁ。作っておかなきゃ。

あとdfsの書き方ですが、テーブルを書き換えてdfs再帰で呼んで、書き換えたテーブルを戻すタイプの記述が好きです。