HTTF2019本選:モンスターテイマー

オープン4位だったので記念に投稿。本選の人と合わせると14位かな？
(12/03:4億点が出たので追記しました)

問題

A - モンスターテイマー

　モンスターの高橋君(?)を育てながら，野良モンスターを討伐し，所持金を増やすという問題。

f:id:sigma1113:20181201233818p:plain:w300
初期状態の高橋君

正の得点を得る

　この問題では，正の得点を得るのは容易だ。高橋君も討伐依頼も無視し，ひたすらアルバイトする。
Submission #3692024 - HACK TO THE FUTURE 2019 本選オープン

レベル上げは重い...?

　問題文をぱっと見ると，レベル上げのコストがかなり重そうに見えた。そこでとりあえず，討伐依頼のうち，必要なスキルレベルの最大値が1であるもののみを相手にすることにしてみる。最初はすべてのスキルのレベルを1にすることを目指し，その後はひたすら討伐する。テストケースの作り方より，相手にする討伐依頼は30000\times 0.1=3000個くらいだろう。
　提出してみると14509点で思ったより良かった。
Submission #3692352 - HACK TO THE FUTURE 2019 本選オープン

それでもレベルは上げたほうがいい

　この時点ですでに2億点に乗せている人がいたため，何かを勘違いしているのだろうと察する。どうやら，レベルは上げてしまった方がいいらしい。簡単に見積もってみる。すべてのスキルのレベルを10にするのに必要な金額は
10\sum_{k=1}^{10}k\cdot 2^k = 1.8434\times 10^9
やはり重いように見えるが，ここですべてのスキルを上げたときに，討伐によってどれくらいの報酬が見込めるかを考えてみる。それは，テストケースの作り方から見積もれる。まず，1000ターンにたいして依頼は30000個あるから，各ターンに30個はそのターンが締め切り日であるような依頼があると考えてよい。また，30個もあれば，1つくらいは必要スキルの総和が50くらいのものがあることを期待することにする(そんなに変な期待ではないはず...)(レベルmaxなので，各ターンで報酬が最大のものを取るのが基本になることに注意，もちろん実際に見るのはC_iの値だが)。さらに，スキルボーナスも必ず獲得できる。そうすると，討伐によって見込める利益は
(1.3^{50}\times 1000) \times 10 \times 10 \approx 4.9\times 10^{10}
であり，たった1回の討伐で元が取れそうとわかる。(ちなみに実際に平均を取ってみると3.0\times 10^9くらいでした，すいません。一応元は取れていますが。)
要は，

  • 前半はできるだけ早くすべてのスキルをmaxにする
  • 後半は討伐内容をうまく選んで，報酬を最大化する

という問題にしてしまった方が，後半でがっぽり稼げるので最終的にもスコアが高くなるのである(基本はそうというだけで、実際は後述するようにレベルを上げながら何をするかということも重要になってくる)。すぐには確信できない部分はあったが，時間はあるので物は試しという気持ちでとりあえず実装する。もう少し詳しく書くと

  • 討伐依頼のリストは締め切り時刻ごとに管理する。
  • トレーニングするお金がないとき:その時点で報酬が最も高い討伐をするか，アルバイト
  • トレーニングするお金があるとき:トレーニングする。すべてのスキルをレベル1に→すべてのスキルをレベル2に→...→すべてのスキルをレベル10に となるようにトレーニングする。スキル1から順番にレベルを上げる。
  • すべてのスキルレベルが10になったら，そこからは各ターンで最も高い報酬の得られる討伐を行う。

これを実装して提出するとなんと2.9億点！ナイーブな発想だが，これがちゃんとできるかが一つの山だったようである。
Submission #3693049 - HACK TO THE FUTURE 2019 本選オープン

f:id:sigma1113:20181202160326p:plain:w300
レベル10の高橋君

地道な工夫

