cafelier@SRM

SRM439

SRM | 12:07 |

SRM439 の成績・ソース (要ログイン) : AC/AC/- : たまには今回は美しく解けたなあなどと思いたい…

500開く

• 『単語の集合が与えられるのでここから適当に何単語か拾って回文作る作り方を数えて』
  • 単語数は13。各単語の文字数も13文字まで。

• なんか前にも見たことがあるようなないような…忘れた。
• a, aa, aaa, ..., a*13 が来ると 13! 以上は解があるから全部数えるのは確実にTLEだなー。
• まあたぶんDP的なもの。

• 2^13 は十分扱える範囲なので、すべての単語部分集合について、それで回文作れるパターン数を数えて足す。
  • それぞれ数えている間にその部分集合のパターン数が必要になるはずなのでそれをメモ化して覚えておけばOK。これだ。

• {w1, ..., wn} を使って回文作れるパターン数 = w1 で始める場合のパターン数 + w2 で…
• w1 で始める場合のパターン数は、
  • #{w1 hogehoge | w1 hogehogeが回文でhogehogeが{w2..wn}で作れる}
  • で、だから要するに
    • hogehoge が rev(w1) で終わってて hogehoge-rev(w1) が回文
    • rev(hogehoge)がrev(w1)に完全カバーされてて、つまりw1とrev(w1)がオーバーラップする感じで残りの部分をexactに作れる場合

• {w1 hogehoge | "w1 hogehoge" が回文} と {w1 hogehoge | "hogehoge" が回文}
  • を別々に数えることになるんかな。ここで出てくるw1的なものは元々の単語の部分文字列なので、たかだか13*13通り。
  • これをキーにしてメモ化しても2^13*13*13…まあ大丈夫じゃないかな。
• 「rev(w1)で終わる」は全体をreverseして「w1で始まる」と思えば回文の話だからたぶん同じ事だから全部「始まる」に統一できる
  • ※間違い

• というわけで２関数のメモ化相互再帰を…
• 書けた。
• 答え合わない

• ？
• 「終わる」と「始まる」区別しないとダメだよね。
  • "a" "ba" で最初に "a" を選んだときに 「"a" で終わって"a"を引いたら回文」なものは "ba" で見つかるけど「rev("a")ではじまってrev("a")を引いたら回文」じゃみつからない。

• ものすごいコピペで逆向きバージョン作成。ひどいソース…。
• 直った。memo1 ～ memo5 まで表がある無茶苦茶な感じに…。

• とりあえずsubmitしてしまえ。ずいぶん手間取ってしまったし。

• 一応最悪ケース試しておこう。
  • a, aa, aaa, ..., a*13
  • 手元で8秒かかる！！！！！！！これは死ぬ

• 文字列でメモ化してるのがまずいのかなー。
• もとの単語の部分文字列ということを利用して整数でのメモ化にスイッチ
• うおお残り20分しかない
• できた。
• 手元で23秒かかる！！！！！！！！！！！！ぎゃー

• 別の単語の別の部分からとった空文字列とかを区別してメモ化しちゃってるから、そりゃメモ化効率悪化してるよね…
• だめだ。あと15分しかないしあきらめよう。

250点開く

• 0点回避のためにこっちに逃げる。
• 249点台で瞬殺してる人がいるから楽勝問題なはず…っ
• 『（だいぶ長い問題文here）』
  • これはやばい…

• 落ち着いて読んだら、要は「与えられた数N以上の数のうち立ってるビット数がK以下の最小の数は」だった。
• Nは10^7とのこと。
  • これならNから1ずつ増やしてって毎回ビット数数えるので十分間に合う。

• サックリ実装。
• サンプル通った。OKOK。

500に戻る

• あと11分！
• 元の文字列版の方を最適化する方が見込みあるなー。
  • しまった元のソース残してない。うわあああ。

• ちょっと落ち着こう。
  • さっき手元で8秒かかったとき最適化オプション付けてなかったような気がする
  • （コンソールさかのぼる…）
  • つけてない！ 最適化なしで8秒なら心配しなくても通るよ！
  • 念のためサーバ上でa,aa,...をテスト。
  • 1.47sec。勝利。
  • というか最初からサーバで試しとけって話ですね、やっぱり…orz

感想

• JavaはInteger.bitCountってあるのか。なるほど。
• 色々と落ち着け俺。