naoya_t@hatenablog

いわゆるチラシノウラであります

TCO17 Algorithm Round 2C

れじったけど起きられなくて
タイムシフト参戦

結果 --- 0pt(出てたら青落ち確定だったか)

Easy <250> CanidsSeesaw

狐を軽い順にシーソーに乗せていった時が狐㌠の最小スコア、重い順に乗せていった時が最大スコア、で、kがその区間にない場合は不可能、というのはすぐに分かるんだけど
何をどう並べたら丁度kになるのか、どう並べてもkを飛び越してしまってk回ちょうどは無理というケースがあるのか分からない。
n=11ぐらいまでならnext_permutation()で全パターンを愚直に試すことだって出来るけれど。
ああ。
permutationを二分探索できないかな
と思って、permutation Aとpermutation Bの丁度とは言わなくても真ん中辺りのpermutationを返す関数が書ければいいのか、と思っておもむろに書き始めて
(next_permutation()する前とした後でスコアが同じか、した後の方が大きいことを仮定してるが良いのか?)
時間内にちゃんと書けなくて終了;
その後1時間ぐらいのデバッグとSystem Test試行の繰り返しで最終的には通せたけど、「これでも通るんだ…」という印象。

通せたところでTLネタバレ解禁してみたら、なるほど、隣接項のswapでは累積和が一箇所しか変わらない=スコアが1増える可能性があるだけ(というかスコア変動は高々1)なことを利用して、昇順状態(最小スコア)から降順状態(最大スコア)に向けてバブルソートをしていけば、最小スコア≦k≦最大スコアなら必ず、バブルソートの途中のどこかでスコアがKちょうどになるからそれを返せば良い、と。

バブルソート方式に書き直してコードもすっきり。AC。
gist.github.com

元の「これでも通るんだ…」コードはこんな感じ。
gist.github.com

Medium <500>

開いてない

Hard <1000>

開いてない