筋トレ8日目: SRM563 Div1Easy "FoxAndHandle"

■時間

一時間

■問題 SRM563 Div1 Easy "FoxAndHandle"

ある文字列S（eg: "ceil"）の順番を入れ替えて（eg: "eilc"）、元の文字列と組み合わせて作る文字列（eg: "ceeililc","ceileilc",...）について考える。

この時、ある目的の文字列H（eg: "fedcbafedcba"）があった場合に、これを作れる元の文字列Sの中で一番辞書式順序の小さい文字列はなにか（eg: "afedcb"）

■試した解き方

一瞬、分からなくなってとりあえずDPで解き始めたが、例えば"zzaabbcc"みたいなケースでは時間オーバーする可能性が高いと判断して断念。

ある場所である文字を選んだ時に、その右に残っている文字で、まだ選んでいない文字が全てカバーできるか、を判断するためのマトリクスを作ることを考える。

例えば文字列がzzaabbccの場合：

idx:	0	1	2	3	4	5	6	7
S[idx]:	z	z	a	a	b	b	c	c
a	2	2	1	0	0	0	0	0
b	2	2	2	2	1	1	0	0
c	2	2	2	2	2	2	1	0
z	1	0	0	0	0	0	0	0

まだ文字をなにも選んでいない時には必要文字数は(a=1, b=1, c=1, d=1）である。
マトリクスを見れば、最初の文字として「a」を選ぶことは不可能だということはO(m)（mは文字の数）で分かる。
（aが生じるidx（2,3）では、zの数がzの必要文字数(1)より低いため）
そのため最初に選び得る文字はzであることが判断できる。
（唯一idx:0ではマトリクスの残り文字数が必要文字数以上であるため）
以降、必要文字数がマトリクスの残り文字数以上となる出来るだけ低い文字を選んで文字列に足していくだけ。
O(nm^2）で計算できる。

public String lexSmallestName(String S) {

//文字の種類と数数える

char cs[];
int nums[];
{
char numForC[]=new char[27];
int numCs=0;
for(int i=0;i<S.length();i++){
if(numForC[(int)S.charAt(i)-'a']==0)
numCs++;
numForC[(int)S.charAt(i)-'a']++;
}
cs=new char[numCs];
nums=new int[numCs];
int j=0;
for(int i=0;i<numForC.length;i++){
if(numForC[i]>0){
cs[j]=(char)(i+'a');
nums[j]=numForC[i]/2;
j++;
}
}
}

//各idxより右にある各文字の数

int existenceMatrix[][]=new int[cs.length][S.length()];
for(int ci=0;ci<cs.length;ci++){
char c=cs[ci];
int num=nums[ci]*2;
for(int si=0;si<S.length();si++){
if(S.charAt(si)==c)
num--;
existenceMatrix[ci][si]=num;
}
}

boolean used[]=new boolean[S.length()];
StringBuffer buf=new StringBuffer();

int atIdx=0;

//文字列が埋まるまで

while(buf.length()<S.length()/2){

//いい文字をなるべく低い順に選ぶ

int ci;
int cPositionIdx=0;
for(ci=0;ci<cs.length;ci++) //いい文字とは・・・
if(nums[ci]>0){ //そもそも足す必要があり、
nums[ci]--;

boolean found=false; //マトリクスで利用可能文字数が必要文字数以上になる

for(int si=atIdx;si<S.length();si++){
if(S.charAt(si)==cs[ci] && !used[si]){
boolean remainingOK=true;
for(int j=0;j<cs.length;j++)
if(existenceMatrix[j][si]<nums[j]){
remainingOK=false;
break;
}
if(remainingOK){
cPositionIdx=si;
used[cPositionIdx]=true;
found=true;
break;
}
}
}
if(found)
break;

nums[ci]++;
}

//マトリクス更新（要らない）

for(int i=0;i<cPositionIdx;i++)
existenceMatrix[ci][i]--;
atIdx=cPositionIdx+1;

buf.append(cs[ci]);
}

return buf.toString();
}

1st submit:
OK

■Editorial
マトリクスをわざわざ事前に作ってはいないが、同じ解き方

■反省

・最初DPで解こうと思ってしまったのが誤り。
・一時間ぎりぎりでコーディング＋サンプルテストを通ったので、自分で色々テストする暇なくsubmitしてしまった。
・大会でのsuccess rateが60.4%なので、結構難しい問題だった？

■筋トレ記録
勝率67% (6/9)