おはようございます、MMNMMです
おうどんのおいしい季節になりましたが皆さまいかがお過ごしでしょうか
今回は2017年10月8日にAtCoderで開催されたCODE FESTIVAL 2017 Qualification Round BのF問題について書きます
CODE FESTIVAL 2017 qual B F問題「Largest Smallest Cyclic Shift」
文字列$S$に対し、$f(S)$ を $S$ の巡回シフトのうち辞書順最小のものとします。 たとえば、$S=$
'babca'のとき、$S$ の巡回シフト ('babca','abcab','bcaba','cabab','ababc') のうち最小の'ababc'が $f(S)$ となります。あなたは、三個の整数 $X,Y,Z$ が与えられます。 あなたは、
'a'をちょうど $X$ 個、'b'をちょうど $Y$ 個、'c'をちょうど $Z$ 個含む文字列 $T$ を構成したいです。そのような文字列が複数存在する場合は、$f(T)$ を辞書順で最大化したいです。$f(T)$ の辞書順での最大値を求めてください。
(コンテスト問題ページから引用 あなたは整数が与えられますってなんですか)
コンテスト終了後に公開された想定解は $O(XYZ(X+Y+Z)^2)\sim O(S^5)$で、私が考えた解法(や、ほかの人のSubmit)では、$O(S^2)$や$O(S^2\log S)$くらいのものがありました。$(S$は文字列長$X+Y+Z$です$)$
私もSubmitしたときは一部を証明してこれで通るでしょ！みたいな心になっていて、他のところでも証明がされていなかったので(Twitterでakouryy1さんに手伝ってもらって)証明をしました
まずは、解法について説明をします
解法の説明
multiset解法 / 最小+最大解法
とてもシンプルで、頭がいいなあと思った解法です
(ソートされている)文字列の集合 $T:=\{s_1, s_2, \dots , s_n\}$ を用いて作ることができる文字列 $S$ に対する $f(S)$ の最大値を $F(T)$とします。
$F(T)=F(T\setminus\{s_1, s_n\}\cup\{s_1+s_n\})$ であること(直観的には正しいですが(たぶん)非自明です正しくないので、下に追記します)を用いて $T$ の要素を減らし、$T$ の要素が一つになったらそれを出力すればいいというものです。
$s_1<s_2$であるような場合はこれが正しいのは明らかで、$s_1=s_2$かついくつかの条件が成り立っている場合について証明するのが難しいように思います
式が正しくない話(追記 : 2017/10/19 22:20)
$F(T)=F(T\setminus\{s_1, s_n\}\cup\{s_1+s_n\})$ は一般に成り立ちません。
たとえば、$T=\{\textrm{'ab'}, \ \ \textrm{'abc'}, \ \ \textrm{'d'}, \ \ \textrm{'e'}\}$ のとき、この式に従うと
\{\textrm{'ab'}, \ \ \textrm{'abc'}, \ \ \textrm{'d'}, \ \ \textrm{'e'}\}\mapsto\{\textrm{'abc'}, \ \ \textrm{'abe'}, \ \ \textrm{'d'},\}\mapsto\{\textrm{'abcd'}, \ \ \textrm{'abe'}\}\mapsto\{\textrm{'abcdabe'}\}
となりますが、正しい $F(T)$ は $\textrm{'abceabd'}$ です。
$T$ がすべて1文字のときには正しい $F(T)$ が求められるような気がするのですけど、どうかはわかりません！(少なくとも今回の条件では正しい答えが出るようです)
再帰解法
(解説と同じように文字列 $S$ が $X$ 個あることを $X S$ で表します)
実験をしていくとかなり自然に思いつける解法だと思います
$X$aと $Y$bと $Z$cから作られる $f(T)$ は、accc....ccbbb...bbとaccc....ccbbb...bbbとaccc....cccの3種類の文字列からなるという予想がたつので、それを信じて計算、実装します。
aの後のcの個数は$\displaystyle\left\lfloor\frac{Z}{X}\right\rfloor$個か$\displaystyle\left\lfloor\frac{Z}{X}\right\rfloor+1$ 個あります。
aの後にcが$\displaystyle\left\lfloor\frac{Z}{X}\right\rfloor$個続くもの($X-(Z\ \%\ X)$ 個あります)の後に続くbの個数は$\displaystyle\left\lfloor\frac{Y}{X-(Z\ \%\ X)}\right\rfloor$個か
$\displaystyle\left\lfloor\frac{Y}{X-(Z\ \%\ X)}\right\rfloor+1$ 個です。
これを素直に書いて、出てきた3種類の文字列をまた新たなa, b, cと考えて再帰することで答えを出します
証明するべきものは、$f(T)$が上にあげた3種類の文字列以外を含んでいないことです。
再帰解法の停止条件と証明(追記 : 2017/10/11 15:30)
再帰解法では、$Y$ と $Z$ がどちらも $0$ になるときに終了します。
$Y$ と $Z$ がどちらも $0$ であるときは、$f(T)$ はその時点のaを繰り返したものになっているのですぐに求まります。
この解法では $X=0$ のときに0除算が発生しますが、$X\neq 0$ から途中で $X=0$ になることはない $(X\mapsto X-(Z\ \%\ X)>0)$ ため、始めに $X=0$ となっているときについて考えます。
始めから$X=0$であるとき、aはひとつもありません。なので、$(0$a$,Y$b$,Z$c$)$ を $(Y$b$,Z$c$,0$d$)$(dはなんでもいいです)のように見て、再帰を開始すれば正しい答えが出ます。(もし $Y$ も $0$ だったら初めから答えが出ています)
証明
証明の前に2つだけ作業をします。
一つは、再帰解法を単純化します(私は単純化したコードをSubmitしました)。
もう一つは、multiset解法と再帰解法の正当性が同値であることを示します。
最後に、再帰解法が正しいことを示します。
再帰解法 単純化
上の再帰解法ではaとbとcを同時に考えていましたが、aとcだけ考えればよくて、accc....cccとaccc....ccとbをそれぞれ新しいa, b, cにすればよいです(これの二回のステップをまとめると上の再帰解法になります)
multiset解法が正しいとき、再帰解法も正しいし、逆も
multiset解法を $Z$ ステップ進めると単純化した再帰解法の1ステップになるので、始めが同じであれば再帰解法の各ステップと同じ状態がmultiset解法で定期的に現れます。
なので、再帰解法で正しい答えが出るならばそのステップにmultisetが追いつくときにmultiset解法も正しい答えを出します。
また、multiset解法だけが正しい答えを出すとき、最後に再帰解法がmultiset解法と同じ状態になったときの再帰解法の$Z$について、multiset解法を$Z$ステップ適用する前にmultiset解法の答えが出ていることになりますが、$Z$は$T$の要素数より大きいのでこれはありえません。
よって再帰解法の正当性とmultiset解法の正当性は同値です。
再帰解法の正当性証明
$T:=\{X\ \ \textrm{'a'}, \ \ Y\ \ \textrm{'b'}, \ \ Z\ \ \textrm{'c'}\}$とします。
ここで、$Z$ と $X$について、$Z=Q\times X+R\ \ (0\leqq R<X)$ となるような整数 $Q, R$ が存在します。
このとき、$T':=\{R\ \ \textrm{'ac...}(Q+1\textrm{ 個})\textrm{...c'}, \ \ X-R\ \ \textrm{'ac...}(Q\textrm{ 個})\textrm{...c'}, \ \ Y\ \ \textrm{'b'}\}$ について、$T'$ からつくれる文字列は $T$ からつくれるため、$F(T')\leqq F(T)$ が自明に成り立ちます。
よって、$F(T)$ を構成する文字列は $\textrm{'ac...}(Q+k_i\textrm{ 個})\textrm{...c'}\ \ (i=1,...,X, \ k_i\geqq 0)$ の形のもの $X$ 個と、$\textrm{'b'}$ が $Y$ 個であり、$k_i$ について
\sum^X_{i=1}{k_i}=R
が成り立たなければなりません。
このとき、鳩ノ巣原理より $k_i=0$ となるような $i$ が存在することがわかるので、$F(T)$ には $\textrm{'ac...}(Q\textrm{ 個})\textrm{...c'}$ の形であり、その次に $\textrm{'c'}$ が続かないものが存在します。
$\textrm{'ac...}(Q\textrm{ 個})\textrm{...c'}$ を $A$ とおきます。
もし、$k_i\geqq 2$ であるような $i$ が存在するとき、$F(T)$ は
F(T)=A+s_0+A+s_1+\dots+A+s_k+A+\textrm{'cc...}(k_i\,\textrm{個})\textrm{...c'}+s_{k+1}+\dots+A+s_n
のようになっています。(ただし、$s_i$ はいずれも $A$ をちょうど($A+\textrm{'c'}$の形を除いて)含まず、$\textrm{'c'}$ から始まりません)
ここで、ある文字列 $S$ を次のように定義しましょう。
S:=A+s_0+A+s_1+\dots+A+\textrm{'c'}+s_k+A+\textrm{'cc...}(k_i-1\,\textrm{個})\textrm{...c'}+s_{k+1}+\dots+A+s_n
ここで、$S$ のすべての $A(A+\textrm{'cc...}(k_i-1\,\textrm{個})\textrm{...c'}\textrm{を除く})$ を $F(T)$ の $A(A+\textrm{'cc...}(k_i\,\textrm{個})\textrm{...c'}\textrm{を除く})$ と先頭から対応させることができます。
ある $S$ の $A$ について、その $A$ が先頭にくるように $S$ を巡回シフトさせた文字列 $S'$ と、その $A$ に対応する $F(T)$ の $A$ が先頭にくるように $F(T)$ を巡回シフトした文字列 $F(T)'$ の大小を考えます。
その $A$ が、$S$ において $A+\textrm{'c'}+s_k+A+\textrm{'cc...}(k_i-1\,\textrm{個})\textrm{...c'}$ の前にあるとき、明らかに $F(T)'<S'$ が成り立ちます。
( $A+\dots+s_{k-1}+A$ までは同じで、$s_i$ の定義から、その次の文字が $S'$ のほうが大きいので)
また、その $A$ が $A+\textrm{'c'}+s_k+A+\textrm{'cc...}(k_i-1\,\textrm{個})\textrm{...c'}$ の後にあるときも巡回しているので明らかです。
もし、$A$ が $s_k$ の中に存在しているなら、 $s_k$ の定義から $A+\textrm{'c'}$ の形をしているので、$F(T)<S'$ が成り立ちます。
$F(T)$ のどの巡回シフトも $F(T)$ 以上であることは $F(T)$ がある文字列の最小巡回シフトなので明らかです。
よって、$S$ のどの巡回シフトも $F(T)$ より大きいことがわかりますが、 これは $F(T)$ の定義に反します。
この矛盾は $F(T)$ に $A+\textrm{'cc'}$ の形の文字列が含まれているという仮定から導かれたので、 $F(T)$ には $A$ か $A+\textrm{'c'}$ の形の文字列しか存在しません。
元の'a'と'c'の個数から、$A$ と $A+\textrm{'c'}$ はそれぞれ $X-R$ 個と $R$ 個であることがわかり、再帰解法の正当性が示されました。
まとめ
難しかったですが、何とか示せたと思います(不備があったらお知らせください)
multiset解法と合わせて考察して、akouryy1さんがO(S)解法(！！！)を思いついたようなので、この問題もとっても広がりがある問題だなあと思っています
私はこの問題も本番中は通せなかったのでコンテスト中に通せるようになりたいですね
面白い問題を作ってくださったwriterの方々、コンテストを開いてくださったAtCoder社の方々、本当にありがとうございました