c_Comp-Prog yukicoder No.145 yukiover

結構考察に時間が取られたけど最終的に自力ACできたので満足

問題

日本語なのでリンク先参照

考察

まず簡単のため、それぞれの文字に対して数値を振る。(下画像参照、~は左右の文字を除く間の文字全て)

https://gyazo.com/01a1b85059e1987c0f8a9d53fd82c1d4

こう数値を振ると、例えば756みたいな順番の文字列を作るよりは76を作った方が数が少なく、5を別のところに使えるので最大値を求められるということがわかるため、

7531を左から比較した時に7531より大きい広義単調減少の長さの文字列を作ってくださいという問題になる。

そうすると

8

77

76

755

754

7533

7532

75311

75310

を作ればいいことがわかる。

しかし前から貪欲をすると最終的に7531より辞書順で大きいものが作れるか確定しないため、後ろからyukiより辞書順で大きい文字列を作れる最大値を求めることにする。

下画像を参照すると、一番後ろで辞書順より大きい文字列を作れる個数が確定するため、それを順番に確定させていくと答えが導き出せる。

https://gyazo.com/20c92fb2cdf1c76249d645dfa1f70e62

code:solve.cpp

int main(){

string s;cin>>n>>s;

for(int i = 0; s.size() > i; i++){

bool ok = false;

for(int j = 0; 8 > j; j+=2){

ok = true;

break;

}

}

}reverse(dta,dta+9);

for(int i = 2; 7 > i; i+=2){

}

tans = ans;

}

}

振り返り

少しだけ考察すれば解けると思ったらだいぶ時間がかかってしまった...この問題解説するの難しすぎるし...