　ここからはろくなことができなかったので，実際にやった地道な工夫を紹介。

  • レベル上げの途中にも，おいしい討伐依頼が転がっている可能性がある。そのため，報酬がある閾値sを超えるような討伐依頼は受けるということをする。計算時間が余っていたので，このsは適当そうな範囲を探索した。
  • レベル上げが終わってからは，受ける討伐依頼を前から決めるより，後ろから決めた方がスコアがよかったのでそうした。この貪欲も厳密ではない(短期間の依頼は報酬の落ち方が激しいため，その分損をする可能性がある)。
  • 全く本質的ではないが，スキル上げの順番を2通り(だけ)試していい方を選んだら少し上がった。

というわけで，最終結果となった提出がこれだった。
Submission #3694390 - HACK TO THE FUTURE 2019 本選オープン

反省と感想

  • レベル上げの順番を焼きなましやら山登りやらするといいらしい。試してみていい結果がでたら加筆します。
  • レベル上げの途中にどの討伐依頼を受けるかというところでも工夫の余地がある。
  • 後ろから貪欲に加えて1つ前のターンとの差分を考えるとうまくいくらしい。
  • 楽しかった。来年は新卒枠なので賞金を狙えるくらいになりたい...。

追記(12/03):山を登る

　山登り法を試したところ効果があったので，その詳細を述べる。
レベル上げの順番を最適化することを考える。レベル上げの順番は，1から10のスキルの番号を10個ずつ持つ大きさ100の配列pで管理する。例えば，配列の\{\dots,1,3,10,1,\dots\}という部分は，「スキル1のレベルを1上げる→スキル3のレベルを1上げる→スキル10のレベルを1上げる→スキル1のレベルを1上げる」ということを意味する。pの初期値をてきとーに設定し，そこから2つの要素をswapした配列に対し1000ターン分のスコアを計算し，良くなれば採用，ということを制限時間いっぱいまで繰り返す。
　山登り法では，できるだけシミュレーション回数を増やしたいため，サボれるところはサボることを考える。レベル上げ終了後は，レベルをどういう順番で上げたかということに依存せずに行動を決定できる。今回は，レベル上げ終了後は「ターンの遅い順に討伐する依頼を決定する」という方針を引継ぐことにする。山登りを始める前に，tターンからレベル上げ後の行動に移るときの報酬の総和と行動を事前に求めておけば，だいたい350\sim 400ターン分くらいはサボれることになる。
　ここまでやったのが以下。3.3億点で，やはり「レベル上げの間でも取るべき報酬は取る」ということが必要そうだ(とはいっても，レベル上げの順番を考えないよりははるかに高いスコアだ)。
Submission #3707961 - HACK TO THE FUTURE 2019 本選オープン

　では，レベル上げの間に取るべき報酬をどう決めるかということを考える。なぜわざわざレベル上げの途中に報酬を貰いに行くかというと，その報酬がレベル上げ後に取る報酬といい勝負だからであろう。よって，レベル上げ後に取る報酬を用いてこの基準を定める。具体的にどう決めるかはいろいろあるが，
0.55\times「(今からストレートでレベル上げが終わるターン+10ターン)後に得る報酬」
以上の報酬であれば，取りに行くことにした。0.55や「10ターン」という謎の数字はエスパーで決めた。
　これを提出すると，運が少し良いと4億に乗る(だめでも3.8億はある)。安定してより高いスコアを出すにはさらなる工夫が必要そう...。
Submission #3708880 - HACK TO THE FUTURE 2019 本選オープン

追記(12/07):焼きなまし法を試したら4.13億に到達。パラメータ調整が難しすぎる。今は温度を減らしていない(は？)のでまだいけるかも？
Submission #3730828 - HACK TO THE FUTURE 2019 本選オープン

おまけ

ビジュアライザでは4種類の高橋君が登場するらしいのでコンプした。うち2種類は上に挙げたので省略。

分岐1

f:id:sigma1113:20181202200935p:plain:w300
かわいい
f:id:sigma1113:20181202201203p:plain:w300
かわいい
f:id:sigma1113:20181202201300p:plain:w300
空気変わったよ...
f:id:sigma1113:20181202201334p:plain:w300
子供の恐竜感
f:id:sigma1113:20181202201410p:plain:w300
BLUE DRAGONと聞いて何を連想する...?
f:id:sigma1113:20181202201607p:plain:w300
ドラゴンボールのあれみたい

