情報更新

last update 03/28 00:39

ツイート検索

 

@chokudai
サイトメニュー
Twilogユーザー検索

Twilog

 

@chokudai

chokudai(高橋 直大)@AtCoder社長@chokudai

Stats Twitter歴
5,747日(2008/07/04より)
ツイート数
137,789(23.9件/日)

ツイートの並び順 :

表示するツイート :

2020年09月13日(日)29 tweetssource

9月13日

@chokudai

chokudai(高橋 直大)@AtCoder社長@chokudai

N=200000として、1,2がそれぞれ10万個だと、1-1と2-2がi個で、1-2と2-1がN/2-i個とかになって、次のステップに進むには、1-1と2-2が1個ずつ選ばれないと行けないので……みたいに考えると、どれくらいの期待値になるか求められる感じ。

posted at 23:51:00

9月13日

@chokudai

chokudai(高橋 直大)@AtCoder社長@chokudai

で、これがキラーケースだって考えて、こういう2種類パターンのときだけうまくいくような初期配置を設定した人は、後者のダメな方の乱択でも通った感じ。これは本来は落とせるので可能であれば落としたかったけど、なかなか難しいかなあ……。

posted at 23:48:27

9月13日

@chokudai

chokudai(高橋 直大)@AtCoder社長@chokudai

ちゃんと説明すると、一番やばいのはA,B共に{1*100000, 2*100000}みたいなケースで、これを乱択で解消しようとすると、ダメな箇所がi箇所ある時に、期待値N/iで1ステップ進めるならO(NlogN)、これが期待値(N/i)^2とかになっちゃうとO(N^2logN)になって、前者はほぼほぼ通るけど後者はまず通らない感じ

posted at 23:46:44

9月13日

@chokudai

chokudai(高橋 直大)@AtCoder社長@chokudai

なるほどF問題で片方Reverseするだけでキラーケース回避出来るって考えは賢い。ノイズちょっとだけ混ぜると確率的に落とせるのかな(A={1*99999, 2*100000, 3*1}, B={1*100000, 2*100000}とか

posted at 23:39:08

9月13日

@chokudai

chokudai(高橋 直大)@AtCoder社長@chokudai

@kichi2004_ とりあえず逆順を入れないと通らないとおもいます。(最後の1手がO(N^2)になるので)
逆順入れなくても通る方法はあって、「片側をsameのもののみから選ぶ」ってしてあげると間に合うので、その乱択を想定していた

posted at 23:30:52

9月13日

@chokudai

chokudai(高橋 直大)@AtCoder社長@chokudai

@kichi2004_ まぁなんか「どの乱択の話?」って言うのがあると思っていて、この乱択は計算量の削減パートがちゃんと入っているので、まぁ通るのが当たり前だと認識している感じです。
(なので込みで1000だとおもってました)

posted at 23:03:12

9月13日

@chokudai

chokudai(高橋 直大)@AtCoder社長@chokudai

乱択解法色々あるけど、その乱択で最も計算回数の期待値が高いテストケースを考えてみて、その期待値を求めてあげれば、大体通るものになってると思います。ちゃんと計算してね><

posted at 23:02:18

このページの先頭へ

×