全点対最短経路問題(All-Pairs Shortest Paths Problem)において、Floyd-Warshall法などで最短経路の距離行列が求められている場合に、その最短距離行列から対応する経路行列を構築するアルゴリズムについてのメモ。アルゴリズムはO(n^3)のアルゴリズムで単…

https://www.spoj.pl/problems/ONP/を解くために書いたRubyのコードを、後々使えそうだからポストする。 $priority = [[['+',0],['-',1],['*',2],['/',3],['^',4]]] def recur(s, idx) op_stack = Array.new p = idx while p < s.length c = s[p].chr case c…

アフィン暗号の復号化についての情報が、検索してもすぐには見つけられなかったのでメモ。アフィン暗号は文字 r を２つのキー a,b を用い、E(r)=(a*r+b)%N 式により暗号化、D(r)=((r-b+N*k)/a)%N 式により復号化する方法(Nは文字種数、k は(r-b+N*k)0 (mod a…