分岐2

f:id:sigma1113:20181202201511p:plain:w300
森にいそう
f:id:sigma1113:20181202201626p:plain:w300
飼いたい
f:id:sigma1113:20181202201650p:plain:w300
倒すと宝石が貰えそう
f:id:sigma1113:20181202201720p:plain:w300
ゲームの中盤くらいからモブで出てきそう
f:id:sigma1113:20181202201837p:plain:w300
こっちは緑系ですね
f:id:sigma1113:20181202202022p:plain:w300
GREEN DRAGONでした

第5回ドワンゴからの挑戦状-C:k-DMC

終了46秒前に通ってアツかった。

問題

C - k-DMC

解法

dpがちらついたが，順番に並んでいる3つ組を数えるときは，中央を固定するのが定石なので，とりあえずそれに従って考えてみる。ここで，もしc-a\lt kという条件がなければ，これは単にSに現れる「DMCという部分列の数」を数えるだけである。つまり，'D','M','C'の出現数について累積和を取っておき，各'M'について「その'M'より左にある'D'の数」と「その'M'より右にある'C'の数」の積を取ればよい。
さらに，「c-a\geqq kをみたすDMCという部分列の数」がわかれば，これを「DMCという部分列の数」から引くことで答えが求まる。ここが1つのポイントだろう。

それでは，「c-a\geqq kをみたすDMCという部分列の数」を求めよう。'D'の位置をa，'M'の位置をb，'C'の位置をcとする。DMCという部分列であって，この条件を満たすとき，a,b,cの関係として考えられるものは

  1. b\lt a+k かつ a+k \leqq c ('C'だけ遠い)
  2. a+k \leqq b \lt c ('M'も'C'も遠い)

の2つであり，これらは排反である。1の方は，区間[a+1,a+k)にある'M'の数と，[a+k,N]にある'C'の数が求まればよいから，'M'と'C'の累積和を使えばO(1)で求まる(詳細は提出参照)。2の方は，「位置iより右にあるMCという部分列の数」を事前に求めておけばO(1)で求まる(これも累積和，提出参照)。よって，各kの値に対してO(N)で答えが求まるので，全体としてO(QN)であり，十分高速である。

提出

Submission #3660113 - Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選

  • コンテスト後に少し整理したものを貼った。
  • a+kがNを超える場合の処理に注意。
  • Bでひどいミスをしたのだがこれが解けたおかげで耐えた。
  • c-a\lt kという条件は，c-a\geqq kという形にした方が扱いやすい印象があった。C - 徒歩圏内を思い出して解いていた。
  • 公式解説見たら尺取りだった。

HTTF2019予選:ばらばらロボット

はじめてのマラソン参加記。
結果は60位と，なんとも言えない成績だが，2桁順位とれるかどうかが実力相応かなと思っていたので，善戦したと思う。上位の方々も何人か記事を上げているので，これがどの程度参考になるものとなるかわからないが，記念に残しておこうと思う。

問題

A - ばらばらロボット
マラソンは問題を理解するのも一苦労だ。要求も難しく，問題文を読み切ったときはどうしたものかと思っていた。

正の点数を得る

最初にやるべきことは「正の点数を得る」(有効な提出をする)ことだと思う。これは本当に何も考えずに書いたプログラムを提出する。今回の場合は，周りは壁マス，その他は空白マスにするというものだろう。これは競プロやってますという人なら書けるレベルである。開始5分で提出した。
Submission #3572613 - HACK TO THE FUTURE 2019予選
これで80940点。これは1つの基準になる。何か工夫をしたプログラムを提出して，この点数より悪くなったら，よっぽど変なことをしている(もしくはバグ)ということである。
このときの様子をビジュアライザで見てみる。
f:id:sigma1113:20181111125650p:plain
これを見たときは意外と青が多いなと思ったのだが，緑や黄色も多いのでスコアは伸びない。
正の点数を得たので，どうやって得点を伸ばすか考える。

