CodeFestival2017 qualB F問題 - sigma425のブログ

F: Largest Smallest Cyclic Shift - CODE FESTIVAL 2017 qual B | AtCoder

この問題のおもしろい解法についてです。

解法1

文字列の集合を持って、「最小と最大を取り出し、この順に並べたものを新たに追加する」をやって最後に残ったものが答え.初期状態は"a"がA個,"b"がB個,"c"がC個.

解法1の正当性を証明するために、まずは次の解法を考えます.

解法2

再帰的な解法.
string solve(int A,int B,int C,string a,string b,string c) という関数を考える.
これは、文字列aを文字'a'だと思い込んで、(b,cも同様)問題を解いた時の最終的な答えを返す関数とします. なので元の問題の答えはsolve(A,B,C,"a","b","c").

内部では次のことをやります.

自明なケース

i) B+C==0 の場合
明らかにaをA個並べたものを返すしかありません.
ii) A==0 の場合
solve(B,C,0,b,c,"")を返します

まともなケース

int q = A/(B+C);
int r = A%(B+C);
string o = a*q;
if(r<=C){
	return solve(r,B,C-r,o+a+c,o+b,o+c);
}else{
	return solve(r-C,C,B-(r-C),o+a+b,o+a+c,o+b);
}

(string * int は string を int 回連結したものとします)

たとえば,
solve(6,3,1,"a","b","c") では、
solve(1,1,2,"aab","aac","ab")が内部で呼ばれ、

solve(3,3,4,"a","b","c") では、
solve("ac","b","c",3,3,1)が内部で呼ばれます.

これでちゃんとsolveが計算できていることを示します.自明なケースに関しては明らかなので、まともなケースについて考えます.

まず非自明なケースのsolveの引数a,b,c(文字列)は、次の条件†を満たします(これは再帰的に簡単にわかります *1 ).

†:どの文字列も,他のどの文字列のprefixではない.

この条件を満たす文字列集合Sに対して、一般に次のことが成り立ちます:

「
Sを辞書順ソート済みとしてS = {w_1,w_2,..,w_N} とする.この時、
a := w_i1 + w_i2 + .. + w_iI
b := w_j1 + w_j2 + .. + w_jJ
と置く(文字列の連結)と、
a < b ⇔ (i1,i2,..,iI) < (j1,j2,..,jJ) (添字の辞書順)
」

これは、†を満たしていることから、i1 ≠ j1 ならその時点でaとbのどちらが小さいかわかるということを考えるとわかります.

これはすなわち、Sの文字列を新たに一つの文字とみなして大小比較しても同じ結果が得られることを指しています.

元の問題に戻ると、これによってsolveを再帰的に呼ぶ時に常にa,b,cを一つの文字とみなしても元の問題が解けていることがわかります.

コードの内容に戻ると、まずaをできるだけ均等に(q+1がr個,qがB+C-r個)分割しています.こうすべきなのは、aの数が連続している部分の最長の長さがより長いとfの値が小さくなってしまうことからわかります(追記:‡不十分で、aaa,aaa,a より aaa,aa,aa の方がよいことを示していないあとで説明します).

なのであとは、さっきあげた例A=6,B=3,C=1でいくと、aa?,aa?,a?,a? (の?に適切にb,cを入れて,)並び替えてfを最小化するのが目的になります.

もしaaの後に全てcを置けるなら、そうでない状態よりfは大きくなる(aabから始まる文字列がなくなる)ので、そうすべきです.すると次の文字列はaac,ab,acしかなくなるのでこれで再起します(コード中のifの方です)

そうでない場合でも(elseの方),実はできるだけaaの後ろにcを詰め込んだほうがよいです(※).すると,次の文字列はaac,aab,abしかなくなるのでこれで再起します.

※の理由:
出てきうる文字列aab,aac,ab,ac は条件†を満たすので、1,2,3,4と置き直します.

「1,2,3,4からなる文字列sがあって、1と4が共存する場合、ある1と4が存在して、その1を2に、その4を3に書き換えることでf(s)をより大きくできる」
ことを示せば十分.

まずsの4をどれでもいいから一つ固定します.そこから(cyclicに)左に見ていってはじめに見つけた1を固定します.この4,1を3,2にすることを考えます.この文字列をtとおきます.

まず変更の結果tに1がなくなるケースでは、明らかにfは大きくなっています(f(s)は1から、f(t)は少なくとも2からはじまるので)

そうでない場合、
sのcyclic shift の内1からはじまるものの集合を考えると、これはf(s)を含みます. これらの文字列s'においては、さっき固定した1と4の間で切れることはありえません(つまり、1と4はs'にこの順に出てきます)

これらの候補に対応する(同じ分だけshiftした) t の文字列達を考えます.この集合は必ずf(t)を含みます.(tには1があり、かつ1からはじまるものをすべて含むため)

それぞれの対応するペア(s',t'と描きます)に対して、s' < t' を示します.
これが示せれば、f(t) > それに対応するs' ≥ f(s) となるのでOKです.

(s' < t' の証明)
さっきの太字の部分で主張したことから、
s' = ..1..4..
t' = ..2..3..
となるので、OK(おわり)

(※の理由おわり)

よってできるだけcをaa?に詰め込んだほうがいいことがわかったので、解法2の正当性も終わりです.

‡(aを均等にすべきな理由):
上の証明と似たような感じで、b,c,ab,ac,aab,aac,..は条件†を満たすので、aの数が偏っている(2以上違う)時は、その二つを固定してaの個数を平均化するのがいいことがわかる.

解法1の正当性

途中状態でsolve()の再帰と同じ状態になることがわかるので解法2と同じ出力になることがわかる.(ベースケースは明らか)

ちゃんと詰めたつもりなんですが、おかしいところがあったら教えてください.

*1:細かいですが、自明なケースiiによって実は満たさなくなるんですが、まあ本質的ではないです,例えば新たな引数をランダム文字列にしても良いので