cafelier@SRM

TCO10 R3

SRM | 11:40 |

TCO10 R3 の成績・ソース (要ログイン) : WA/WA/- : 完　全　敗　北

500開く

• 『王子様がN人います。それぞれ(px[i],py[i])にいて、(dx[i],dy[i])に行きたいのです。王子様は他の王子様を自分のいる場所に呼び寄せる魔法のテレポーテーションカードが何度でもいつでも使えます。（ただし、同じ一瞬には世界で一枚しかこのカードは使えません一瞬でもずれていれば複数枚使えます）。全員が目的地に着くまでの時間を最短化？』
  • N≦50
  • 座標の範囲は0～10000

• テストケース作成
  • 最小ケースと、50人いる最大ケースを適当に。

• とりあえず「最大値の最小化→二分探索」テンプレを発動させて考えてみる
  • 二分探索の初期値… 0-ε分では不可能。下限は0
  • 全員直接向かっても √2 * 10000 時間あれば着ける。上限は20000くらいにしておこう
• という範囲から、時刻 T を二分探索して、T で全員目的地に行ける？行けない？を探索する

• 目的地d[i]から半径Tの円を描いてみて…
• この範囲に入れれば、到着できる。

• d[i] の近くに p[i] さんが p[i] さんは到着できることは確実なんだけど
• テレポートしまくれるから、p[i] さんでなくて p[k] さんがその範囲にいて、適当なタイミングで p[i]さんを召還してくれれば、それでも行ける
  • テレポするタイミングって考える必要あるのかな…
  • しばらく自分の目的地とは遠ざかる方向に走って他の人を助けてから戻るとか
  • ううーむ無さそうな気もするけどちょっとわからん

• 逆に、d[i] の半径T近傍に誰もいなければ、どれだけテレポートを駆使してもその範囲に行けないので、無理。
  • これは確実だ。

• やっぱりテレポは最初の一瞬だけしか使わない気がするなあ。
• そういうことにしよう。

• すると、d[i] -- p[k] が距離 T 以内にあるペアが行けるペアなので、ここにうまく配置できるかどうか判定を考えればいい。
• 二部グラフのマッチングか！
• ↑の二部グラフで最大マッチングが N か判定するお仕事
• できた
• あれ？答えサンプルと全然合わない

• あー、そうか、p[k] が複数の目的地にとってベストポジションだったら何人も集まってここから出発していいので
• 最大マッチングじゃないや。一つの頂点から何本辺がでてもいいので。

• すると…？
• あれ、単にすべての d[i] から距離 T 以内に p[?] がどれか一個あればOK？
• つまり距離の最小値が T 以下ならOK か
• これ二分探索とか要らなかったなー。まあいいや速度は十分だし
• 書いた
• あれ？まだ１個だけ答えサンプルと合わない

• 合わないサンプルを見てみる
• 集合として {d[0],...,d[N-1]} = {p[0],...,p[N-1]}
• だからさっきのアルゴリズムだと 0 秒で全員行けることになるけど、
• こう、たとえば目的地が{A,B}で現在地が{B,A}だとすると
  • Aに要る王子様がもう一方を召還すると、その時点で{A,A}になっちゃってBに行けなくなるし、
  • 逆に{B,B}にするとAに行けなくなるし
• つまり、そうか、「同じ瞬間に同時発動できない」という制約はこういうことか。
• 一気にみんなでテレポ使うとしても、一人だけは移動できずに元の場所から走らないといけない

• なるほどなー
• で、どうするんだこれ。
• 一人テレポできないので、F さんができない人と仮定して、
• それでT秒でいけるかどうかチェック
• F が 0～N のどれか一つででも全員到着できたら勝ち

• 本当かこれ
• ううむ
• ううむ
• 自信ないけどサンプル通るし時間なくなってきたし、出しちゃおう

250開く

• 瞬殺されてる
• 『エラトステネスのふるいをmaxNumまでやります。最後に消される数字はどれですか』
  • 4≦maxNum≦20億

• テストケース作成
  • 小さい方4,5,6と
  • 大きい方20億と、20億未満の最大の素数でも入れておくか

• えーと素直にエラトステネスを実装すると…20億は無理ですね

• 消えるのは合成数
• 素因数が大きいほど遅くに消える
• てことは、√maxNum 以下の最大素数の平方あたりが最後ではないか

• 書いてみた
• √maxNum 以下、とりあえず10万以下のエラトステネスを普通に書いて素数リスト作成しつつ…
• 全然合わない
• maxNum=100 で 91 らしい。7×13。
• そりゃそうだ。7×7 より大きい。

• むむう。
• 最後に消えるのが√maxNum 以下の最大素数(Pとしよう)の倍数であることは間違いない
  • P × (素因数がすべてP以上な数)
• のうち、maxNum以下で最大のもの

• P × (P以上の素数)
• でループしてみて、maxNum を超えない限り大きくしていけばいのでは
• しかしこれは、「答えは必ず素数2個の積で書ける合成数である」と仮定していることになるなあ。
• 本当かな…

• とりあえず書いてみたらサンプルと答えは合った
• ううむ3個以上の積の場合…
  • といっても、それがあるとするとP×(P以上の数全部素因数分解してみてP未満で割りきれないもの)
