cafelier@SRM

SRM438

SRM | 02:22 |

SRM438 の成績・ソース (要ログイン) : AC/AC/- : 腹を切って死ぬべきな感じのコード量産大会

500開く

• 『inputとprogramという二つの文字列が渡される。x=input; s.times{x=program.replaceAll('$' => x)}; x[min..max] を求めよ』
  • input と program は50文字まで。sとmin,maxはintに収まるくらい。ただしmax-minは100

• 再帰的にごりごりと書いていけばどうにでもなると思う…
• sが巨大なので、本当に再帰の底まで届かせるような再帰はだめ
• $が2個以上あれば32stepもすればminとかmaxの範囲を文字列超が超えるからそれより上は考えなくてもいいよね…

• ということで適当に打ち切りながら頑張るぽい
• まず$の個数をカウント
  • $が0個の時にinput[min..max]を切り出すのはだいたいsubstr…
  • $が1個の時はp$qという形なら最終形はp^s input q^sだから、ここから[min..max]を切り出すのは…ええと面倒だな…

• $の個数0,1,それ以上で場合分けとか実はまずい方針で、そのせいで面倒になっているのでは…

• 色々考える

• やっぱり他に思いつかない

• あきらめて書こう

• あれ？max-min短いから、一気にsubstringを切り取るんじゃなくて、minからmaxまで一文字一文字毎回再帰でも求めてもいいんじゃね？
  • (p^s input q^s)[min..max] を一発で求める再帰は難しいけれど
  • (p^s input q^s)[i] なら何とか書けそう。これをfor i←min..max で回してもたかだか100倍遅いだけ。
  • inputもprogも～50でsも～32くらいで押さえてあるはずだから、ここに最適解より100倍増えても大丈夫じゃないかなーそうしよう。

• 以下必死に実装
• できた。サンプル通った。

• でもサンプルにsが大きいのないな。作ってみる
• はいはい無限ループ無限ループ
  • sを適当なところで打ち切ってない箇所…あった。修正
• これで時間的にも大丈夫になったけど
• コードがad-hocなコピペ乱打すぎてこれ以上デバッグする気力がでないからもうsubmitでいいや

300開く

• そもそも300って点数がどう考えても危険
• 『正数の集合luckySetが与えられます。このとき、正数nの"幸運度"を、nを覆う閉区間でluckySetを含まないものの個数、で定義（小さい方がlucky）。幸運度が同じなら元々の値が小さい方がlucky。luckyな数上位n個を求めてね』
  • luckySetの要素数は50まで。要素の値はintに入る程度。nはたしか100とか1000とかその辺り

• luckySet自身は常に幸運度0なので上位にくる
• luk, n, luk と挟まれている数も…区間の定義がA＜Bな[A,B]だったので幸運度0。
  • これはどう見ても落とし穴…
  • サンプルにもこういうのないし…
  • 狙い目

• あとはもっと広い区間内にある数は、区間内の左右の幅を掛け算したような感じの値が幸運度。
  • ただ、luckySetの上限はintに入るくらいなので、その範囲の全部のintの幸運度を計算していくと時間が足りない。
  • luckySetで50分割くらいしかされないから、それぞれの区間から幸運度小さい順に数を出してくるジェネレータを作ってマージ…
  • Pythonとかならそう書いてもいい気がするけどちょっととっさに書くにはきつい…

• ぴこーん！
• nが100だか1000だかなんだから、
• 50個に分割されたブロックそれぞれから上位n個とってきて、
• あとでまとめてソートしてその上位n個とる、
• でO(50n log n)だよね。これで十分。

• 書いた
• 動いた
• submit。

撃墜タイム

• luk, n, luk と挟まれている数はluckySet達より先に来られるケースを見落としてる解を撃墜すべく準備
  • {2}, 1 で。
  • 正解は 1。間違えてgreedyにluckySetを出すようなルーチンは2を返す。

• …
• 自分が開いてコードを読み始めるたびにそのコードが撃墜されてゆく…
• みんな速すぎる…
• 辛うじて1人撃墜。1ミス

感想

• 300も500もかなりコードが酷いので、焦っててももっと綺麗に書けるようにしたい…
• [追記] なに、programの最初の文字は常に '$'、だと……それはものすごく簡単だ……ぐおお