geam1113’s diary

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

AtCoder Beginner Contest 278 備忘録

ABC ゲーム 巡回セールスマン問題 ビットDP 二次元累積和 後退解析

コンテストページ:AtCoder Beginner Contest 278 - AtCoder
コンテスト中AC:A〜D
E,Fはコンテスト後に自力AC

E - Grid Filling

このユーザ解説と同じ方法で解きました。
想定解法は二次元累積和だったようです。
実装:Editorial - AtCoder Beginner Contest 278

二次元累積和の構造体を作って解いてみました。
実装:Submission #36758941 - AtCoder Beginner Contest 278

F - Shiritori

後退解析+bitDP(巡回セールスマン問題)の考え方で解けます。

問題を有向グラフに言い換えておきます。

  • S_iを頂点iとする。
  • S_iを言った後にS_jを言える場合、頂点iから頂点jへ向かう有向辺があるとする。
  • 有向グラフ上を交互に移動することを繰り返し、移動できなくなった方が負け

制約上、bitDPが疑われるので、その要領で考えてみます。

dp[S][i]:=これまでに訪問した頂点集合がSで頂点iで自分のターンを終えたとき、勝てるなら1、負けるなら0

まず、"次のターンでこれ以上移動できる頂点がない"となった時点で勝ちが確定します。そこで、訪問した頂点数が多い順から勝敗を確定していけそうです。
これが後退解析にあたります(おそらく)。

では、勝敗の確定条件を考えます。
自分が頂点uで移動を終え、uから移動可能であって、かつ未訪問の頂点がv_1,\ v_2,\ \cdots ,\ v_kであるとします。

このうち、いずれか1つでも勝ちとなる頂点が存在する場合、相手はその頂点に移動すれば勝てるので、自分は負けとなります。逆に負けの頂点しかなければ、勝てます。
また、訪問可能な頂点がない場合も自分が勝ちとなる条件となります。

後はこれに従って、bitDPを逆に回していきます。
最終的に"頂点が1つだけ訪問済みである"という状態のDP値(例えば、N=3ならdp[001][0], dp[010][1], dp[100][2]。なお、1つ目のインデックスはbit列)について、頂点1,\ 2,\ \cdots ,\ Nのうち、ただ1つでも勝ちがあれば太郎くんが勝ちます。

実装: Submission #36721268 - AtCoder Beginner Contest 278

余談で、DPの別の言い方を示しておきます。

dp[S][i]:=これまでに訪問した頂点集合がSで頂点iで自分のターンが回ってきた時、勝てるなら0、負けるなら1

この場合、移動できなくなったら負けるので、訪問可能な頂点がなければ負けです。また、相手のターンになったときに負けとなる頂点が1つでもあれば自分は勝てます。

最終的に"頂点が1つだけ訪問済みである"という状態のDP値について、頂点1,\ 2,\ \cdots ,\ Nのうち、ただ1つでも負けがあれば、太郎くんが勝ちます(1つだけ訪問済みの状態で順番がくるのは次郎くんであるため)。
実装:Submission #36708784 - AtCoder Beginner Contest 278

AtCoder Beginner Contest 277 備忘録

ABC ダイクストラ Union-Find 拡張ダイクストラ

コンテスト中AC:A〜E

D - Takahashi's Solitaire

コンテスト後に考え直したので、メモしておきます。

一旦modを無視します。
以下の問題を解けばこの問題に答えられます。

Aから要素を順に選び、B=\{B_1,\ B_2,\ \cdots ,\ B_m\}とする。但し、Bは以下の条件を満たさなければならない。

1\leq i\leq m-1について、B_{i+1} - B_i \leq 1
要素の和が最大となるBを求めよ。

ここで、Aを昇順ソートしておくと、BはAの連続部分列となります。

また、和を最大化したいので、連続部分列は条件を満たす限り伸長させた方が良いです。そのため、各要素は2つ以上の連続部分列に属する必要がありません。

そこで、Aの連続部分列を探索する際、例えば、A_i,\ A_{i+1},\ \cdots ,\ A_jが可能な限り伸長した連続部分列であるなら、次の連続部分列の探索はA_{j+1}から再開すれば良いです。 探索範囲を右に進めるだけとなるので、O(N)となります。

modの部分ですが、これはA_1 = 0かつA_{N} = M-1の場合に、これらを含む連続部分列を繋げるようにすれば解決になるわけですが、以下の2パターンで実装してみました。

