Lyft Level 5 Challenge 2018 - Elimination Round

olphe @_olphe

ん、僕room100じゃん

satanic@研究💪 @satanic0258

あーわかったけど時すでにお🍣

iwashi31 @iwashi31

ひーん

hirokazu @hirokazu1020

時間足りない

olphe @_olphe

こどふぉおつ

うし @ei1333

これはなんですか

satanic@研究💪 @satanic0258

こどふぉおつでした

iwashi31 @iwashi31

D 通った心地がしなさすぎる

(nは自然数) @n_vip

Dかなりの注意力ゲーじゃないか？こんなに通ってるの信じられないけどpretest弱いですか？

てんぷら @tempura_cpp

Hackをする気力がなくて

kmjp @kmjp_pc

Fは方針あってると思ったけどサンプルが合わなかった…。A～Dが通ることを祈るしかないな。

HIR180 @HIR180

E嫌いすぎる

kuuso @kuuso1

こどふぉお疲れ様でした． ei133333さんと同じ部屋だった．

てんぷら @tempura_cpp

D、pretestは通ったけどかなり不安

HIR180 @HIR180

F<<<<<<Eです

satanic@研究💪 @satanic0258

こどふぉ A:クイーンの行けるマスを消してBFS B:a-b==1かつa+bが素数ならYES C:大きい数字から行き先に勝ち確マスがあるか判定,行き先はn/i個なので調和級数よりO(nlogn) (→)

kuuso @kuuso1

E面白いと思ったけどまったくわからない．

satanic@研究💪 @satanic0258

(→) D:素数の2,3,4乗のやつをまず判定,それ以外は二個固定してgcd取って1じゃなかったら約数判明,どの数ともgcdが1のものがあれば未知の素数を2個持つとして処理,最後に各素因数ごとに個数求めて掛け算

(nは自然数) @n_vip

Eもかなり面倒要素が強くない？とりあえずなにか辺を探してこないといけないし、600^3くらいかかる気がする。間に合わなかったけど

iwashi31 @iwashi31

Java の BigInteger、isProbablePrime とかいうメソッドがあるのね（B で a^2 - b^2 に対しそれするだけのコードがあった）

うし @ei1333

A: これうくじゃあないですか　けわしいきもちでUFをかきました B: これはなんですか　B+1=AでA+Bが素数であることと同じ C: メモ化再帰　調和級数 D: 素数の2～4乗か2つの異なる素数の積しかなくて、前者はにぶたん、後者はgcdを求めればなんとかなる

nmnmnmnmnmnmnm @enuemuenuemuenu

CはDP以外の方法をずっと探っていたのだけれどよく考えたらDP以外の確実な方法なんてないよね。

うし @ei1333

はず

てんぷら @tempura_cpp

AはO(1)です

(nは自然数) @n_vip

これ怖くない？ pic.twitter.com/H4code0RXo

拡大