AtCoder Beginner Contest 274 メモ
コンテスト中AC:A〜D
コンテスト後AC:E,F (いずれも自力)
D - Robot Arm 2
過去問に類題があります。
過去問のリンク (ネタバレ注意)
は、
としてありうる座標は、
としてありうる座標は、
としてありうる座標は、
ここまでで、であるについて、以下の法則が考えられます。
- が奇数なら点を配置できる座標のみが変化し、偶数なら座標のみが変化する。
- 配置可能な座標の集合を、座標の集合をとすると、とから得られる全ての組が示す座標に点を配置できる。
これが一般ので成り立つことは帰納法などによって証明できそうですが、ここでは省略します。2番目の法則はからの変化を図に書いてみるとわかりやすいです。
2番目の法則から、配置可能な座標について、座標を独立に考えれば良いことがわかります。
では、配置可能な座標をどう計算していくかですが、これは部分和DPの応用で解決できます。
すなわち、について座標のに配置可能であればとなるような配列を用意し、これを更新していきます。1番目の法則から偶奇に合わせて更新する座標を変更します。
実装のポイントとして、負の座標は配列に直接保存できないので、定数を加算して平行移動し、全て非負の座標となるようにします。
今回の場合、座標は大雑把に見積もっても〜の範囲内です。そこで、配列にの2倍+αの領域を確保し、原点がとなるように座標にを加算すると良いです。
DPテーブルの更新時に配列外参照をしないようにするチェックを忘れてWAを量産していました。
Submission #35893208 - キーエンスプログラミングコンテスト2022(AtCoder Beginner Contest 274)
E - Booster
巡回セールスマン問題の応用問題です。巡回セールスマン問題はbitDPで解くことができますが、ネットで調べると出てくるので、ここでは詳細は割愛します。
今回は、頂点であるとみなして、bitDPを解きます。普通の巡回セールスマン問題と異なる部分は、以下のとおりです。
- 宝箱に訪れた個数によって、移動速度が異なる
- 宝箱には行かなくてもよい
- 原点から出発し、原点に戻る
それぞれの自分の解決策を示します。
宝箱に訪れた個数によって、移動速度が異なる
これからの説明では0-indexedとします。
まず、DPテーブルは以下のようになります。
訪問状態を示す冪集合の状態で頂点に居る時の移動時間の最小値
なら、ビット目を街に、ビット目を宝箱に割り当てます。
例を示すと、街と宝箱に訪問済みなら、その状態を表すビット列は、11001
です。
これからの説明でDPテーブルの行のインデックスはビット列とします。
DPテーブルの更新の際に、宝箱に対応するビットの1の個数をカウントし、頂点間の距離を個数+1で割れば良いです。
例えば、上の例で頂点の座標がそれぞれであり、訪問状態を表すビット列が11001
の状態で、頂点からに移動する場合、
と更新します。
宝箱には行かなくてもよい
例えば、先程の例と同じ場合、街に対応するビット目がなら、宝箱に対応するビット目はなんでもよいです。
従って、??111
となるような全ての状態に対して、原点に戻るまでの最短時間を調べれば良いです。
原点を出発し、原点に戻る
原点を出発する代わりに、初期値として各頂点のみが訪問済みの状態に、原点からの移動時間を設定すれば良いです。
例えば、で、街の座標がなら、
という感じで設定します。これを各頂点について設定します。
原点に戻るのは、各状態の最小の移動時間を求めた後、原点への移動時間を考慮すれば良いです。
例えば、上の例と同じ条件で考えると、はすべての街(+宝箱1)を訪れ、最後に街にいる時の最小移動時間です。
しかし、このままこの状態の最小移動時間にするのではなく、を、この状態における最終的な最小移動時間とします。
なお、原点を頂点として追加した実装だとTLEになりました。
https://atcoder.jp/contests/abc274/submissions/35914594
F - Fishing
最適解で得られた魚を座標の昇順に並べたものをとします。
これらの魚を捕獲する際、始点となる実数をとして差し支えありません。
これより、魚を始点として捕獲した場合の通り調べれば良さそうだとわかります。
ただし、前提として、各魚を始点として捕獲する場合の最適解が求められる必要があります。
最適解の求め方を示します。
魚を始点として魚捕獲する場合、魚が時間からまで捕獲可能であるという閉区間が、例外を除いて存在します。
そのため、以下の問題を解ければよいです。
正方向に伸びる数直線上に複数の区間と、区間に対応するスコアが与えられる。座標を1つ選ぶと、その座標を含む区間のスコアが得られる。スコアを最大化せよ。
これはいもす法によって解けます。
充分に小さい時間をとします。区間とその区間で得られるスコアが与えられた場合に配列にとという組を追加します。
全ての区間について追加し終えた後、組の第一要素をキーとして昇順にソートします。その後、第二要素の累積和を計算します。
累積和を計算した時に最大となった値が得られる最大のスコアであり、これが最適解です。
このいもす法の計算量はソート部分がボトルネックとなってです。各魚についてこれを計算するので、計算量はとなり間に合います。
区間の求め方ですが、魚と魚の最初の座標と速度の関係で場合分けが必要です。また、区間そのものが存在しない場合もあります。
始点については、
- なら、
- 魚が魚に追いつくなら、を解いて、
- 魚が魚に追いつくなら、を解いて、
終点については、
- でかつなら、は存在しないことにするか、とする
- 魚が魚を引き離すなら、を解いて、
- 魚が魚を引き離すなら、を解いて、
という感じで場合分けします。
Submission #35965103 - キーエンスプログラミングコンテスト2022(AtCoder Beginner Contest 274)