cafelier@SRM

SRM451

SRM | 09:47 |

SRM451 の成績・ソース (要ログイン) : AC/AC/- : 久々に500解けた気がする

500開く

• 『(0,0)からスタートして、(1,K1), (2,K1+K2),(3,K1+K2+K3),... のように駒を動かせます。ただし0<K1<K2<K3<...。盤面上に置かれているコインを最大何枚集められますか』</li>
  • コインは最大50枚
  • 盤面サイズは10000×10000まで

• 見るからにDPだ
• 盤面の座標を全部考慮すると最低 10000×10000 はかかるから、これはちょっと大きいな。
• コインが50枚しかないことを使って、50種類の座標だけ考えればいいようにするに違いない。

• とりあえずコイン座標をY座標順でソートしてみた
  • これでコインはこの配列のindexの昇順でしか取れない。
  • 「i枚目のコインをとるときに、そこまでで集められるコインの最大値」を求めるループを最後まで回すとかどうだ
  • いや
  • i枚目のコインをとった後にi+1枚目が取れるかどうかは、どのくらいの大きさのKでi枚目をとったかどうかに依存するな。

• じゃあこうだ。
• 「i枚目のコインを歩幅Kでとるときに、そこまでで集められるコインの最大値」を回す。
• Kは10000以下だから、思いっきり多く見積もってもせいぜい50万状態。
• i枚目から行く次のコインは最大50通りあるけど、それぞれ、Kを最小にするように行けばいいから、50通りしかない
• 最大最悪でも2500万。行ける行ける。

• というわけでメモ化再帰を書き始める。
• 書けた。
• ただし、「(y,x,k) から (y',x',k') に行くときに k' をできるだけ小さくする行き方」を求める関数を書いてない
  • えーと
  • たとえば (0,0,0) から (3,999,?) だと、
    • できるだけ小さい歩幅で進んで最後帳尻合わせる (0,0,0)→(1,1,1)→(2,3,2)→(3,999,996)
    • だと、最後が大きすぎる。もっと均等に進めるはず
    • (0,0,0)→(1,332,332)→(2,665,333)→(3,999,334) みたいに。
    • これは
      • k+1, k+2, ... の1ずつ増やす数列の全体を、x'を越えない範囲で底上げする
      • まだ余りがあったら、2ステップ目から… k+2,... の部分を底上げしてみる
      • 繰り返し
    • とかで最適になると思う。
    • さらに50倍計算がかかってるけど…いや、まあKが10000通りという見積もりは絶対に物凄く過剰だから大丈夫！きっと

• 書いた。できた。
• 自分で作ったサンプルが通らない。あれー？
• xとy逆だった。直したら通った。
• 50個集められる大きいケースでもすぐ終わるなー。時間も大丈夫っぽい。
• submit!

• サブミットした直後に気づいたけど、最適なk'を求める部分はO(1)で書けるなあ。
  • 「まだ余りがあったら」の後はk+(-余り)のところから後ろだけ増やすようにすればいいだけなので、k'は+1されるだけ
  • まいっか。

250開く

• 瞬殺してる人が多い
• 『最大10^12の数字nが与えられる。n=x+x0+x00+x000+... という形で書けるような最小のxを求めてね』
  • x00 というのは xの後ろに0を二つ繋げた数ね。

• えーとわからない。
• 全部試す…は、n以下の数全部試すと10^12通りだから終わらんよなあ。

• nをxの式で表示するとどうなるだろう。
• 0を後ろに並べるとかじゃなくて。
• 要するに10倍するってことだから…
  • n = x + x*10 + x*100 + ...
• だ。
• あれ？これって
  • n = x * 11...11
• じゃん。

• つまり、nを1で割ってみる、11で割ってみる、111で割ってみる…
• して割り切れたときの一番小さい数が答え。
• 1が12個並んだ数まで考えればいいから、12回割り算すれば終わる。

• 書いた。できた。
• 1 から 111...111 (12個) までソースに手書きする酷いソースですが気にしない
• submit

1000開く

• 『テトリスっぽいブロック４種類(□と棒とSとZ)が向き固定で使えます。与えられた白黒2次元マップの白マスを、ブロックがかぶらない様に覆うには最低何枚必要？黒マスは覆っても覆わなくてもどっちでもいい』
  • マップは最大で22×22

• どのブロックも向き固定なので、高さは2以下。
• ということは直前の列の埋め方 2^22 通りのそれぞれの最適解を持っておいて、次の列の最適な埋め方を求めるDP…
• いや、それは今の列の埋め方が2^22通りあるから 2^44 かかる。
• これはダメだ。似たような問題で15×15でもキツかった覚えがある。
• これを枝刈りでどうにか…という方向で挑みたくはないなあ。

• 15×15でキツかった問題というのは去年のGoogle Code JamのWorld Finalsですが、あれは正解は最小カット（最大流）だった。
• 同じ用にグラフの問題におちないですかね。

• 白マスを頂点に、ブロックによる覆い方を別の頂点にした２部グラフにsourceとsinkをつけて
• 最小費用流かなにかに…
• ならないなあ。ブロックが重ならないという制約が表現できない。
• そもそも22×22×5>2000くらい頂点ができるし、これ最小費用流無理じゃ

• 発想を変えよう。
• n枚のブロックで覆えたら4nマスを覆っているので、白マスの個数を引くと、
• 覆わなくてもよかったけど覆ってしまった黒マスの数がでてくる。
• これが最小な時、nも最小となる。
• nを最小化すると考えるんじゃなくて、黒マスを覆っちゃう数を最小化する問題と考えるとどうだ？

• どうもならん。
• うーん

感想

• 撃墜タイムは１個も撃墜できず。250で物凄く頑張ったコードを書いている人のミスを探そうとしたけど、読むのつかれる…
• system test でかなり500が落ちてるんだよなあ。
  • こういうの見つけられるようになりたい。