苦悶

ここから2時間は全くまともなことができなかった。いい感じの盤面を構成しようにも全然うまくいかない，ということを繰り返していた。
1つだけ考えたものを公開すると，周辺を2倍マス(D)で埋めるというもの。端に溜まりがちかと思ったので，端に来たら帰りやすくするようにしたかった。
f:id:sigma1113:20181111130204p:plain
Submission #3573461 - HACK TO THE FUTURE 2019予選

結果は微増。逆に端が疎になりすぎてしまった。

山登り法

2時間経ってから，マラソンの定番である山登り法を試していないことに気付く。これはあかん。
山登り法とは，端的には以下のような方法である。

  1. 適当な初期状態を定める。
  2. 現在の状態から，「少しだけ」変わった状態を作る。その状態の得点を実際に計算する。
  3. その得点が現在の状態より良かった場合は，「少しだけ」変わった状態に遷移する。2に戻って繰り返す。

要は，今いるところより高い方に進んでいくという気持ちそのままである。この「高いところを探す→更新」という流れを制限時間いっぱいまで繰り返す。局所解に陥る可能性はあるが，それはもう仕方ない。(焼きなまし法はこの局所解に陥るという可能性を減らす方法であるが，実装できないので(おい)使わなかった。)
この問題における「少しだけ」変わった状態とは，あるマスの種類を別の種類に置き換えるというものであろう。よって，以下のようにして山登りを行った。

  1. 初期盤面を「周りは壁，その他は空白マス」と定める。
  2. 現在の盤面からあるマスを乱択で選び，別の種類のマスに置き換えてみる(これも乱択)。その後，実際にコマンドに従ってN体のロボットを動かし，得点を計算する。
  3. その得点が現在の盤面より良かった場合は，マスの変更を採用する。2に戻って繰り返す。

やっていることは難しくないが，ロボットの動きをシミュレーションするなど，それなりの実装力が要求される。コンテストの時間は8時間もあるのだから，じっくり実装できる。多少バグらせたが，1時間程度で実装できた。結果はこちら。
f:id:sigma1113:20181111131707p:plain
青マスがだいぶ増えている。スコアも劇的に伸びた。これを提出すると113776点。やる気が出てきた。
Submission #3575341 - HACK TO THE FUTURE 2019予選

シミュレーション高速化(差分更新)

愚直な山登り法がとりあえず動いたので，この方向性でスコアを伸ばすことを考える。当たり前だが，山登り法は「高いところを探す→更新」というループの回数をできるだけ多くした方がよい。制限時間があるので，シミュレーションを早くすることでこの回数を増やすことを考える。上のプログラムのループ回数をAtCoderのコードテストで見たところ，1777回であった。
上のプログラムでは，あるマスを変えたときにすべてのロボットを動かしなおしているので，計算時間がO(NL)かかる。ところが，あるマスを変えたときに，動きが変わるようなロボットというのはそこまで多くないはずである。よって，各ロボットについて，現在の盤面のときにどのマスでコマンドを実行するかということを記録しておく。すると，あるマスを変えたときに影響を受けるロボットがわかるので，そのようなロボットについてのみ操作をやり直す。これも実装力が要求されるが，時間があるので頑張る。これもかなりバグったが，なんとか実装しきる。結果はこちら。
f:id:sigma1113:20181111132736p:plain
さらに良くなったことがわかる。ループ回数は8232回だった。実装がよければもっと伸びると思う。提出すると得点は120148になった。順位表を眺めていて12万点は乗せたいと思っていたのでよかった。

さらなる工夫

ここからは問題固有の考察が必要になる(と言っても，ここからはあまり伸ばせなかった)。よく考えると，壁マスを置いてしまうと，ロボットの到達できるマスが減ってしまうため，ばらばらにしたいという問題の要求に逆行している。よって，壁マスは使わないことにする。あとは，角のあたりに2倍マスや3倍マスを置いてから山登りするとなぜかスコアが伸びたので，そうしたものを提出した。一応，角に集まり過ぎないようにするという作戦は微量だが効果を発揮したらしい。
f:id:sigma1113:20181111133630p:plain
Submission #3579046 - HACK TO THE FUTURE 2019予選
122547点。これが最終得点となった。この後，「コマンド列のどの時点どのマスにいるか」を記録して操作を最初からやり直さなくていいようにしようとしたのだが，バグが取れず間に合わなかった。

