cafelier@SRM

SRM437

SRM | 02:22 |

SRM437 の成績・ソース (要ログイン) : WA/AC/- : ぐりぃでぃ

500開く

• 『ちょうどk種類の数字からなる、n以上の最小の自然数は？』
  • 1≦k≦10、nはlong longに入る程度

• DPかなー、と一瞬考え始めるも
• Random Coder Stats に「お前はGreedy Algorithmが苦手だ」と図星を突かれたばかりだったので、なんとかGreedyっぽく解こうとし始める。

• 上位桁はできるだけ n と揃えて…
• ある桁で n より大きい値にして…
• あとは自由なので一番小さいのを作れたらそれを返す
  • よしこれは俺基準ではGreedyっぽい

• というパターンで数を作ってやればいい。作れたらそれを返す
  • 「ある桁で n より大きい値にして…」をどの桁を変えるかどの値に増やすかでループする

• 「自由に一番小さくなるように」は、
  • "0000...0001234" みたいな感じに。
  • ちょうどk個使わないといけないので、
  • そこまでに使った数をrとして、使ってない方から小さいのk-r個を後ろに並べる

• 書いた。動かした
  • サンプル1個間違える
  • あー、nがk桁より小さい場合はちょうどk個使うためにはk桁まで拡張しないといけない

• 拡張した。サンプル通った。
• とりあえずsubmit

• まだ不安なので他の問題開く前にいくつか撃墜ケース考えてみる
  • 111111111111111, 10
  • 120000003456789 って出た！なにそれ！
    • 「ある桁で n より大きい値にして…」のループ上位桁から回してるよ俺！下からじゃないと

• あとはもう幾つか試してみたけど良さそう
• 再submit

250開く

• 『7桁くらいの数の桁をちょうどk回swapしてできる数の最大値を出せ。k回swapできない場合は-1。』

• とりあえずswapできない場合というのは、1桁の数か、あるいは0を最上位に持ってくるswapはできないから、最上位以外全部0だったらswapできない
  • ※これはまちがい
• というパターンをはじくコードを書いた。かけた。

• さて
• あとは…Greedyに！最大値を上に持ってくるように順々にswapしていけばいいのかな。
  • 「ちょうどk回」がくせ者だ
  • 最後swapが余ると降順ソートにならないで余ってしまう…

• ううむ困った。
• 考える。
• それだとダメな例は
• …
• …
• …考えてみたけど思いつかない。
  • たとえば123を2回だとどうしても321は作れない、たぶん
  • 余る場合は余らせて良さげ
• もうそれでいいや、250だからそのくらいじゃないと解けないよ

• そういうコードを書いた。サンプル通らない。
• あ、最大値を先頭に持ってくるときに、2つある場合はどっちでもいいわけじゃないのか。えーと、常に後ろ(下位桁)にある方を持ち上げたほうが大きくなるからそれで。
  • ※まちがい

• サンプル通った。OKOK。submit。

1000開く

• 500も250も大撃墜大会になりそうな問題だな…30分残ってるけど1000は開かずにひたすら撃墜例を考えていた方が絶対スコア的には得だ…
• だが1000を開く
• 『自然数a,b,cの桁を挿入したり削除したり変更したりしてa+b=cにする最小コスト』

• edit distance の DP をやたら面倒にしたようなものを書けばいいのでは…

• 20分悪戦苦闘

• なかなかうまくいかん。あきらめる。

250の撃墜例を考えるタイム

• さっきの、最大値が複数あるケースが気になるな。
• 実は下位桁からとってくるのがベストではないケース…

• 適当に思いついた n=325664, k=2
• …
• !!!!
• 325664 → 625634 → 665234 だめじゃん下位桁からとってきちゃ！

• うおおいきなり自分が撃墜された。あと6分。どう直す…？
• 最大値が複数場合は全通り探索。そのくらいのコードしか書ける時間じゃない。書いた。
• よっしゃサンプル通った。再submit。

撃墜タイム

• 絶対自分と同じ事をやってる人が大量にいると思う
• 「開く→ (探索/DPっぽい→閉じる || 最大値を後ろから順にとってきてる→325664,2でChallenge)」という戦略で2個撃墜
  • １個は最初もっと別のミスに見えて別の例を突っ込んで-25pt
• 一人最大値じゃなくて最小値をとってswapしてるっぽい人がいたので、たぶんどう考えてもおかしいので何も考えず同じ325664,2を入れてみたら撃墜

感想

• 250、100000とかだったら0と0をswapすればいいから全然問題ないですね。
• そもそも、最大値を取ってくるとかにこだわらなくても、100万までの数しかこないんだから、
  • 1回のswapで作れる数全部→2回の…→k回の…
  • を全部setでもっておけば100万*6C2*10 で求まるよ。
  • いや6桁の並び替えなんて6!通りしかないんだから720*6C2*10だ。余裕にもほどがある
• うわーだめすぎだ

• しかしGreedyっぽく解けたし再submit成功したしChallenge成功したし、実は意外と満足していなくもない