D1まで。
コンテスト後のツイート
D1 隣接三項を聞く。x,x+1,x+2とx+1,x+2,x+3が違う答えなら、x+1とx+2は違う値なので、それを使って判定していく。
— titia (@titia_til) December 16, 2021
D2. Too Many Impostors (hard version)
D1のように隣接三項を聞いていく方針でも、0や1の個数が(n/3, 2*n/3)ということを使っているため、同じ方針でいけるのかなー、と思うとそれではダメ。
さらに3/nということを強く利用するため、全体を3個ずつに分けるのがポイントだった。3個ずつの組のn/3個あると見て、その三つずつを全部聞くと、0や1の個数が(n/3, 2*n/3)なためその返答に0も1も含まれる。
そして、その組についてもう6回くらい聞くと、0や1を少なくとも一つ以上確定できる。
後はそれを利用するのだが、最初に聞いた3個組が0か1かを利用すると、各組二回ずつ聞いて答えを求めることができる。
E. Christmas Chocolates
解説AC。
操作により、xからxより小さい数へ遷移するのは一通り。それにより作られる木の直径が答え。シンプルだが、そのような頂点・辺からなるグラフだけ考えれば良い、というのが難しい。
ただ、思いつくのは難しくても、実験すれば気付けたような気もする。何も思い浮かばない時は実験するのが大事。
0 件のコメント:
コメントを投稿