• とか書かなくちゃいけなくて、素因数分解のコスト掛け算すると最悪 O(maxNum) になったりしちゃいそうな…
• うむむわからんし3個以上要る場合思いつかないし
• 500を落とすつもりで考えると、今submitして250の点数だけだと200位とかだし
• そろそろsubmitしないと150位入れない。出すならもう出さないと意味ない。
• えお、みんな瞬殺で解いてるからそんな複雑にはならないに違いない！出しちゃえ！

1000開く

• 問題文みじかっ
• 『アルファベットと数字からなるN文字のパスワードで、最低U文字大文字が、L文字小文字が、D文字数字が入っているものの総数』
  • mod 1000000009 で
  • 0≦U,L,D≦N≦10万

• あれ、なんとかなりそうに見える…
• けどスコアボード見てもまだ誰も解いてない。難しいのかな。

• 式でとりあえず書いてみると
  • Σ_{l≧L,u≧U,d≧D, l+d+u=N} C(N,l)・C(N-l,u)・26^l・26^u・10^d
• ちょっとよくわからないが
• N≦10万ということは、一個くらい固定して、残りをO(1)かO(log N)で計算できれば十分なのでは

• 数字の個数dを先に固定すると
• Σ_{D≦d≦N-U-L} C(N,d)・10^d f(N-d)
  • where f(N') = Σ_{l≧L,u≧U, l+u=N'} C(N',l)・26^l・26^u
• 26^{l+u} は 26^N' だからくくりだせるか
• Σ_{D≦d≦N-U-L} C(N,d)・10^d・26^{N-d} f(N-d)
  • where f(N') = Σ_{l≧L,u≧U, l+u=N'} C(N',l)

• ほら簡単になった。
  • 要は Σ_{l≧L,u≧U, l+u=N'} C(N',l) これさえ高速に求まればいい
  • LとUの制限がなければ2^N'なんだけどなー。左右切り落とすとどうなる…
• いやちょっとその前に
  • C(N,d)・10^d・26^{N-d}
• この計算をO(N)回するんだけどこれ、それぞれO(1)でできるか？
• ベキ乗はO(log N)のオーダでできるとして、C(N,d) って毎回定義式どおり計算するとO(N)時間かかるよね
• ううむ
• メモ化しても再利用するわけでなし
• パスカルの三角形も10万まで計算は無理か
• あ、
• いや、
• これ単純なループなので、求めるべきものは C(N,D),C(N,D+1),C(N,D+2),...
• で、C(N,D)は普通に求めるとして、C(N,D+1) は、C(N,D)から掛け算１回割り算１回で求まる
• だから、ループの度に更新していけば平均コストはO(1)だ。

• よし
  • f(N')=Σ_{l≧L,u≧U, l+u=N'} C(N',l)
  • すなわち Σ_{L≦l≦N'-U} C(N',l)
• に戻る。これもだから、lとl+1の場合で使う C(n,k) は掛け算１回割り算１回で更新できる程度しか変わらないのを利用して、最初だけ定義通り計算してあとはインクリメントにどうにかすればどうにかなりそう…

• ええと f(N') は普通に計算するとして、そこから f(N'-1) をインクリメンタルに求めるには
  • パスカルの三角形を考えると、だいたい
  • f(N'-1)*2 + C(N'-1,L-1) + C(N'+1,N'-U+1) = f(N')
  • こんな感じに、2倍して端っこだけ足してやれば次になる感じなので
  • この端っこの C をインクリメンタルに求めていけばよくて、これは掛け算割り算で定数オーダで管理できる

• OK!
• そして最初のf(N') は普通に計算…あれ？
  • Σ_{L≦l≦N'-U} C(N',l)
• これ全部普通にやったらO(N^2)かかるのでは
  • あーこの中のC(N',l)もやっぱり少しずつけいさんしていけば、頑張るのはC(N',L)だけでいいや
  • あるいは、N'を試す順を逆にして、L=N'-U になるところからループすれば…と思ったけどこれはDが小さいとそんな状態がないから駄目か

• よしコーディング…と思ったら時間がない…おわた…

撃墜タイム

• 部屋の250が凄い勢いで落とされていく
• うわあこれは絶対やっぱり3個以上の積が正解になるケースがあるんだ…orz

• 撃墜して回ってる人のソース開いてみる
  • if(maxNum==8)return 8; みたいなコードが
  • おお、8の場合2*2*2の8が最後に消える！確かに！！！

• あ、自分のも落とされた。はいはい。
• しかしまだ間に合う、乗るしかない、この撃墜ビッグウェーブに。
  • 500の自分の点数280点くらいあるから、撃墜多少失敗してもこれがあってれば150位には残れるはず
  • 逆にこれが落ちてたらもう無理だし、あってると仮定してガンガンチャレンジしてみよう
• 適当に開く
  • よし、なんか素数二個の積しか試してないっぽいコードが！
  • 8 ！
  • あれ？チャレンジ失敗…？？
  • うおお、この人、上の方で素数リストを作るためのエラトステネスと見せかけて、10万くらいまでは実際にエラトステネスで最後に消えた数字を覚えておいてそれ返してる！賢い！

• あ、500も落ちた。もうだめだ…

感想

• というわけで初のネガティブスコアでした
• 反省点はなんだろう
  • 250だなー。
  • 「小さいケースでナイーブな解法と完全に一致する」は確かめておくべきだった
  • 特に今回はエラトステネスまで書いてるんだから、ほとんどノーコストでsmall用の解が作れるのに…