解決方法1
配列が円環となることが想定される場合の常套手段ですが、Aを昇順ソートしたものを2つ繋げます。これに対して連続部分列を探索すれば、modを考慮した場合と同様の結果が得られます。
但し、Aに0,\ 1,\ \cdots ,\ M-1の全てが含まれる場合は、Aの要素の和を超えてしまうので注意が必要です。
実装例:Submission #36484745 - Daiwa Securities Co. Ltd. Programming Contest 2022 Autumn (AtCoder Beginner Contest 277)

解決方法2
Union-Findを用いた解法です。0-indexedとします。
Aを昇順ソートし、0\leq i \leq N-1について、A_i = A_{(i+1)\ mod\ N}または、(A_i +1) \ mod M = A_{(i+1)\ mod\ N}\ mod Mが成り立つなら、Union-Findで同一連結成分とします。

Union-Findにおける連結成分の和を計算していけば、答えを得ることができます。

実装例:Submission #36488298 - Daiwa Securities Co. Ltd. Programming Contest 2022 Autumn (AtCoder Beginner Contest 277)

E - Crystal Switches

解法はこちらの公式解説とほぼ同じなので、省略します。
実装では、dist[i][j]を、頂点iでスイッチの状態がjの時の移動回数の最小値、としました。
また、スイッチを押す操作もダイクストラ法で頂点uからvに移動する際に考慮されるようにしました。

提出コード:Submission #36446787 - Daiwa Securities Co. Ltd. Programming Contest 2022 Autumn (AtCoder Beginner Contest 277)
スイッチの状態の表現が公式解説と逆なので、ご注意ください。

AtCoder Beginner Contest 275 備忘録

ABC 部分和DP 計算幾何 DP 期待値DP

コンテストページ:AtCoder Beginner Contest 275 - AtCoder
コンテスト中AC:A,B,D
コンテスト後AC:E,F(自力)
Cでハマったのと、Eで回数制限があることを忘れて考察してしまいました。

C - Counting Squares

  • 点P_0,P_1,P_2,P_3が、正方形の頂点を半時計回りに順番に並べた点である

これが成立するには以下の条件を満たす 必要があります。

  1. 辺の長さが等しい
  2. 凸多角形
  3. 辺のなす角が全て90°

これは、0\leq i \leq 3の全てについて、ベクトル

\vec{v_0} = \vec{P_{(i+1)\ mod\ 4}P_i}
\vec{v_1} = \vec{P_{(i+2)\ mod\ 4}P_{(i+1)\ mod\ 4}}

が以下の3つを満たすことと同値です。

  1. |\vec{v_0}| = |\vec{v_1}|
  2. \vec{v_0}\times \vec{v_1} \lt 0
  3. \vec{v_0}\cdot \vec{v_1} = 0

2は外積(sin\theta)、3は内積(cos\theta)です。
1、3は正方形なので自明かと思います。2は1本目の辺と2本目の辺の位置関係が半時計回りである必要があるということです。

2は要らなくて3だけでよいのではと思ってしまいますが、内積だけだと時計回りの角度が半時計回りの角度がわからないので必要になります。

全ての点のあり得る4つの組に全てについて、上の条件を満たすものをカウントすると、同じ正方形が4回数えられるので、条件を満たす個数を1/4したのが答えとなります。

コンテスト中は3の条件が必要だと思っておらず、解けませんでした。
提出コード:Submission #36108492 - AtCoder Beginner Contest 275

D - Yet Another Recursive Function

メモ化再帰の問題。種類数の見積もり方法がわからずにとりあえず通しました。見積もり方法は公式解説参照。

提出コード:Submission #36064977 - AtCoder Beginner Contest 275

E - Sugoroku 4

操作回数を考慮しない点で異なりますが、期待値DPと同じような考え方ができます。
N=10,M=3の例で考えてみます。

まず、DPを以下のようにしてみます。
dp[i]:=マスiからゴールできる確率

例えば、i=1なら、
dp[1] \leftarrow \frac{1}{M}(dp[2]+dp[3]+dp[4])
という風に計算できます。
dp[10]=1なので、後ろから順に更新できそうと思ってしまいますが、今回はNを超える場合には戻ってくるので、例えばi=9の場合、

dp[9] \leftarrow \frac{1}{M}(dp[10]+dp[9]+dp[8])

