🤪

ABC_305_E "Art Gallery on Graph" をheapなしのrubyで解く

2023/06/15に公開

Ruby

競技プログラミング

AtCoder

tech

何だってrubyはそうheapに対して根性がねえんだ！
今回の問題はこちら

模範解答

公式解説は逆ダイクストラとも言うべき方針です。
一般的なダイクストラはheapにノードとそのノードに行くのに必要なコストを放り込み、最低コストで行けるノードを取り出してノード到着までの最低コストを確定、その確定済みノードから次に行けるノードをheapに放り込むという方式です。
今回の問題の公式解説はheapにノードとそのノードに到着した警備員の残り体力を入れておき、最も体力を残している警備員のいるノードを取り出す...というやり方です。

これがpythonなら問題ないでしょう。しかしここで立ち塞がる事実があります。rubyにはheapがありません。
自力でフルスクラッチするにしろ、aclから持ってくるにしろrubyそのものの重さのせいでTLEスレスレになってしまいます。

NGのBFS

atcoderの最短経路問題で使うのは大体BFS、ダイクストラ、ワーシャルフロイドのどれかです。ベルマンフォードって出題されたことあるんでしょうか？誰か教えてください。
ワーシャルフロイドの場合は露骨に頂点も辺も少ないはずです。今回の問題ではどう考えても使用不可。ダイクストラという翼を奪われた我々rubyistにはbfsしか武器がありません。
だからと言って変なBFSの使い方をするとハネられます。2つほど例示しましょう。

警備員の人数分だけBFS

警備員のスタート座標を起点に、1人ずつBFSしていく方針です。本番では通ったという噂がありますが、一直線上に並んだ2万のnodeに体力2万の警備員が2万人いて端から端まで巡回した場合にTLEします。

架空の警備室を置いてBFS

スタート地点が複数ある場合、架空のスーパースタート地点を一箇所作ってそこから実際のスタート地点に行く道があると考えるテクニックがあります。
最近有ったのがこの問題で、複数の発電所をスーパー発電所から電気を受け取っていると考えることで計算量を節約しています(そんな事しなくても解けたみたいですが）。
今回の問題もスーパー警備室を置いておくとちょっとだけ楽ですが、問題は発電所と違い距離の概念がある事です。体力5の警備員が2万人いるだけなら、スーパー警備室に体力6の警備員を1人入れてそこから辺を2万本引けば済む話。しかし体力1と体力2万の警備員がいた場合、スーパー警備室には体力2万1の警備員を置くしかありません。そこから実際のスタート地点に到着するまでに体力を減らすため架空のnodeを2万個置く必要があります。これで体力1の警備員が19999人いた場合、架空のnodeを約4億個置く必要があります。TLEしますね。

ヒント

この問題に限らず競プロは計算量との格闘です。つまりどのパターンならもう計算を打ち切っていいのかを考える競技です。
体力1万の警備員の隣のnodeに体力100の警備員がいる場合、体力100の警備員は無視してOKです。隣にいる体力1万の警備員が行けないnodeに体力100の警備員が行けるわけがありません。
じゃあ体力1万の隣に体力1万がいたらどうか。これはちょっとややこしいですが「そっちの道に行くことは考えなくていい」という事になります。せっかく体力1万あっても一歩動いたら体力9999、それなら最初からそこにいた体力1万の警備員に任せればいいので。

正解のBFS「キューを複数用意しておく」

教科書上のbfsではキューは一本ですが、atcoderでは「何歩進んだか」を記録するためにキューを2次元配列にする事があります。
上段のキューから現在地点を取り出す→visitedに記録→次のノードを一段下のキューにpushする、という奴です。
今回はこれの逆で、二次元配列の行インデックス＝体力と考えてキューを作成後、下段のキューから現在位置を取り出す→visitedに記録→次のノードを一段上のキュー(体力マイナス1)にpushする→体力0まで進んだ現在地全て | そこまでの経路でvisited判定されたnode全ての集合が答えです。
こうすれば1万あった体力が100まで減る頃には隣のnodeにはとっくにvisitedフラグが立っており、「隣にいた体力100警備員」は最初から無視できます。
また、「体力9999まで減らしてnodeに辿り着いてみたら、すでにそこは体力1万残した警備員が踏んでいた」という場合も計算を打ちきれます。

疑似コード

二次元配列のキューを用意する。
placeとhit_pointを受け取ったらキューのhit_point行目にplaceをpushする
キューの最下行placesをpopし、placesからループで一つずつplaceを取りだす。
placeが未訪問だった場合はvisitedフラグを立て、placeに繋がってるadjustedを1行上(3で最下行をpopしているので現在の最下行)にpushする。
残体力0まで行ったら終了。visitedとplacesの和集合を取って表示。

ACコード

疑似コード1は普通にqueueを作っている部分です。
擬似コード2は30行目です。なぜhit_pointをkで受け取っているんだこいつは。
擬似コード3は42から44行目。擬似コード4は48行目です。もうvisited作るのが面倒になっていきなりanswerに入れちゃってますね
擬似コード5は51行目以降です。

逆にrubyにあってpythonにないのが最小公倍数だそうな。