JOISC2014 - 漢字しりとり
解法
各クエリについて、パスは以下のいずれかに分類される。
コストのわかっている辺のみ使う
コストのわからない辺$ U_kを使う$ (0 \leq k \lt K)
$ K = 5とし、それぞれ$ -1, 0, \dots, 5とラベル付けする。
各クエリについてどのタイプか送ると$ 40点まで取れる。
この方針だと$ 80点は厳しそうなので別の方法を考えなければならない。
コストを全て送れるなら当然解けるが、bit 数制限に引っかかるので、なんとか「座圧して」送りたい。
コストのわかっている辺のみ使うときの最短距離を$ d(u, v)と定める。
辺$ U_xよりも辺$ U_yを使うべき条件を考えると、
$ d(S, A_{U_x}) + C_{U_x} + d(B_{U_x}, T) \lt d(S, A_{U_y}) + C_{U_y} + d(B_{U_y}, T)
$ A_{U_x} = A_{U_y}を用いて
$ C_{U_x} - C_{U_y} \lt d(B_{U_y}, T) - d(B_{U_x}, T)
となるから、「何個のクエリについて辺$ U_xよりも辺$ U_yを使うべきか」さえわかれば、$ C_{U_x}, C_{U_y}の値がわからずとも、$ d(B_{U_y}, T) - d(B_{U_x}, T)の値によってどのクエリが該当するかがわかる。
タイプ$ -1との比較も似たような感じになる。
よって、合計$ K + \frac{K(K - 1)}{2} = 15通りについて$ \lceil \log_2{Q} \rceil = 6bit 送ればよいので、$ 80点を獲得することができる。
満点解法は上の方法をさらに改善する。まずは全てのクエリについてタイプ$ -1が今のところ最適であると定めておく。
タイプを$ 0, 1, \dots, 5の順に見ていって、
現在のタイプよりも新たなタイプの方がよいなら、そちらを採用する
ことを行う。タイプ$ kを見ている時点で、暫定の最適タイプは$ k+1通りありえるので、これらそれぞれについて、何個のクエリがタイプ$ kを採用するかを送る。$ 6bit ずつ使ってしまうとダメだが、全てのタイプについてのクエリ数の総和が$ Qなので、最悪ケースで
$ \left\lceil \log_2 \{ (Q + 1) \times \left(\frac{Q}{2} + 1\right)^2 \times \left(\frac{Q}{3} + 1\right)^3 \times \left(\frac{Q}{4} + 1\right)^4 \times \left(\frac{Q}{5} + 1\right)^5 \} \right\rceil
bit となり、これなら 64 bit 整数としてエンコードすることができる。
感想
本番なら 80 点とったら即諦めそう