SRM 759

千咲=タプリス=シュガーベル @gzlcp

レートバグってるならもうちょっと上がってないかな

竹雄 @takeo1116

てんぷらくんまた伝説を作ってしまったのか

tsutaj @tsutaj

Med 列挙パートで TLE してそこから何も書けてないの嫌すぎる

tsutaj @tsutaj

他の人のコード見るか・・・

うし @ei1333

ねね

うし @ei1333

1916->2018(+102)

千咲=タプリス=シュガーベル @gzlcp

最近まれに見る「○○じゃ、だめだろ」って出典あるんですかね

minus9d @minus9d

SRM 759, 安定の75.00。基本は素数A、素数Bを全探索して素数Cが条件を満たすかチェックするのだけど素直にやると8000(5桁の素数の数)^2で間に合わな（数十秒かかる）。そこで、素数の下2桁で素数をグルーピングする。

minus9d @minus9d

素数下2桁は01, 03, ..., 99の50通りで、だいたい素数は160個くらいに分割される。下2桁がaaである素数と、下2桁がbbである素数の組み合わせは160^2程度。aa, bbの可能な組み合わせは50^2より減る（ここの考察がいい加減）ので、全体の計算が1秒以内で収まる。

tsutaj @tsutaj

tourist は基数ソートしてるみたい

minus9d @minus9d

R1297→R1342。思ったよりみんな落ちてた

千咲=タプリス=シュガーベル @gzlcp

10 進 trie でソートしたら速いですか？

ヘクト🐬 @osrehun

@n_vip @_TTJR_ 少し話が脱線しますが、(cur_hash << 7) - 1はcur_hashを127倍にする処理ですか?

有為 @uwitenpen

@satanic0258 これは罠でしゃくとりするためには両方ソートしないといけない

tsutaj @tsutaj

@osrehun @n_vip はい (* 127 が遅いのかなあと思って適当に変えていました) (今思いましたがこれ間違ってますね)

千咲=タプリス=シュガーベル @gzlcp

競技プログラミングはやらないって言ったのに

有為 @uwitenpen

ソートをO(n)でやるなら別か

千咲=タプリス=シュガーベル @gzlcp

院試までトップコーダーは出ません

tsutaj @tsutaj

なんか普通にソートしてる人とかもいるしよくわからないなあ

てんぷら @tempura_cpp

@satashun をしたらTLEします

千咲=タプリス=シュガーベル @gzlcp

院試まで出ないもの トップコーダー コードフォーシーズ シーエスアカデミー

こるとん @kyort0n

僕は結局vectorに全部突っ込んでsortしてにぶたんでした setに毎回insertは定数倍が重くてダメだった

千咲=タプリス=シュガーベル @gzlcp

med はハッシュ取るときの剰余演算を最後の一回だけにした以外特に高速化してないし普通にソートした

不養生 @satashun

@tempura_cpp (何はともあれ)赤おめでとうございます！

minus9d @minus9d

TopCoderの賞金、ずっっっっと放置してたけどようやくもらうことができた。総額105ドル！