SRM464

TopCoder

なんかもういろいろと残念すぎる。

250

  • ・・・全然わからん。
    • n = 50, k = 1,000,000,000だと・・・？全探索のしようがない・・・。
  • DPも思い浮かばない。数学ゲー？
  • invalidな文字列の条件を考えてみよう。
  • まず同じ部分文字列が2回以上登場したらダメ。
  • あとは、部分文字列のproduct valueが1桁で、その数字が含まれていたらダメ。
  • ・・・これ以外は全部OKな気がする。[要証明]
  • そもそもこれでいいと仮定して、どうやってK番目のを持ってくればいい？
    • 全探索か・・・。無理。
  • やっぱDPかも。
  • dp[長さ][既に使った数字の集合] = 個数 みたいなDPはどうだろう？
    • 文字の並び順を忘れてしまうと上手くいかないと思う。
  • 数学は無理、DPはダメ。八方ふさがりだ・・・。
  • やけくそで全探索 + 枝狩りでも考えてみるか。
  • さっき言った通り、同じ部分列が2回以上登場したらダメ。
    • もっと言うと、同じ数字が2回以上登場したらダメ。
  • ・・・。
  • ・・・？
  • ・・・同じ数字が2回以上登場したらダメ？
  • ・・・
  • あああああああぁぁぁぁぁぁ！
  • 10文字以上の解とかありえない！
    • n = 9でも最悪362,880個の解しかない！
  • 詐欺だぁぁぁぁ！
  • 実家にいるので満足なプログラミング環境が無くて、前回同様Arenaで頑張る。書けた・・・。
  • こんなトラップに引っ掛かるとかバカすぎる・・・。
  • 最大ケースと1桁のケースをちゃんと試してsubmit.

550

  • バイナリサーチ + 何か。
  • 何かって何だろう。フローだろうか。
  • よく分からないけどもうあんまり複雑なのを書いてる時間ないな。適当にDFSで調べよう。
  • Complie Errorが取れた瞬間に終わった。残念。

Challenge Phase

  • 500は放置。
  • 1桁の場合の処理がみんなのと違う気がする。
  • ・・・！ "0"もvalidなのか！
    • 意図的に弾いた挙句、n=1, k=9に "9" と帰ってくるのを見て満足してた自分ばーかばーか。まるきゅー。
    • その後しばらくして落とされました。
      • 落とされる前に間違いに気付いた場合、せめて自らの手で葬ってやることはシステム上できるのだろうか？
  • n=10の時まで探索してる人がいて、これはギリギリTLEになるかな？と悩んでたら先に落とされました。
    • challenge phaseでは私は基本的にチキンです。

result

  • [Challenge Succeeded, Complied, Unopened], 0.00
  • 1417 -> 1380
  • 「今日の結果次第では黄色になれそうだ！」とか浮かれてたSRM前の自分には爆発を促したい。