終了後

終了後に得た知見を少し紹介。

LとRだけ使う

自分はDとTだけ使うということをしていたのだが，シミュレーションの高速化上都合が悪い。無駄な動きが増えてしまうからである。これは気づきたかった。

初期盤面をLで埋める

これに気付いた人はすごい。すべてのロボットを左向きに回転させてから山登りするとうまく散るということらしい。
とりあえずこの2つの工夫はすぐに試せるのでやってみた。
f:id:sigma1113:20181111134442p:plain
Submission #3581258 - HACK TO THE FUTURE 2019予選
125545点に。ここまでやれば30位台に入れたが，気づかなかったので仕方ない。

コマンド列の圧縮

例えば，LRというのは何もしないというのと同じだし，SSSというのは3マス前に進むというのと同じである。こういう圧縮をすべてのロボットのコマンド列に適用する。これだけでコマンド列はかなり短くなるはずで(悪くても1/2くらいにはなるはず)，高速化にかなり効いている。

感想

実は1週間前からマラソンの勉強を少しだけしていて，その成果が出て12万に乗せられたのはよかったと思う。その先は問題固有の考察が必要で，これはアルゴリズム同様に鍛えていかなければいけないところだと感じた。焼きなましやらビームサーチやら習得すべき技術はあるが，結局問題の性質を掴めるかの方が大切そうと感じた。
終わってみれば8時間はあっという間で，非常に充実した時間を過ごすことができた。chokudaiさんとtsukammoさんに感謝します。
本戦オープンコンテストの日はバイトを入れようと思っていたが，オープンコンテストに真面目に参加しようと思う。

追記(11/13)

20卒だったら本戦オープン行けてたらしい。残念！

ABC113-D:Number of Amidakuji

フィボナッチ数列が登場しがち。

問題

D - Number of Amidakuji

解法

こういうのはdpが有効である。dp_{i,j}を位置iまででjに行くようなあみだくじの数とおく。dp_{i,j}の遷移先はdp_{i+1,j},dp_{i+1,j+1},dp_{i+1.j-1}のいずれかである。あとはそれぞれの遷移先について，そこに遷移するような位置(i+1)での横線の置き方の数がわかればよく，これはbit全探索することでO(2^W)でできる。本番でここが思いつかなかった。悲しいね。

ところで，次のような事実がある。

証明
Wに関する帰納法で示す。左から順に縦棒に1,2,\cdots W-2,W-1,Wと番号をつけることにしよう。W=0,1のときはそれぞれ1通りである。W-2,W-1での成立を仮定して，Wのときの横棒の置き方の数を求めよう。縦棒Wと縦棒W-1の間に横棒を置かないとき，横棒の置き方は1からW-1までの横棒の置き方に等しく，F_{W-1}通りある。縦棒Wと縦棒W-1の間に横棒を置くとき，横棒の置き方は1からW-2までの横棒の置き方に等しく(縦棒W-1と縦棒W-2の間には横棒が置けないから)，F_{W-2}通りある。よって，Wのときの横棒の置き方の数はF_{W-1}+F_{W-2}=F_W通りである。

すると，bit全探索などする必要がないことがわかる。例えば，dp_{i,j}からdp_{i+1,j-1}への遷移を考えよう。このような遷移が起きる条件は

  1. jとj-1の間に横棒がある
  2. j-1とj-2の間に横棒がない
  3. jとj-1の間に横棒がない

の3つである。これらの条件を満たすような位置i+1での横棒の置き方は，「縦棒1から縦棒j-2までの横棒の置き方」と「縦棒jから縦棒Wまでの横棒の置き方」の積であるから，F_{j-2}\times F_{W-j}通りある。つまり，遷移がO(1)で可能であることがわかる。他の遷移も同様にしてできる(コード参照)。天才だ。

