geam1113’s diary

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

AtCoder Beginner Contest 274 メモ

コンテスト中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座標の集合をXy座標の集合をYとすると、XYから得られる全ての組が示す座標に点を配置できる。

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

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

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

実装のポイントとして、負の座標は配列に直接保存できないので、定数を加算して平行移動し、全て非負の座標となるようにします。
今回の場合、座標は大雑把に見積もっても-10^410^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とします。
これらの魚を捕獲する際、始点となる実数xx=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)