hotpepsiの練習帳

SRM 545

01:45

Div1 Easy (275) StrIIRec

問題

• 長さがNの文字列Sの各文字をS[x]で表す。
• 0 <= i < j < NにおいてS[i] > S[j]が成り立つ個数がスコアとなる。
• aから順にN個のアルファベットを使った文字列で、
• 与えられた文字列minStrよりも辞書順で小さくなく、
• スコアがminInv以上で、辞書順最小の文字列を求める。

方針

• アルファベットを逆に並べたものが最大のスコア N*(N-1)/2
• 全体としては、辞書順でminStr以上となる文字列を、手戻りが少ないように探す
• minStrをprefixとして、そのあとに辞書順最大の文字列を加えてみて、スコアを計算する
• もしminInv以上ならば、解が存在するということなので、prefixを固定して、残りの部分がminInv以上になるまで辞書順最小から探索する
• minInvを下回るのならば、そのprefixではだめなので、最後の文字を+1して、そのあとに辞書順最大の文字列を加える
• それでもだめならprefixを1文字減らして、最後の文字を+1する、という操作を繰り返す
• prefixがなくなったら、不可能なので終了
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_545/StrIIRec.cpp

結果

0pt 480th rating 1299 -> 1278

文字列の探索はけっこうしんどい。

証明してないが、スコアがminInvちょうどのときは、その文字列を返してしまってよさそう。