提出

Submission #3543308 - AtCoder Beginner Contest 113

フィボナッチ数列が現れるのは面白いが，bit全探索で解けなかったのは情けなかった。

QUPC2018-E:Treeone

最近よく見るやつ。

問題概要

長さNの数列\{A_i\}が与えられる。その数列の連続する部分列であって，総和が0であるものの個数を数列のたぴさと呼ぶ。数列のうち1つの値を自由に変えられるとき，あり得るたぴさの最小値を求めよ。
E - Treeone

解法

「数列の連続する部分列であって，総和が0であるものの個数」と聞いたら，累積和\{S_i\}を考えるのが定石である。その個数は，S_i=S_jとなる(i,j) (i\leqq j)の組の個数に等しい。つまりは，ある条件を満たす区間の数である。このうち，A_kの値を一つだけ変えて，どれだけそういう区間を減らせるかということを考えよう。答えは

  • 「元の数列のたぴさ」から「A_kを変えることで減らせる区間の数の最大値」を引いたもの

である。「元の数列のたぴさ」の効率的な計算については，A - Zero-Sum Rangesがそのものなので参照していただきたい。
A_kの値をうまく変えることによって，i\leqq k \leqq jを満たす区間(i,j)については，条件を満たさないようにできる。例えば，A_kを5000兆とかにすれば，もともと和が0だった区間の和が5000兆くらいになる。また，A_kを5000兆に変えたことによって，和が0でなかったの区間の和が0になることもない。kを含む区間については5000兆という数字がでかすぎて和が0になりようがないし，kを含まない区間はA_kが5000兆になったところで何の影響もない。よって，各kについて，「i\leqq k \leqq jを満たす区間(i,j)であって，S_i=S_jなるものの個数」が効率的に求まればよい。
これにはimos法と呼ばれるものを使う(imos法を知らない方は調べてください)。各iについて，「iから始まる条件をみたす区間の数」足し算し，「iで終わる条件をみたす区間の数」を引き算する。その後，順に累積和を取っていけば，各kに対して，「kを含む条件をみたす区間の数」がわかる。また

  • 「iから始まる条件をみたす区間の数」は「i\leqq jであって，S_i=S_jをみたすものの個数」に等しい
  • 「iで終わる条件をみたす区間の数」は「j\leqq iであって，S_j=S_iをみたすものの個数」に等しい

よって，各S_iの値が全部でいくつあるかを調べておき，iが小さい順に上の計算をしてけばよい(詳細はコードを見た方がわかると思う)。実装上注意すべきは，単にS_i=0となるような場合(つまり，A_1+\cdots +A_i=0となる場合)を数えるために，S_0=0から計算を行うところである。

提出

https://beta.atcoder.jp/contests/qupc2018/submissions/3441083

  • S_iがどんな値かわからないため，mapを用いている
  • 「i\leqq jであって，S_i=S_jをみたすものの個数」や「j\leqq iであって，S_j=S_iをみたすものの個数」は適当に引き算すれば求まるので，直接調べる必要はない


方針はすぐだったが，変なところでバグらせて足を引っ張ってしまった。反省。

QUPC2018-D:Novelist

きれいに解けるので好き。

問題

D - Novelist

考察過程

王都から都市へ移動する依頼をタイプM，都市から王都へ移動する依頼をタイプLとする。
最初は各依頼を頂点として，ある依頼を終えた後，実行可能な依頼について有向辺を張って，最長パスを調べるということを考えていたのだが，これでは辺がO(ML)本あるためTLEする。考え直し。
よく考える。タイプMの依頼を終えた後，Treeone君はある都市nにいる。次には(可能なものが存在すれば)タイプLの依頼を選ぶことになるが，都市nから出発する依頼のうち，現在時刻より後で，最も出発日が早いものを選ぶのが最適になる。できるだけ早く王都に戻った方が，多くの依頼を達成できるかもしれないからである。つまり，あるタイプMの依頼をやると決めた後，タイプLの依頼を終えて王都に戻ってくる日が一意に定まる。
それならば，以下のようにすればよい。

  • タイプMの各依頼に対して，その依頼の開始日と，王都に帰ってくる日を両端とした区間を作る(ただし，王都に帰ってこれない場合は作らないでおく)。
  • これらの区間について，区間スケジューリング問題を解く。その解\times 2を答えに加算する。
  • 区間スケジューリング問題の最適解の終了日を記録しておく。このとき王都にいるので，タイプMの依頼のうち，まだ達成できるものがあれば答えに1を加算する。もう王都には戻ってこれないので，これでTreeone君の仕事は終わりである。

