geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Beginner Contest 270 参加記録

ABC ゲーム

コンテストページ:https://atcoder.jp/contests/abc270

コンテスト中AC:A〜D
Eはコンテスト中は実装ミスで間に合いませんでしたが、コンテスト後に解けたので書いておきます。

D - Stones
E - Apple Baskets on Circle

D - Stones

石が $X$ 個の状態からは、石が $X-A_1,X-A_2,\cdots ,X-A_K$ 個の状態に遷移します。
そのため、石が少ない時の状態から順に高橋くんが取れる石の個数を決定していくことができれば、 $O(NK)$ くらいで解けそうだということがわかります。

普通のループを使ったDPでも解けそうですが、コンテストではメモ化再帰を使いました。

メモ化再帰にあたり、

$f(X):$ 石が残り $X$ 個の状態で、高橋くんが取れる石の最大個数

とおいて計算していきたいところですが、高橋くんのターンか青木くんのターンかで、戦略が異なります。
すなわち、

高橋くんは、高橋くんが取れる石の個数を最大化したい
青木くんは、高橋くんが取れる石の個数を最小化したい

そのため、どちらのターンなのかという情報を持たせます。

$f(X,Y):$ 石が残り $X$ 個、ターンの状態が $Y$ で、高橋くんが取れる石の最大個数。但し、 $Y=\{0,1\}$ で、 $Y=1$ の時は高橋くんのターンで、 $Y=0$ の時は青木くんのターン。

それでは、遷移を考えます。
各ターンにおいて、 $m$ を $1\leq m \leq K$ かつ、 $A_m \leq X$ を満たす最大値とします。

高橋くんのターンの場合
取れる石の個数を最大化します。また、石を取った時に、高橋くんがとれる石の個数に加算できるので、以下のようになります。
$f(X,\ 1) = max\{f(X-A_1,\ 0)+A_1,\ f(X-A_2,\ 0)+A_2,\ \cdots ,\ f(X-A_m,\ 0)+A_m \}$
青木くんのターンの場合
取れる石の個数を最小化するので、以下のようになります。
$f(X,\ 0) = min\{f(X-A_1,\ 1),\ f(X-A_2,\ 1),\ \cdots ,\ f(X-A_m,\ 1) \}$

遷移は以上です。
また、再帰の終了条件として、石が $0$ 個の時の値、 $f(0,0)=f(0,1)=0$ を設定しておきます。

計算量は最初にも書きましたが、各個数において $K$ 回の計算となるので、 $O(NK)$ と思います。

Submission #35156369 - TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest 270)
↑はコンテスト後に微修正した実装です。

E - Apple Baskets on Circle

最終的な移動回数を $X$ とし、 $X$ を $N$ で割った商を $q$ 、余りを $r$ とします。これは、 $q$ 周してから残り $r$ 回移動するという風に考えられます。
$0\leq r \lt N$ であることから、 $q$ を求められれば、残り $r$ 回はシミュレーションできます。

$q$ を求める方法を考えます。
例として $A=\{5,1,3,3\}$ を考えます。

1週目
$A=\{4,0,2,2\}$ となり、食べたりんごの数に $4$ 個加算される。
2週目
$A=\{3,0,1,1\}$ となり、食べたりんごの数に $3$ 個加算される。
3週目
$A=\{2,0,0,0\}$ となり、食べたりんごの数に $3$ 個加算される。
4週目
$A=\{1,0,0,0\}$ となり、食べたりんごの数に $1$ 個加算される。
5週目
$A=\{0,0,0,0\}$ となり、食べたりんごの数に $1$ 個加算される。

加算するりんごの数の変化点に注目すると、

最初の $A$ の最小値である $A_2=1$ が $0$ となるまで、空でないかごの個数分 $4$ 個を加算する
$A_2$ が空になった時点の $A$ の最小値である $A_3=A_4=2$ が空となるまで、空でないかごの個数分 $3$ 個加算する
$A_3,A_4$ が空になった時点の $A$ の最小値である $A_1=2$ が空となるまで、空でないかごの個数分 $1$ 個加算する

このように、りんごの数が最小となるかごが空になるまでは同じ分だけりんごの数が加算されるので、まとめて考えることができます。
そこで、以下のように操作していくと、食べたりんごの数と現在何周したかを計算していくことができます。

$A$ から最小値 $A_i$ を取得する。ここから $A_i$ 周して、合計 $|A|\times A_i$ 個のりんごを食べる。その後、 $A$ の $i$ 番目の要素を削除し、全ての要素から $A_i$ を引く。

最小値の取得や値の削除は優先度付きキューにより実現できます。
あとは、 $A_i$ を引く操作に時間がかかるので、今までに何周したのかというのを $R$ に記録します。すると、以下のようにできます。

$A$ から最小値 $A_i$ を取得する。 $A_i-R$ 周して、 $|A|\times (A_i-R)$ 個のりんごを食べたことにする。その後、 $R\leftarrow R+A_i$ と更新し、 $A$ の $i$ 番目の要素を削除する。

さて、この操作を繰り返すと、どこかの時点で「次の操作をすると食べたりんごの数が $K$ 以上となる」状態になります。
この状態からあと何周必要かを計算します。残りの周回数は、この時点での $A$ の最小値以下であることが保証されます。

この時点からの残りの周回数を $m$ とおくと、以下の不等式が成り立てばよいです。

$|A|\times m \leq K$

よって、

$m=\lfloor \frac{K}{|A|}\rfloor$

です。
よって、先ほどの操作と今回の操作で得られた値を合計すれば、 $q$ が求まります。

あとは、 $q$ 周した状態(元の $A$ のすべての要素から $q$ を引いた状態)からりんごの数が $K$ となるまでシミュレーションすればよいです。
長くなりましたが、要点をまとめるとこのような流れになります。

$A$ の最小値が0になるまで周回するという操作を繰り返す
上記の操作でりんごの食べた数が $K$ 以上となる直前で操作を終了し、残り何周必要かを計算する
全体で何周すれば良いかがわかったので、その分だけ周回した後から、残りをシミュレーションする

Submission #35138460 - TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest 270)