cafelier@SRM

SRM491

SRM | 17:53 |

SRM491 の成績・ソース (要ログイン) : AC/-/- : ちょっと難しいセットになるとすぐこの成績ですよもうだめだ

250開く

• 『入力は自然数 N と K。1～Nまでから選んだ異なる数字が各面に書いてある6面ダイスで、裏表の和が3カ所で等しくて、K以上になるようなものは何個あるか』
  • 回転は同一視
  • N, K は 1000 か 2000 とかその辺り以下

• テストケース作成
  • 最大ケース
  • あと、NやKが小さすぎて0通りになるケースを入れまくっておく

• 簡単ぽい
• 式一発で求まりそうだけど
• NもKも小さいから2乗のオーダまでは地道にループして数えて大丈夫
• ならそう書いた方が絶対間違えにくい。それで。

• 和をK以上のいくつにするか固定して（これはK～2Nまで全通り試せばいい）
• その和になる裏表ペアが何個あるか1～Nまでのループで数えて
• C(ペア数, 3) を求めて
• 1～6の場合は2通りとサンプルに書いてあるので回転無視すると2通りなんだろう、2を書ける
• これを全部足し算

• できた。
• 書き書き。
• いろいろ混乱しながらも書き終える
• サンプル通った。
• 230点。ううう時間かけ過ぎ…

600開く

• 『50文字以下の文字列が最大16個与えられます。各文字列の中身は好きなように並び替えていいので、trieを作った時のノード数を最小にしてね』

• 16個ということは2¹⁶をどうにか。
• 2¹⁶*50 くらいの計算量かなあ。

• DPとすると、こうなるはず。
• 文字列の集合（元々の文字列たちの部分集合）が与えられたときに、
• これを最適にtrie化する
• というのは、部分集合の最適trie化がわかってればすぐ解けるか？
• 解けるか？
• ええと、
  • 今の部分集合が文字列１個しかなければ、その文字列の長さ分伸ばすしかない。
  • それ以外なら？
  • 全部に同じ文字（たとえば 'a'）が含まれてたら、'a' でとりあえず全部まとめるのが明らかに最適で
  • 残りを再帰的に…
  • あれ、残ってるのまた同じ文字列全部の集合だ

• てことはあれか、そうか、「文字列の集合」と、「trieの上何文字をこの文字列で確定したとしたとき」の最適解を求める
  • さっきのだと、dp(集合,"") = dp("集合","a")+1 になる
• これだと状態数が…
• 爆発しませんか…？
• trieのパスになり得る文字列は、長さ50の文字列がわりと何でも来る
• ダメだ…

• 900の方が簡単だったりしないかなあ。
• と思ってスコアボードを見たら案の定、何人かに瞬殺されてる
• よし、600は保留。

900開く

• 『最大50枚ずつ、同数のカードが2セットあります。1から100までの実数が書いてあります。それぞれから1枚ずつ選んでa+bとa*bの大きい方がTaroに、小さい方がHanakoに得点として入ります。k回やったときにTaroの得点/Hanakoの得点が最大になるようにするといくらになりますか』

• 足し算と掛け算ってどういう条件でどっちが大きくなるんだっけ
  • a+b < ab
  • 0 < ab-a-b
  • 1 < ab-a-b+1
  • 1 < (a-1)(b-1)
• (a-1) と (b-1) の値による。
• なのでaもbも2以上なら掛け算がお得。そうでなければケースバイケース。
• なるほど。わりと綺麗な式になった。
• きっとこの境界で場合分けすると綺麗に解けるに違いない！

• とりあえず2以上と2未満に分類して覚えておいて…
• それでどうするんだ…？

• うむむわからない。
• やっぱりHardは無理だ。Mediumに集中しよう。

600に戻る

• とはいえこちらもわからない。
• 文字列集合 × そこまでのコンテキスト情報
• を間に合う計算量で持とうと思うと、コンテキスト情報って50、深さの情報くらいしか持てないけど
• 深さと集合で最適解求めても、
• 集合を子ノード用に分割したとき、深さだけだと一貫した最適解が得られるとは限らないのでマージできないし…
• わからない…

• ええい乱数アタックだ！
• 16個の文字列をランダムに並び替える。
• 左から順にgreedyに最適にマージしていく。
• 16! 全通りは勿論間に合わないけど、結構な割合時間内でカバーできるでしょう

• で、最適にマージって。
• まずそもそも最初の一個目の文字列をどうしよう。
• 完全に trie にしてしまうとどの順で並べるべきかは50!（までは行かないけど、26文字種しかないので）通りなので、
• これも乱数にするとさすがに無理だ
• ここは、trieを拡張して、leafには文字列集合が入るようにする
  • そこから下はlazyにあとでマージするときに伸ばす

• 次
• 拡張trie と文字列（というか文字集合）が与えられたときに最適マージ
• すでに集合じゃなくて展開されてるedgeに沿って一番深く行けるところまで伸ばして、そこに集合をぶらさげ…
• leafまでいったら集合と集合のmergeで、
• これはできる限り共通部分を下に垂らして最後で分離
• 共通部分を下に垂らすのは…
• うおおここの順番も後で最適マージするのに重要だ
• これも集合にした拡張trie

• とかやってると、最後まで問題の情報を単にencodeしただけの謎データ構造が残るだけだなあ。
• 無理だ
• わからない…

感想

• というわけでタイムアップ。
• ひどい結果…
• 900は、その後も時間内にはわからなかった気がするけど、
• しかし２部グラフのマッチングに一瞬たりとも見えなかったのは酷いというレベルじゃ済まないなあ
• 足し算と掛け算というスコアシステムのせいで、数論っぽい気の利いた最適化か！と釣られてしまった
• 反省