No.2844 Birthday Party Decoration
タグ : / 解いたユーザー数 81
作問者 : 👑
![AngrySadEight](https://pbs.twimg.com/profile_images/1774819988135927808/f4w6hc33.jpg)
![Ayuna](https://pbs.twimg.com/profile_images/1629119004798488577/7L90VDCi.jpg)
![torisasami4](https://pbs.twimg.com/profile_images/1102585635137679360/edE9JNpl.png)
問題文
無限に長い数直線上に,Alice の家と店があります.Alice の家は,数直線上の座標 $X$ にあります.また,全ての非負整数座標上に $1$ つずつ店があります.
Alice は,家で誕生日パーティを開くにあたり,装飾品を買うことにしました.
装飾品は $N$ 種類あり,それぞれの装飾品を購入できる店の条件は以下の通りです.
- $i$ 番目の装飾品は,店の座標 $x$ が $x \& 2^{c_i} \neq 0$ を満たす場合に,またそのときに限り購入可能である.
ただし,$a \& b$ で非負整数 $a$ と $b$ のビット単位 AND を表します.
Alice は,次に示す行動を $0$ 回以上の好きな回数,また好きな順番で行うことができます.
- 移動:好きな整数 $y$ をひとつ選ぶ.Alice の今いる座標を $x$ としたとき,Alice の座標を $x + y$ に変化させる.
- 購入:Alice の今いる座標が非負整数のときにのみ行える.今いる座標にある店で購入できる商品を $1$ 個選び,購入する.
ここで,移動距離を,すべての移動における選んだ値の絶対値の総和と定義します.
最初,Alice は自身の家にいます.Alice が行動を繰り返すことにより,全ての種類の装飾品を $1$ 個ずつ購入して家に戻ってくるまでの移動距離として考えられる最小値を求めてください.
$T$ 個のテストケースが与えられるので,それぞれについて答えてください.
ビット単位 AND とは
$2$ 個の非負整数 $a$ と $b$ のビット単位 AND $a \& b$ は,以下のように定義されます.
- $a \& b$ を $2$ 進表記した際の $2^k$ の位の値は,$a, b$ それぞれを $2$ 進表記した際の $2^k$ の位の両方が $1$ であれば $1$,そうでなければ $0$ であるとする.
- 例えば,$3 \& 5 = 1$ となる.($2$ 進表記すると $011 \& 101 = 001$)
制約
- 入力は全て整数である.
- $1 \leq T \leq 1000$
- $1 \leq N \leq 60$
- $0 \leq c_1 < c_2 < \dots < c_N < 60$
- $0 \leq X < 2^{60}$
入力
入力は以下の形式で標準入力から与えられる.
$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$
各テストケースは以下の形式で与えられる.
$N$ $X$ $c_1$ $c_2$ $\dots$ $c_N$
出力
$T$ 行出力せよ.$i(1 \leq i \leq T)$ 行目には,$i$ 番目のテストケースにおける答えを出力せよ.
サンプル
サンプル1
入力
4 2 10 0 2 1 0 3 4 15 0 1 2 3 5 20240822 0 5 7 8 18
出力
4 16 0 2
$1$ 個目のテストケースについて,次のように行動するのが最適です.
- まず,家から座標 $11$ に移動する.
- 次に,座標 $11$ にある店で $1$ 種類目の装飾品を購入する.
- 次に,座標 $11$ から座標 $12$ に移動する.
- 次に,座標 $12$ にある店で $2$ 種類目の装飾品を購入する.
- 最後に,座標 $12$ から家に戻る.
このときの移動距離は,$4$ となります.なお,この一連の流れを図に表すと以下の通りとなります.
$2$ 個目のテストケースについて,装飾品を買える家から最も近い店は座標 $8$ にある店です.したがって,座標 $0$ から座標 $8$ に移動し,座標 $8$ で装飾品を購入し,座標 $8$ から座標 $0$ に移動する,という行動が最適です.このときの移動距離は $16$ となります.
$3$ 個目のテストケースについて,Alice の家と同じ座標にある店で全ての装飾品を購入できます.したがって,移動距離の最小値は $0$ となります.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。