脳log[20211031]

2021年10月31日 (日) [AtCoder] 精進。ARC064-E「Cosmic Rays」(青 diff)。解けてみればド典型という感じだけど、初見ではグラフが見えなかった。問題を読むのは今日で２度目。提出 #26961806 (AC / 956 Byte / 1915 ms)。つい先日「辺に重みがあるんだから BFS ではなくダイクストラ法を使うべきだというのはあるかも。実装も定数倍も重くて気が進まないわけなんだけど」と書いたばかりで、重くて気が進まないプライオリティキューでダイクストラ法をした。ところで Ruby の他の提出を見ると 500 ms を切る提出がちらほらあって、プライオリティキューは使っていない。まねしてみたのがこれ>提出 #26962407 (AC / 413 Byte / 221 ms)。短くて速い。えっ？ どういうことなの？ N の総数が高々 1000 だからなのか完全グラフだからなのか。(完全グラフという数日前に初めて見た単語を使ってみた。Wikipedia によるとクリークと関連があるらしい。クリークの初見は３か月前>20210716)。