CSA Round #64

はむこ @hamko_intel

問題文がインタラクティブに与えられるマジ？面接じゃん

iwashi31 @iwashi31

C、結局何が remove されるんだ…

nmnmnmnmnmnmnm @enuemuenuemuenu

CSAやってたのか。

(nは自然数) @n_vip

A,B,Cがdistinctである必要があるかですが、同じだったら同じやつになるので質問するよりもクエリ投げる関数内で場合分けしたほうがお得（validだったとしてもクエリ回数が節約できる）

競技プログラミング @LatteMalta

E:次を繰り返す 1.サイズN/2のグループ2つに分割する(ランダムに) 2.それぞれについてクエリを投げる 3. 50％くらいの確立でspyAとspyBを分離できる。分離できたかどうかは、簡単にわかる。分離出来ていたら、Aonlyのグループの人全員にフラグA、Bonlyのグループの人全員にフラグBを立てる

競技プログラミング @LatteMalta

これをひたすらやると、spy以外の人は、十分な確率でフラグA,Bが両方立っている。逆に、片方のフラグしかたっていない人がspy

有為 @uwitenpen

Eは、ランダムにspyが1匹ずつ含まれるように分割したあと、残りを絞る際にもう一方の集合も含めつつやるとうまくいった

iwashi31 @iwashi31

わけがわからないよ

sigma @sigma425

@LatteMalta え、ランダムで大丈夫なんですか

(nは自然数) @n_vip

Cは「任意のvについて、0とv間のパスがちょうど1個」が木と同値になる気がしたのでそうした

iwashi31 @iwashi31

そういえばBもひどかったなァ

競技プログラミング @LatteMalta

@sigma425 えーなんか2回投げたら通りました(最悪)

(nは自然数) @n_vip

えーランダムはやめて（まあランダムを殺すジャッジを作るのが死ぬほど大変だろうけど）

sigma @sigma425

うーんまあジャッジ適切に書くの難しいからなあ もしかしたらジャッジが意地悪しても大丈夫なのかもしれないけど

有為 @uwitenpen

@sigma425 一方ともう一方両方にクエリを投げればOK

(nは自然数) @n_vip

iビット目が立っているかで2つに分けると、15*2回のクエリでA xor Bが求まります。A xor B == U xor V となるような各(U,V)について、両方含める/片方だけ含めるという場合をこれもやはりiビット目で分けて全部試します。

satanic@研究💪 @satanic0258

(試されてるのかな)

olphe @_olphe

1803->1773

satanic@研究💪 @satanic0258

C解けた， FOR(i,2,n+1)while(!query(1,i)); みたいなのでいいのかぁ

有為 @uwitenpen

クソすぎ

sigma @sigma425

@uwitenpen そういう意味ではなくて、ジャッジが(spyA,spyB)を出来るだけ最悪に決めようとadapt した時にどのくらい分離を遅く出来るかが気になりました(ので2進数でkビット目が経ってるか でやりました)

satanic@研究💪 @satanic0258

Congratulations! Your rating has increased by 24 points 😄. Keep it up!

kmjp @kmjp_pc

なんかここ数回CSAは調子よくないなぁ。単に強い人が増えてきただけかもしれないけど。

(nは自然数) @n_vip

51上がったがまだ赤に戻してくれない

有為 @uwitenpen

Dのsample2が通らなかったんだけど何すればよかったんだろう