となり計算できません。
問題文をよく読むと操作回数に限度があります。操作を1回すると残りの操作回数が1減るので、残りの操作回数が0となってしまえばそれ以上の操作はできず、確率が確定します。
そこで、DPに操作回数の情報を持たせ、以下のように変更します。
dp[i][j]:=残りの操作回数がi回で、マスjからゴールできる確率

初期値は、

  • 0\leq j \leq Kについて、dp[i][N]\leftarrow 1
  • 0\leq j \leq N-1について、dp[0][j]\leftarrow 0

と、設定します(その他もすべて0で初期化します) 。
テーブルの更新はメモ化再帰でもいけそうですが、実装では普通のループにしました。

操作回数i=1,\cdots , Kの順に、マスj\ (0\leq j\leq N-1)について、
dp[i][j]\leftarrow \frac{1}{M}(dp[i-1][j+1] + dp[i-1][j+2] + \cdots + dp[i-1][j+M])

と更新します。
なお、j+k\gt N\ (1\leq k \leq M)の場合には戻るようにする必要があります。

答えはdp[K][0]の値です。
計算量はO(KNM)です。これでも通りましたが、和を求める部分は区間和となっているので、累積和を使えば、O(KN)に落とせそうです。
提出コード:Submission #36076090 - AtCoder Beginner Contest 275

F - Erase Subarrays

部分和DPを応用します。今回DPテーブルには操作回数の最小値を記録します。

普通の部分和DPのように考えると、

dp[i][j]:=Aのi番目までの要素まででできる部分列の和がjであるときの操作回数の最小値

となりますが、このままだと操作回数の最小値は求められないので、どうするかを考えます。

例えば、N=10で2,3,6,8番目の要素で部分列を作ったとします。i番目を選んだら1、選ばなかったら0とした数列Bを考えます。

B=\{0,1,1,0,0,1,0,1,0,0\}

となり、この時の操作回数の最小値は、閉区間[1,1],\ [4,5],\ [7,7],\ [9,10]に操作したときの 4回です。

実は、最初の0を除いてB_i = 1\wedge B_{i+1}= 0となる数をカウントすれば最小の操作回数に一致します。最初の0のみ、例外として+1しておきます。

以上より、i番目の要素を部分列として選んだ状態と選んでいない状態の2つをDPの情報として追加すれば良いです。すなわち、

dp[i][j][k]:=Aのi番目までの要素まででできる部分列の和がjであり、かつ状態がkの時の操作回数の最小値
但し、k=\{0,1\}で、k=1ならi番目を選んでおり、k=0なら選んでいないことを表す。

初期値は、
dp[0][A_0][1]\leftarrow 0
dp[0][0][0]\leftarrow 1
とし、他は\inftyにしておきます。
遷移については実装を見てもらう方が早いと思います。
ポイントとしては、i-1番目がk=1の状態からi番目がk=0の状態に遷移する時に操作回数に+1します。

なお、3次元配列をdp[N][M+1][2]という感じで領域を確保すると、A_0 \gt Mの場合に配列外参照となるので注意が必要です。
提出コード:Submission #36130326 - AtCoder Beginner Contest 275

AtCoder Beginner Contest 274 メモ

ABC 部分和DP イベントimos DP ビットDP 巡回セールスマン問題

コンテスト中AC:A〜D
コンテスト後AC:E,F (いずれも自力)

D - Robot Arm 2

過去問に類題があります。
過去問のリンク (ネタバレ注意)

p_2は、(A_1,\ 0)

p_3としてありうる座標は、
(A_1,\ A_2),\ (A_1,\ -A_2)

p_4としてありうる座標は、
(A_1+A_3,\ A_2),\ (A_1-A_3,\ A_2),\ (A_1+A_3,\ -A_2),\ (A_1-A_3,\ -A_2)

p_5としてありうる座標は、
(A_1+A_3,\ A_2+A_4),\ (A_1+A_3,\ A_2-A_4)
(A_1-A_3,\ A_2+A_4),\ (A_1-A_3,\ A_2-A_4) (A_1+A_3,\ -A_2+A_4),\ (A_1+A_3,\ -A_2-A_4) (A_1-A_3,\ A_2-A_4),\ (A_1-A_3,\ -A_2+A_4)

ここまでで、i\geq 3であるp_iについて、以下の法則が考えられます。

  • iが奇数なら点を配置できるy座標のみが変化し、偶数ならx座標のみが変化する。
  • 配置可能なx座標の集合をX、y座標の集合をYとすると、XとYから得られる全ての組が示す座標に点を配置できる。

