脳log[20220129] JOIG 2021/2022 本選 過去問／F 問題 タクシー 2 (Taxis 2)

最終更新: 2023-07-22T23:29+0900

♪ [AtCoder] JOIG 2021/2022 本選 過去問／F 問題 タクシー 2 (Taxis 2)

 ステップ１

• タクシーが赤色の場合，乗車後の所持金が a−1 円になる．
• タクシーが青色の場合，乗車後の所持金が「a÷2 を整数に切り捨てた値」円になる．

町 1 から出発し，1 円以上の所持金を残した状態で町 Tj​ に到着するために，最初に少なくとも何円の所持金を持っている必要があるか

問題のこの部分は、まあ、逆に考えます。所持金が１の状態でスタートして、所持金が +1 になる、×2 になる、というように。そうすれば初期金額を探索しなくて良い。ただしそれぞれの町をスタート地点に設定して町１への最短経路を繰り返し求めるということは許されていないので、スタート地点は町１のままにしておきたい。

ところが町１を１円でスタートして、+1/×2 しながら各町に着いたときいくらになっているかをダイクストラ法で求めてもサンプルが合わない。合わなかった。

たぶん、-1/÷2 の逆計算は +1/×2 でいいのだけど、((((-1)-1)÷2)-1)÷2 の逆計算は ((((×2)+1)×2)+1)+1 ではないとか、合ってるけどその通りに計算できていないとか、そういう理由。

わからんなりにテキトーに 2×2 の正方行列に 2 とか 1 とか 0 を割り当てて実際に計算してみれば、必要な係数が２つだということと、それをどう変化させればいいのかがわかった。スクリプトの中の x,y = x,x+y と x,y = x+x,y というのがタクシーごとの変化。式を見ても意味はわからない。

 ステップ２

逆計算がわかったからダイクストラ法で解けたかというと、小課題の４あたりから答えが稀にあわなかったり時間をオーバーしたりする。した。小課題の３までは問題のグラフが木だから複数の経路の競合がなかったのだな。

これはたぶん、ある町における状態というのが所持金というパラメータ１つで優先順位を付けられないせいだと思う。さっき x と y の式を２つ書いたけど、そして所持金というのが d = x+y で表されるのだけど、ある町からある町へ移動するにあたりどちらのタクシーを使っても所持金の変化は x+x+y == d+x で共通している。だけどその次の移動での増加量が x の値にのみ依存するので、x を増加させることで所持金を変化させたタクシーの方が分が悪い。

 ステップ３

２つのタクシーの運賃を普通の経済感覚で比べてみると、どの場合でも所持金が１円減るだけの赤色のタクシーを利用できるときは利用して損をすることがないことがわかる。たぶん。01BFS みたいなステップを踏めば解けるような気がするなー。

 提出 #28854159 (AC / 1242 Byte / 2410 ms)

頭の中が整理されていないので無駄がまだあると思う(嘘解法の可能性も大いにある)。でも１秒しかなかった JOIG-2021-F「デジタルアート (Digital Art)」(20211210p01) と違って制限時間が４秒もあったので間に合った。嬉しい。

D 問題まではやるだけだったけど、E 問題「エゴイ展 (EGOI Exhibition)」がまだ解けていない。価値の正負と絵の種類で場合分けとクラス分けをして DP をしようとしたんだけど……。

PQ#dn_heap がバグってるね。不等号の向きが逆。これは要するに、PQ には繰り返す幅優先探索の無駄を気休め程度に取り除く意味しかなく、実際にはその効果さえなかったということ。

 提出 #28975251 (AC / 502 Byte / 1158 ms) ← 2410 ms

PQ#dn_heap のバグをとったとしても定数倍が重いせいで、初期パラメータが異なる複数の地点をスタート地点に設定した幅優先探索のようなものを、距離の更新がなくなるまでぐるぐる回した方が速い。優先度付きキューを使うと確かに最短距離を複数回更新するという無駄はないのだけど。

Array をキューにするのと Hash をキューにするのでは Hash の定数倍が重い。キュー内で要素が重複することを気にせず Array につっこんだ方が速かったりする。

そんな(良くない)理由でメインループ内の前半のループのキューは PQ でも(後半のループのように) Hash でもなく Array になっている。

 提出 #28988344 (AC / 600 Byte / 863 ms) ← 1158 ms

キューを２本持つことでプライオリティキューを使わないでもソート済みの状態を保ちながらキューを伸ばせる場合があるというのは、AtCoder について書いた２番目の日記に書いてある>20190916p01.01。今回もこれが使える。

863 ms というのは Ruby に限らない AC の中で１ページ目に入っているのだ(全部で９ページではあるのだけど)。