コンテスト中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を解きます。普通の巡回セールスマン問題と異なる部分は、以下のとおりです。

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

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

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

これからの説明では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）

geam1113’s diary

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

AtCoder Beginner Contest 274 メモ