これが一般のi\ (i\geq 3)で成り立つことは帰納法などによって証明できそうですが、ここでは省略します。2番目の法則はiからi+1の変化を図に書いてみるとわかりやすいです。

2番目の法則から、配置可能な座標について、x,y座標を独立に考えれば良いことがわかります。

では、配置可能な座標をどう計算していくかですが、これは部分和DPの応用で解決できます。
すなわち、p_iについてx座標のkに配置可能であればdp_x[i][k]=trueとなるような配列を用意し、これを更新していきます。1番目の法則から偶奇に合わせて更新する座標を変更します。

実装のポイントとして、負の座標は配列に直接保存できないので、定数を加算して平行移動し、全て非負の座標となるようにします。
今回の場合、座標は大雑把に見積もっても-10^4〜10^4の範囲内です。そこで、配列に10^4の2倍+αの領域を確保し、原点が(10^4,\ 10^4)となるように座標に10^4を加算すると良いです。

DPテーブルの更新時に配列外参照をしないようにするチェックを忘れてWAを量産していました。

Submission #35893208 - キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274）

E - Booster

巡回セールスマン問題の応用問題です。巡回セールスマン問題はbitDPで解くことができますが、ネットで調べると出てくるので、ここでは詳細は割愛します。

今回は、N+M頂点であるとみなして、bitDPを解きます。普通の巡回セールスマン問題と異なる部分は、以下のとおりです。

  1. 宝箱に訪れた個数によって、移動速度が異なる
  2. 宝箱には行かなくてもよい
  3. 原点から出発し、原点に戻る

それぞれの自分の解決策を示します。

宝箱に訪れた個数によって、移動速度が異なる

これからの説明では0-indexedとします。
まず、DPテーブルは以下のようになります。

dp[S][i]:=訪問状態を示す冪集合Sの状態で頂点iに居る時の移動時間の最小値

N=3,\ M=2なら、0,1,2ビット目を街に、3,4ビット目を宝箱に割り当てます。
例を示すと、街0と宝箱0,1に訪問済みなら、その状態を表すビット列Sは、11001です。

これからの説明でDPテーブルの行のインデックスはビット列とします。

DPテーブルの更新の際に、宝箱に対応するビットの1の個数をカウントし、頂点間の距離を個数+1で割れば良いです。
例えば、上の例で頂点0,2の座標がそれぞれ(x_0, y_0),(x_2,y_2)であり、訪問状態を表すビット列が11001の状態で、頂点0から2に移動する場合、
dp[11101][2] \leftarrow min(dp[11101][2], dp[11001][0]+\frac{\sqrt{(x_2-x_0)^2 +(y_2-y_0)^2}}{2+1})
と更新します。

宝箱には行かなくてもよい

例えば、先程の例と同じ場合、街に対応する0,1,2ビット目が1なら、宝箱に対応する3,4ビット目はなんでもよいです。

従って、??111となるような全ての状態に対して、原点に戻るまでの最短時間を調べれば良いです。

原点を出発し、原点に戻る

原点を出発する代わりに、初期値として各頂点のみが訪問済みの状態に、原点からの移動時間を設定すれば良いです。
例えば、N=3,\ M=2で、街0の座標が(x_0,y_0)なら、

dp[00001][0] \leftarrow \sqrt{(x_0-0)^2+(y_0-0)^2}

という感じで設定します。これを各頂点について設定します。

原点に戻るのは、各状態の最小の移動時間を求めた後、原点への移動時間を考慮すれば良いです。

例えば、上の例と同じ条件で考えると、dp[10111][0]はすべての街(+宝箱1)を訪れ、最後に街0にいる時の最小移動時間です。

しかし、このままこの状態の最小移動時間にするのではなく、dp[10111][0]+\frac{\sqrt{(0-x_0)^2+(0-y_0)^2}}{2}を、この状態における最終的な最小移動時間とします。

なお、原点を頂点として追加した実装だとTLEになりました。

https://atcoder.jp/contests/abc274/submissions/35914594

F - Fishing

最適解で得られた魚を座標の昇順に並べたものをY_1,Y_2,\cdotsとします。
これらの魚を捕獲する際、始点となる実数xをx=Y_1として差し支えありません。
これより、魚iを始点として捕獲した場合のN通り調べれば良さそうだとわかります。