区間スケジューリング問題を知らない方は調べてください(すいません)。

提出

https://beta.atcoder.jp/contests/qupc2018/submissions/3438077

  • タイプLの依頼は，出発する都市ごとにvectorで管理した。
  • あるタイプMの依頼に対する最適なタイプLの依頼を探すのに二部探索をしている。
  • もうちょっときれいに書けそう。


今思えば，「できるだけ早く王都に戻った方が，多くの依頼を達成できるかもしれない」という考え方はまさに区間スケジューリング問題を示唆するものであった。良問だと思う。

QUPC2018-C:Ito Campus

慣れているとなんてことない問題だが，ちゃんと書いてみる。

問題:C - Ito Campus

解説

@から距離X以内のマスは安全でないなので，そのようなマスを調べて安全でないマークをつけてから，安全なマスだけでSからGへの最短距離を調べればよい。安全でないマスを調べるのも，SからGへの最短距離を調べるのも，幅優先探索(以下bfs)すればよいのだが，前者については注意が必要という問題である。
例えば，「@を見つけたら，そこからbfsで距離X以内のマスに安全でないマークをつける」ということをすると，毎回のbfsにO(X)かかり，@がいっぱいあると計算量がO(XHW)となり，TLEする。
では，「安全でないマークをつけたマスは壁'#'にしてしまう」というアイデアはどうか。これならば，同じマスを2度以上探索しないのでTLEは回避できる。しかし，これではWAを踏んでしまう。例えば，X=3として，以下のような状況を考えてみよう。外側の壁は省略してある。
f:id:sigma1113:20181020185553p:plain
ここで，(1,1)にある@から探索をすると，以下のようになる。
f:id:sigma1113:20181020185655p:plain
これで，(3,1)からあるマスを探索しようとしても，イノシシは壁を通れないので，ここで安全でないマスを調べるパートが終了する。そうすると，SからGまでは距離4で行けることになるのだが，実際はGは安全でないマスであるため，WAである。

そこで，次のようなbfsをする。最初に@であるようなマスと残りの距離(x,y,d)をqueueに入れてしまう。そこからは素直に安全でないマスを調べていくだけである。異なる点は最初だけだが，これでうまくいく。
うまくいくことを確認しよう。最初に@であるようなマスをqueueに入れておくと，以下のことが成り立つ。

  • すべての壁以外のマスに(x,y)ついて，(x,y,d)がqueueに入るとき，dは(x,y)について最適な値である。つまり，dは(x,y)から最も近い@から探索したときに得られる残りの距離である。

なぜなら，このbfsは「ある@からの距離が1のマスすべて」→「ある@からの距離が2のマスすべて」→...→「ある@からの距離がXのマスすべて」という順で探索が進むからである。また，どのマスも高々1回しか探索されないので，計算量もO(HW)で済む。

提出

https://beta.atcoder.jp/contests/qupc2018/submissions/3439882
実装上の変なところ(?)は以下。

  • 安全でないマスを調べる際には，queueに入れるときにマス(x,y)を2000\times x+yで管理している。y\leq 1000なので，2000で割ったときの商とあまりでマス(x,y)を復元できる。こんなことをした理由は，pair< int, pair< int,int> > と書きたくなかったからなのだが，いい方法あったら教えてください。
  • とか言いつつ，2回目のbfsではマス(x,y)をそのまま管理してる。何も他に情報がいらなければこう書くのが個人的には楽なためそうしている。


こういう探索の始点が複数あるbfsは割とよく見る。