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
Stats | Twitter歴 5,747日(2008/07/04より) |
ツイート数 137,789(23.9件/日) |
表示するツイート :
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
chokudai(高橋 直大)@AtCoder社長@chokudai
で、これがキラーケースだって考えて、こういう2種類パターンのときだけうまくいくような初期配置を設定した人は、後者のダメな方の乱択でも通った感じ。これは本来は落とせるので可能であれば落としたかったけど、なかなか難しいかなあ……。
posted at 23:48:27
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ ええー、おもったよりよわい。
posted at 23:46:50
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
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ もちろん修正とかは入らないのでそれでおっけーです!
posted at 23:44:26
chokudai(高橋 直大)@AtCoder社長@chokudai
「乱択の正しい解法」と「落とせるはずの乱択の解法」をごちゃごちゃに語るのはやめるんだ!(今回の問題ではどっちもあるみたいです)
posted at 23:43:37
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ ><
posted at 23:43:00
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ あれ、これで変わらない……?
https://twitter.com/chokudai/status/1305154050078339078…
posted at 23:40:02
chokudai(高橋 直大)@AtCoder社長@chokudai
なるほどF問題で片方Reverseするだけでキラーケース回避出来るって考えは賢い。ノイズちょっとだけ混ぜると確率的に落とせるのかな(A={1*99999, 2*100000, 3*1}, B={1*100000, 2*100000}とか
posted at 23:39:08
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ ところでさっきの、Aの先頭だけ3にすると落ちる……?
posted at 23:37:42
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ 配列だけでそこそこ簡単に作れるので(ちょうどDiff水色くらいの難易度?)、頑張って作ってみると良いかも。マラソンとかでちょこちょこ使う。
posted at 23:33:17
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ とりあえず逆順を入れないと通らないとおもいます。(最後の1手がO(N^2)になるので)
逆順入れなくても通る方法はあって、「片側をsameのもののみから選ぶ」ってしてあげると間に合うので、その乱択を想定していた
posted at 23:30:52
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ あ、ソートして逆順が強いのか。なるほどねえ。頑張れば落とせそう
posted at 23:28:14
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ あ、ちゃんと出るのね。ならおっけー。
(なんか計算量ダメな気がしてたけど大丈夫らしいので見積もりに困っている)
posted at 23:25:22
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ これってA,Bともに1が10万個、2が10万個、みたいな奴だいじょぶ?
posted at 23:16:05
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ なんか嘘な気がしてきた(落とせるのでは?)
posted at 23:14:53
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ おおよそそんな感じだけど、「悪くなる変化は行わない」がないと落ちるので、そこが本質的な改善かなあ。これが出来てれば大体O(NlogN)くらいで終わるはず。大体だけど。
posted at 23:08:39
chokudai(高橋 直大)@AtCoder社長@chokudai
よーしABCトーナメント2回戦突破!!!ってなんでやねん!w
https://abc.kenkoooo.com/#/tournament/1
posted at 23:05:35
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ (ちなみにアルゴリズムの説明の時に日本語での説明を放棄するのはあんまり好きじゃないのでちょっとおこ気味に対応しました。ごめんね><)
posted at 23:03:46
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ まぁなんか「どの乱択の話?」って言うのがあると思っていて、この乱択は計算量の削減パートがちゃんと入っているので、まぁ通るのが当たり前だと認識している感じです。
(なので込みで1000だとおもってました)
posted at 23:03:12
chokudai(高橋 直大)@AtCoder社長@chokudai
乱択解法色々あるけど、その乱択で最も計算回数の期待値が高いテストケースを考えてみて、その期待値を求めてあげれば、大体通るものになってると思います。ちゃんと計算してね><
posted at 23:02:18
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ 平均計算量ならもちろん出せます
posted at 23:00:33
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ はい、これの計算量は?
posted at 22:59:25
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ ちょっと行数見て読む気がしなくなったので読まないけど、乱択でもバリエーションが大量に存在するので、単に「乱択」って言うだけだと何を指してるかわかんないです。
posted at 22:55:48
chokudai(高橋 直大)@AtCoder社長@chokudai
@kichi2004_ 乱択は何を表しますか
posted at 22:53:53
chokudai(高橋 直大)@AtCoder社長@chokudai
F問題1000人くらい正解出そうだなって思ってたので見積もりが下手
C問題は3問目にしてはだいぶ難しい、というか数学的工夫を要求されるなあ、と思っていた
posted at 22:52:18
chokudai(高橋 直大)@AtCoder社長@chokudai
はっじまっるよー!
https://atcoder.jp/contests/abc178
posted at 20:54:57
chokudai(高橋 直大)@AtCoder社長@chokudai
今日だよー!
https://twitter.com/atcoder/status/1305098820758335488…
posted at 20:00:22
chokudai(高橋 直大)@AtCoder社長@chokudai
あーだこーだー、次回もACLで長引きそうな気がするからゲストなしのつもりだけど、そろそろゲスト回やりたいなー。
posted at 12:29:28