ただし、前提として、各魚を始点として捕獲する場合の最適解が求められる必要があります。
最適解の求め方を示します。

魚iを始点として魚j捕獲する場合、魚jが時間s_jからe_jまで捕獲可能であるという閉区間[s_j,e_j]が、例外を除いて存在します。

そのため、以下の問題を解ければよいです。

正方向に伸びる数直線上に複数の区間と、区間に対応するスコアが与えられる。座標を1つ選ぶと、その座標を含む区間のスコアが得られる。スコアを最大化せよ。

これはいもす法によって解けます。

充分に小さい時間を\epsilonとします。区間[s_j , e_j]とその区間で得られるスコアW_jが与えられた場合に配列に(s_j, W_j)と(e_j +\epsilon, -W_j)という組を追加します。

全ての区間について追加し終えた後、組の第一要素をキーとして昇順にソートします。その後、第二要素の累積和を計算します。
累積和を計算した時に最大となった値が得られる最大のスコアであり、これが最適解です。

このいもす法の計算量はソート部分がボトルネックとなってO(NlogN)です。各魚についてこれを計算するので、計算量はO(N^2 logN)となり間に合います。

区間の求め方ですが、魚iと魚jの最初の座標と速度の関係で場合分けが必要です。また、区間そのものが存在しない場合もあります。

始点s_jについては、

  • X_i \leq X_j \leq X_i +Aなら、s_j = 0
  • 魚iが魚jに追いつくなら、X_i +A+ s_j V_i = X_j + s_j V_jを解いて、s_j = \frac{X_i -X_j+A}{V_j - V_i}
  • 魚jが魚iに追いつくなら、X_i + s_j V_i = X_j + s_j V_jを解いて、s_j = \frac{X_i -X_j}{V_j - V_i}

終点については、

  • X_i \leq X_j \leq X_i +AでかつV_i = V_jなら、e_jは存在しないことにするか、e_j =\inftyとする
  • 魚jが魚iを引き離すなら、X_i +A+ s_j V_i = X_j + s_j V_jを解いて、s_j = \frac{X_i -X_j+A}{V_j - V_i}
  • 魚iが魚jを引き離すなら、X_i + s_j V_i = X_j + s_j V_jを解いて、s_j = \frac{X_i -X_j}{V_j - V_i}

という感じで場合分けします。

Submission #35965103 - キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274）

AtCoder Beginner Contest 273 参加記録

永続データ構造 ABC 座標圧縮

2022/10/20 Eに永続スタックによる解答を追記

コンテストページ:Panasonic Programming Contest 2022(AtCoder Beginner Contest 273) - AtCoder

コンテスト中AC:A〜D
Eもコンテスト後に自力で解けました。

D - LRUD Instructions

壁を行と列にわけて保存し、移動方向に合わせて直近の壁を二分探索する、という手法は典型と言えると思います。

今回は、行及び列が非常に多いので、単純に行または列の番号をインデックスとした二次元配列に壁を保存していくことができません。
公式解説では、mapが遅いなと思うことがあり、座標圧縮で対応しました。しかし、その分、実装が複雑になってしまい手間取りました。

また、壁の記録には自作の平衡二分探索木(スプレー木)を使用しました(値の重複を許す、多重集合で実装しています)。ここでは詳細は書きませんが、「x以下／未満の最大値を取得する」という操作をサポートします。
動作は保証できませんが、自由に使用して問題ありません。
Submission #35688615 - Panasonic Programming Contest 2022(AtCoder Beginner Contest 273)

E - Notebook

木っぽい感じだと思ったのですが、ポインタを使うような問題をあまり見たことがなかったので、ポインタを使用しない実装方法で解きました。

公式解説の補足を見て、永続スタックについて知りましたが、記載する実装方法はポインタを使用していないだけで、内容は永続スタックと同じでした。

永続スタックの参考↓
あなたの庭に永続データ構造を飾りませんか？ - noshi91のメモ

では、実装方法を書きます。

まず、使用する配列や変数です。
- 配列V：クエリで追加した値を追加順に保存する
- 変数cur：各クエリ処理において、Aの末尾の値が保存されているVのインデックスを保存する
- 配列BK：BK_iにはV_iが追加される直前のcurが保存されるような配列
- ハッシュマップM：ページをkeyとしてcurを保存する

V_0 = -1,\ BK_0 = 0と初期化しておきます。これはAが空であることを示す番兵となります。
後述するcurを戻す処理をどれだけ行ってもV_0に留まり続けることが可能です。

