/ 最近 .rdf 追記 編集 設定 本棚

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



2022年01月29日 (土)

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

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

 ステップ1

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

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

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

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

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

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

 ステップ2

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

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

 ステップ3

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

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

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

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

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

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