scipyでABC061 D Score Attackを解こうとして解けなかった話

はじめに

今までAtCoderをやってきて最短経路問題を避けてきたのですが、レート水色目前にしてようやく重い腰を上げFloyd-Warshall法やDijkstra法などを勉強しました。
その中で最短経路問題を解くのにscipyのライブラリを使えることを知りました。 note.nkmk.me https://juppy.hatenablog.com/entry/2019/06/04/scipy%E3%81%AEFloyd-Warshall%E3%81%A8Dijkstra%E3%81%AE%E3%81%99%E3%81%99%E3%82%81_Python_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder_1juppy.hatenablog.com kawap23.hatenablog.com じゃあ自分もやってみよー、せっかくだし負の辺があってジョンソン法が使われる問題でやってみよーと思って解いてみたのが今回の話です。

問題

atcoder.jp

ようは有向グラフで1つ目の点から最終的にN個目の点に移動するときに、最善な移動をしたときの点数(距離)はいくらになるのかといった問題です。
逆に考えると、距離を全部マイナスにして点数を最小化する問題と考えることができます。
最短経路問題そのまんまですね。

解いてみる

コード

scipy.sparse.csgraph.shortest_path()で負の辺が存在するときは自動的にジョンソン法が使われます。
まずは素直に実装してみます。
無限ループがあったときはshortest_path()を呼んだときにNegativeCycleErrorを吐かれるのでそのときに"inf"を出力すれば良さそうです。

def resolve():
    from scipy.sparse.csgraph import shortest_path
    from scipy.sparse import csr_matrix
    import numpy as np
    n, m = map(int, input().split())
    edge = np.array([input().split() for _ in range(m)], dtype=np.int64).T
    a = csr_matrix((-edge[2], (edge[:2] - 1)), shape=(n, n))
    try:
        s = shortest_path(a, indices=0)
        m = -s[n - 1]
        print("{}".format(int(m)))
    except:
        print("inf")
if __name__ == "__main__":
    resolve()

自環境で動作することを確認し、提出してみます。

結果

8/30 ACでした。
サンプルデータもWAになってた(自環境では大丈夫だった)ので急いでコードテストしてみると、何故か全て"inf"が出力されます。
嫌な予感がしてtry～exceptを外して再実行すると、以下のエラーが吐かれていました。

TypeError: shortest_path() got an unexpected keyword argument 'indices'

もしやと思いABC061でのscipyのversionを確認すると0.13.3でした。

import scipy
print(scipy.__version__)

0.13.3

当時のReferenceを確認すると……

引数にindicesがない！！！

どうやら後になって追加された仕様っぽいです。
(ABC162以降の環境ではv1.4.1となっているので利用可能)

コード②

ということで少し書き直してみます。 indicesを外し受け取った結果の[0][n - 1]を見ることにし(どうせ全探索するし速度は変わらないはず)、念の為NegativeCycleErrorだけを例外で受け取るようにします。

def resolve():
    from scipy.sparse.csgraph import shortest_path
    from scipy.sparse import csr_matrix
    import numpy as np
    n, m = map(int, input().split())
    edge = np.array([input().split() for _ in range(m)], dtype=np.int64).T
    a = csr_matrix((-edge[2], (edge[:2] - 1)), shape=(n, n)).toarray()
    try:
        s = shortest_path(a)
        m = -s[0][n - 1]
        print("{}".format(int(m)))
    except scipy.sparse.csgraph.NegativeCycleError:
        print("inf")
if __name__ == "__main__":
    resolve()

結果②

17/30 AC……。
WAの理由を小一時間考えたところ、以下の反例のように1→Nのルート以外で負の無限ループになったときもNegativeCycleErrorを吐かれることに気づきました。

結論

ABC061-Dにscipyのshortest_path()は使えない

おわりに

結局ダメだったのかよ！という話になってしまいますが、標準ライブラリに頼らず原理を理解したり自前のライブラリを用意したりするのは大事だなという教訓になったのでブログ記事にしてみました。
ACしたい人はhttp://prdc.hatenablog.com/entry/2017/09/07/112849などを参考にしてみてください。
次に青パフォを出せれば水色コーダーになれそうなので頑張ります。

徒然

思いついたら書きます

scipyでABC061 D Score Attackを解こうとして解けなかった話

はじめに

問題

解いてみる

コード

結果

コード②

結果②

結論

おわりに