各クエリの処理です。

  • ADD x
    Vの末尾にxを追加します。xの直前にAの末尾であった値のVのインデックスはcurなので、BKの末尾にcurを追加します。新たなcurはVの末尾のインデックスとなるよう更新します。

  • DELETE
    現在のAの末尾の値V_{cur}を削除する代わりに、１つ前に末尾だった値に戻ればよいです。すなわち、cur\leftarrow BK_{cur}と更新します。

  • SAVE y
    ハッシュマップにyをkeyとして現在のcurを保存します。すなわち、M_y \leftarrow curとします。

  • LOAD z
    ハッシュマップに保存した位置となるようにcurを更新します。すなわち、cur\leftarrow M_zとします。なお、保存されていない場合は、cur\leftarrow 0としておけば良いです。

これで各クエリはO(1)で処理できます。

Submission #35754741 - Panasonic Programming Contest 2022(AtCoder Beginner Contest 273)

↓永続スタックの解答
Submission #35797075 - Panasonic Programming Contest 2022(AtCoder Beginner Contest 273)

AtCoder Beginner Contest 270 参加記録

ABC ゲーム

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

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

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となるまでシミュレーションすればよいです。
長くなりましたが、要点をまとめるとこのような流れになります。

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

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

AtCoder Beginner Contest 267 F - Exactly K Steps

ABC 木 全方位木DP Link-Cut Tree

最遠点を求めた後にLink-Cut TreeでK回移動する解法で解いてみました。

ここでは、Link-Cut Treeの詳細な説明は割愛し、必要な部分だけを記載します。

詳細は以下のサイトを見るのが良いと思います。

Link-Cut Treeの実装メモ - 日々ｄｒｄｒする人のメモ

Link-Cut 木 - ei1333の日記

Link-Cut木では、以下のような操作ができます。

  • evert(v):頂点vを根にする
  • expose(v):根から頂点vまでのパスをHeavy-edgeで繋ぐ(パス上の頂点から出るその他の辺は全てLight-edgeになる)

頂点sを根とし、頂点tまでのパスをHeavy-edgeで繋ぐと、s-t間に含まれる全ての頂点が同一の平衡二分探索木によって管理されます。

この平衡二分探索木の頂点を通りがけ(in-order)順に並べるとs-t間のパス順になるようになっています。

続いて、平衡二分探索木を通りがけ順に並べた時のk番目の頂点を高速に得る方法を考えます。

まず、平衡二分探索木に部分木のサイズを持たせます。すると、通りがけ順でX番目となる頂点が、今いる頂点vの左部分木か、右部分木か、v自身かというのが、以下の場合分けで判定できます。 なお、1-indexedで並べるものとします。

S=頂点vの左部分木のサイズ+1
とします。+1は頂点vの分です。

  • X = Sの場合
    通りがけ順では、左部分木を全て並べた後、頂点vを並べます。
    左部分木のX-1の頂点を並べた後に、X番目としてvを並べるので、このケースではvを返せば良いです。

  • X \lt Sの場合
    左部分木にX番目が存在するので、vの左の子のX番目を調べます。

  • X \gt Sの場合
    右部分木にX番目が存在するので、vの右の子について、S個の頂点を除いたX-S番目を調べます。

このように根から順に二分探索のような感じで調べていくことでX番目の頂点を得ることが可能です。

計算量は、平衡二分探索木の高さ分の探索をするので、平衡二分探索木であることを考えると、ならしlog時間くらいになると思われます。

以上から、元の問題を以下のように解くことができます。

  1. 頂点iからの最遠点V_iを、すべての頂点について求める
  2. 各クエリで与えられるの頂点U_iをLink-Cut Treeの根とし、最遠点V_{U_i}を根と繋ぐ
  3. U_iからV_{U_i}までのパス上におけるK_i番目の頂点をLink-Cut Treeの平衡二分探索木から求める

計算量を考えます。
最遠点は、全方位木DPにより求めたので、O(N)です。
Link-Cut Treeで行う各処理は、O(logN)で処理できると思うので、O(QlogN)です(おそらく)。
よって、全体でO(N+QlogN)だと思います。

提出コード:Submission #34979495 - NEC Programming Contest 2022 (AtCoder Beginner Contest 267)

Link-Cut Treeにはモノイドを乗せるようにしてあるので、構造体等が定義されていますが、この問題を解くにあたっては不要です。