転倒数 アルゴリズム

転倒数 (inversion number) とは?

数列 a = {a_0, a_1, a_2 ... a_n-1 } が与えられたとき,

i < j かつ a_i > a_j を満たす (i, j) の組の個数を転倒数または反転数という.

たとえば a = {3, 1, 5, 4, 2} のとき,

i < j かつ a_i > a_j となっている組は,

(3, 1), (3, 2), (5, 4), (5, 2), (4, 2) の 5組であるから転倒数は 5 となる. (添字ではなく要素の組を列挙した)

転倒数は下記のようなバブルソートを行った際の交換回数と等しくなることが知られている. 一回の交換で反転数は1減少し, ソートが完了すると反転数は0となるのでそれはそう.

#!/usr/bin/env python3

def bubble_sort(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(len(A)-1, i, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                cnt += 1
    return cnt

直感的には転倒数は昇順ソートされた状態を正しい並びとしたとき, 正しくない並びとなっている組の数と考えることができる.

転倒数を愚直な実装で求めると時間計算量は  O(n^{2}) となるが以下に示すように  O(n \log{n})アルゴリズムが存在する.

Fenwick Tree(Binary Indexed Tree)を用いる方法

i < j かつ a_i > a_j を満たす要素を数えるには以下の 2 つの方法が考えられる.

  • i についてループを回し i < j かつ a_i > a_j となるものを数える.

  • j についてループを回し i < j かつ a_i > a_j となるものを数える.

どちらもほぼ同じように見えるが, 後者のように考えないとうまくいかない.

後者の方法で i < j かつ a_i > a_j となるものを数えるとき Fenwick Tree を使うと各 j について  O(\log{n}) で求めることができる.

Fenwick Tree は区間の和の計算, 要素の値の更新がそれぞれ  O(\log{n}) でできるデータ構造.

  • C++ による Fenwick Tree の実装例
struct fenwick_tree {
    typedef int T;
    T n;
    vector<T> bit;

    // 各要素の初期値は 0
    fenwick_tree(T num) : bit(num+1, 0) { n = num; }

    // a_i += w
    void add(T i, T w) {
        for (T x = i; x <= n; x += x & -x) {
            bit[x] += w;
        }
    }
    // [1, i] の和を計算.
    T sum(T i) {
        T ret = 0;
        for (T x = i; x > 0; x -= x & -x) {
            ret += bit[x];
        }
        return ret;
    }
    // [left+1, right] の和を計算.
    T sum(T left, T right) {
        return sum(right) - sum(left);
    }
};
  • 使い方

    • fenwinck_tree f_tree(n); で size n の tree を作成.
    • f_tree.sum(x)区間 [1, x] の和を求める.
    • f_tree.sum(l, r)区間 [l+1, r] の和を求める.

    • f_tree.add(i, w) で 0-based-index で i 番目の要素に w を足す.

Fenwick Tree は最初 a = {a_0, a_1, a_2 ... a_n-1} の数列があり, 各要素の初期値は 0 となっている.

j = 0 から n-1 までループを回し. 以下のような処理をすることで転倒数を求めることができる.

fenwinck_tree f_tree(n);

for (int j = 0; j < n; j++) {
    ans += j - f_tree.sum(a[j]);
    f_tree.add(a[j], 1);
}

fenwick tree の i 番目の値が x であるとき, 値が i である要素が x 個あるものとみなす. すると sum(a[j]) が返す値は i < j かつ a_i <= a_j の個数となる. なぜなら sum(a[j]); が実行されるとき fenwick tree に追加されている数列の要素は必ず, 現在の j より小さいときに追加されたものであり(i < j を満たす), sum(a[j]) は区間[1, a[j]] の和であるから.

数えたいのは i < j かつ a_i > a_j であるから, 現在見ている数列の要素の個数である j から sum(a[j]) を減算した値を足せば良い.

注意点としては size n の tree を作成する際の n の値は数列の最大値より大きなものを設定する必要があるという点と, 数列の要素に0以下のものがあると要素の追加ができないので下駄を履かせる必要があるという点である.

分割統治法を使う方法

以下のようなコードでマージソートを行いながら転倒数を求めることもできる.

typedef long long ll;

ll merge_cnt(vector<int> &a) {
    int n = a.size();
    if (n <= 1) { return 0; }

    ll cnt = 0;
    vector<int> b(a.begin(), a.begin()+n/2);
    vector<int> c(a.begin()+n/2, a.end());

    cnt += merge_cnt(b);
    cnt += merge_cnt(c);

    int ai = 0, bi = 0, ci = 0;
    // merge の処理
    while (ai < n) {
        if ( bi < b.size() && (ci == c.size() || b[bi] <= c[ci]) ) {
            a[ai++] = b[bi++];
        } else {
            cnt += n / 2 - bi;
            a[ai++] = c[ci++];
        }
    }
    return cnt;
}

与えられた数列を A とし, その数列を B と C に分割(Devide)する.

B, C をそれぞれソート済みとすると, Aの転倒数はBの転倒数とCの転倒数を足し, さらにBとCとの間にまたがって存在する i < j かつ a[i] > a[j] となるような組の数を足したものとなる.

数列 a = {3, 1, 5, 4, 2,} を例として考える. merge_cnt() が実行されると, 数列は以下のように再帰的に分割される.

f:id:kira000:20190223045138p:plain

A = {4, 2}, B = {4}, C = {2} とする. B と C はそれぞれサイズが1なので転倒数は0である.

BとCを merge するとき, cnt がどのように更新されるかを見る.

    while (ai < n) {
        if ( bi < b.size() && (ci == c.size() || b[bi] <= c[ci]) ) {
            a[ai++] = b[bi++];
        } else {
            cnt += n / 2 - bi;
            a[ai++] = c[ci++];
        }
    }

数列 C の要素が Aに merge されるとき (i < j), cnt は更新されている. これは転倒数の定義 (i < j and a[j] < a[i] となる i, j の組の数) を考えれば当然である.

cnt += n/2 - bi;n/2 は数列B のサイズを表している. bi は BのインデックスでBの要素全てがAに代入されると n/2 となる. 数列Cの要素が merge されるとき, 数列 B のうちまだ merge されていない要素の個数を cnt に足している.

merge の処理が済んだ数列はきちんとソートされる.

分割された数列の転倒数を赤で示したのが下図である.

f:id:kira000:20190223050517p:plain

使用例

AOJ: ALDS1-5 D

参考文献

MSYS2にインストールしたImageMagickが正常に動作しない件について

  • まずは下記のようなコマンドで imagemagick をインストールする.
  • 私は 32bit 版を選んだ.
$ pacman -Ss imagemagick
mingw32/mingw-w64-i686-imagemagick 7.0.3.1-1
    An image viewing/manipulation program (mingw-w64)
mingw64/mingw-w64-x86_64-imagemagick 7.0.3.1-1
    An image viewing/manipulation program (mingw-w64)
$ pacman -S mingw-w64-i686-imagemagick

(略)
  • バージョンの確認をしてインストールが正常にされているかを確かめる.
  • このとき msys2.exe で起動すると path が通っていなくてエラーが出るので mingw32.exe を使う. (msys2-launcher を使うことを前提にしてる)
$ convert -version
Version: ImageMagick 7.0.3-1 Q16 i686 2016-10-07 http://www.imagemagick.org
Copyright: Copyright (C) 1999-2016 ImageMagick Studio LLC
License: http://www.imagemagick.org/script/license.php
Features: Cipher DPC HDRI Modules OpenMP
Delegates (built-in): bzlib cairo djvu fftw fontconfig freetype gslib jbig jng jp2 jpeg lcms lqr ltdl lzma openexr pangocairo png ps rsvg tiff webp wmf xml zlib
  • 何かしらのコマンドを使おうとするとエラーが出る.
$ convert test.jpg test.png
convert.exe: no decode delegate for this image format `JPG' @ error/constitute.c/ReadImage/508.
  • 使用可能なフォーマットを表示させようとするも何も表示されない.
$ convert -list format
  • 日本語でググっても解決方法が見つからなかった .
  • 英語でググったらいいのが出てきた (https://github.com/Alexpux/MINGW-packages/issues/1885)
  • coder modulesconfigure のパスが通ってないので次のように bash の設定ファイルを編集しろとのこと.
export MAGICK_HOME="/mingw64/bin"
export MAGICK_CONFIGURE_PATH="/mingw64/etc/ImageMagick-7"
export MAGICK_CODER_MODULE_PATH="/mingw64/lib/ImageMagick-7.0.3/modules-Q16HDRI/coders"
  • 自分の場合は以下のような記述を .bashrc に追加した.
export MAGICK_HOME="/mingw32/bin"
export MAGICK_CONFIGURE_PATH="/mingw32/lib/ImageMagick-7.0.3"
export MAGICK_CODER_MODULE_PATH="/mingw32/lib/ImageMagick-7.0.3/modules-Q16HDRI/coders"
  • 1度閉じて再度起動すると変更が適用される.
$ convert -list format
   Format  Module    Mode  Description
-------------------------------------------------------------------------------
      3FR  DNG       r--   Hasselblad CFV/H3D39II
      AAI* AAI       rw+   AAI Dune image
       AI  PDF       rw-   Adobe Illustrator CS2

(略)
  • ImageMagick をアップデートした際にはその都度 path の値を変更する必要がある.

参考

github.com

github.com

yaritakunai.hatenablog.com

逆ポーランド記法による数式処理

逆ポーランド記法とは

逆ポーランド記法(Reverse Polish Notation: RPN)は、演算子オペランドの後に記述する数式やプログラムの記法の一つです。

例えば、一般的な中間記法で記述された数式 (1+2)*(5+4)逆ポーランド記法では 1 2 + 5 4 + * と記述されます。

逆ポーランド記法では、中間記法で必要とされた括弧が不要であり、また式の計算(評価) の実装が容易であるためコンピュータでの利用に適しています。

演算子を被演算子の後ろに置くことから、後置記法 (Postfix Notation) とも言うらしいです。

逆ポーランド記法で表された数式の評価

実装にはスタックを用います。

先頭から順に記号を読み込み、その記号が演算子以外であればスタックに値を積み、演算子であればスタックから値を2つ取り出して演算結果をスタックに積む、という簡単な操作の繰り返していき、最後にスタックの中に残った値が答えとなります。

AOJ 0087: Strange Mathematical Expression

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0087

試しにこの問題を解いてみましょう。

  • C++による解答例
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <cstdlib>
#include <cctype>
#include <cstdio>

using namespace std;

int main()
{
    string s;
    stack<double> St;
    double a, b;
    while (getline(cin, s)) {
        stringstream ss(s);

        while (ss >> s) {
            if (s == "+") {
                b = St.top(); St.pop();
                a = St.top(); St.pop();
                St.push(a+b);
            }
            else if (s == "-") {
                b = St.top(); St.pop();
                a = St.top(); St.pop();
                St.push(a-b);
            }
            else if (s == "*") {
                b = St.top(); St.pop();
                a = St.top(); St.pop();
                St.push(a*b);
            }
            else if (s == "/") {
                b = St.top(); St.pop();
                a = St.top(); St.pop();
                St.push(a/b);
            }
            else {
                St.push(atoi(s.c_str()));
            }
        }
        printf("%.6f\n", St.top());
        St.pop();
    }
    return 0;
}   
# coding: utf-8

def Calculate_RPN(L):
    St = []
    for i in L:
        if i == '+':
            b, a = float(St.pop()), float(St.pop())
            St.append(a+b)
        elif i == '-':
            b, a = float(St.pop()), float(St.pop())
            St.append(a-b)
        elif i == '*':
            b, a = float(St.pop()), float(St.pop())
            St.append(a*b)
        elif i == '/':
            b, a = float(St.pop()), float(St.pop())
            St.append(a/b)
        else:
            St.append(i)

    return St[0]


while True:
    try:
        s = raw_input().split()

    except EOFError:
        break

    print Calculate_RPN(s)

中間記法で記述された数式を逆ポーランド記法に変換する

この変換もスタックを用いて行うことが出来ます。

次のような手順で変換できます。

ほぼここ(http://knowledge.sakura.ad.jp/etc/220/)に書いてあることのコピペ。

  • 数式を左から順に読み込む
  • 数値だったら出力だったらスタックに積む だったらスタック上の演算子が出てくるまで出力しは削除する
  • 演算子だったらスタックに積む
    • スタックトップの演算子の優先順位がスタックに積まれる演算子より高ければそれを出力する
  • 数式を最後まで読み込んだ後、スタック上に演算子が残っていればそれをスタックが空になるまで順に出力する

逆ポーランド記法では演算子の優先順位は左に行くほど高くなります。

中間記法の数式を左から読み込んでいき演算子をスタックに積んだとき、+-*/などの同じ優先順位のものは先にスタックに入っているものの方が当然優先順位は高くなります。(中間記法では同じ優先順位なら左から計算が行われるから) (それはそう)

空白区切りなしで中間記法で表された数式1行が与えられ逆ポーランド記法に変換したものを出力するプログラムは次のように書けます。

動けばいいやと思って書いたクッソ汚いコードなのであまり参考にしないほうが良いと思います。

#include <iostream>
#include <string>
#include <stack>
#include <map>
#include <cstdlib>
#include <cctype>

using namespace std;

void str2arr(string s, string A[]) {
    int n = 0;
    string tmp = "";

    for (int i = 0; s[i] != '=' ; i++) {
        if ('0' <= s[i] && s[i] <= '9') {
            tmp += s[i];
        }
        else {
            if (tmp != "") { 
                A[n++] = tmp;
                tmp = "";
            }
            A[n++] = s[i];
        }
    }
    if (tmp != "") { A[n++] = tmp; }
    A[n++] = "=";
}

void Generate_RPN(string A[], string B[]) {
    map<string, int> table;
    stack<string> St;
    table["*"] = 1;
    table["/"] = 1;
    table["+"] = 0;
    table["-"] = 0;
    table["("] = -1;
    table[")"] = -1;

    int j = 0;
    for (int i = 0; A[i] != "="; i++) {
        if ('0' <= A[i][0] && A[i][0] <= '9') {
            B[j++] = A[i];
        }
        else if (A[i] == "(") {
            St.push(A[i]);
        }
        else if (A[i] == ")") {
            while (St.top() != "(") {
                B[j++] = St.top(); St.pop();
            }
            St.pop();
        }
        else {
            while ((!St.empty()) && (table[St.top()] >= table[A[i]])) {
                B[j++] = St.top(); St.pop();
            }
            St.push(A[i]);
        }
    }
    while (!St.empty()) {
        B[j++] = St.top(); St.pop();
    }
    B[j] = "=";
}

int main() {
    string A[100], B[100];
    string s;

    cin >> s;
    s += "=";

    str2arr(s, A);
    Generate_RPN(A, B);

    for (int i = 0; B[i] != "="; i++) {
        cout << B[i];
        cout << (B[i+1] == "=" ? "\n" : " ");
    }

    return 0;
}
# coding: utf-8

# Convert String to List
def String2List(s):
    L = []; tmp = ""
    for i in s:
        if i.isdigit():
            tmp += i
        else:
            if tmp != "":
                L.append(tmp)
                tmp = ""
            L.append(i)
    if tmp != "":
        L.append(tmp)

    return L

# generate Reverse Polish Notation
def Generate_RPN(L):
    S, L2 = [], []
    table = {"*": 1, "/": 1, "+": 0, "-": 0, "(": -1, ")": -1}
    for i in L:
        if i.isdigit():
            L2.append(i)
        elif i == "(":
            S.append(i)
        elif i == ")":
            while S[-1] != "(":
                L2.append(S.pop())
            S.pop()
        else:
            while len(S) != 0 and (table[S[-1]] >= table[i]):
                L2.append(S.pop())
            S.append(i)

    while len(S) != 0:
        L2.append(S.pop())

    return L2

s = raw_input()
print " ".join(Generate_RPN(String2List(s)))

中間記法で記述された数式を評価する

先に書いた2つのコードを組み合わせれば中間記法で記述された数式の評価が出来ます。

AOJ0109: Smart Calculator

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0109&lang=jp

この問題を解いてみましょう。

C++逆ポーランド記法の数式を評価するとき全てdoubleで計算して最後にintにキャストするみたいにやったら Wrong Answer が出て辛かったです。

  • C++による解答例
#include <iostream>
#include <string>
#include <stack>
#include <map>
#include <cstdlib>
#include <cctype>

using namespace std;

void str2arr(string s, string A[]) {
    int n = 0;
    string tmp = "";

    for (int i = 0; s[i] != '=' ; i++) {
        if ('0' <= s[i] && s[i] <= '9') {
            tmp += s[i];
        }
        else {
            if (tmp != "") { 
                A[n++] = tmp;
                tmp = "";
            }
            A[n++] = s[i];
        }
    }
    if (tmp != "") { A[n++] = tmp; }
    A[n++] = "=";
}

void Generate_RPN(string A[], string B[]) {
    map<string, int> table;
    stack<string> St;
    table["*"] = 1;
    table["/"] = 1;
    table["+"] = 0;
    table["-"] = 0;
    table["("] = -1;
    table[")"] = -1;

    int j = 0;
    for (int i = 0; A[i] != "="; i++) {
        if ('0' <= A[i][0] && A[i][0] <= '9') {
            B[j++] = A[i];
        }
        else if (A[i] == "(") {
            St.push(A[i]);
        }
        else if (A[i] == ")") {
            while (St.top() != "(") {
                B[j++] = St.top(); St.pop();
            }
            St.pop();
        }
        else {
            while ((!St.empty()) && (table[St.top()] >= table[A[i]])) {
                B[j++] = St.top(); St.pop();
            }
            St.push(A[i]);
        }
    }
    while (!St.empty()) {
        B[j++] = St.top(); St.pop();
    }
    B[j] = "=";
}

int Calculate_RPN(string s[]) {
    stack<double> St;
    double a, b;

    for (int i = 0; s[i] != "="; i++) {
        if (s[i] == "+") {
            b = int(St.top()); St.pop();
            a = int(St.top()); St.pop();
            St.push(a+b);
        }
        else if (s[i] == "-") {
            b = int(St.top()); St.pop();
            a = int(St.top()); St.pop();
            St.push(a-b);
        }
        else if (s[i] == "*") {
            b = int(St.top()); St.pop();
            a = int(St.top()); St.pop();
            St.push(a*b);
        }
        else if (s[i] == "/") {
            b = int(St.top()); St.pop();
            a = St.top(); St.pop();
            St.push(a/b);
        }
        else {
            St.push(atoi(s[i].c_str()));
        }
    }
    return int(St.top());
}

int main() {
    int n;
    string A[100], B[100];
    string in;

    cin >> n;

    while (n--) {
        cin >> in;
        str2arr(in, A);
        Generate_RPN(A, B);
        cout << Calculate_RPN(B) << endl;
    }

    return 0;
}
# coding: utf-8

# Convert String to List
def String2List(s):
    L = []; tmp = ""
    for i in s:
        if i.isdigit():
            tmp += i
        else:
            if tmp != "":
                L.append(tmp)
                tmp = ""
            L.append(i)
    if tmp != "":
        L.append(tmp)

    return L

# generate Reverse Polish Notation
def Generate_RPN(L):
    S, L2 = [], []
    table = {"*": 1, "/": 1, "+": 0, "-": 0, "(": -1, ")": -1}
    for i in L:
        if i.isdigit():
            L2.append(i)
        elif i == "(":
            S.append(i)
        elif i == ")":
            while S[-1] != "(":
                L2.append(S.pop())
            S.pop()
        else:
            while len(S) != 0 and (table[S[-1]] >= table[i]):
                L2.append(S.pop())
            S.append(i)

    while len(S) != 0:
        L2.append(S.pop())

    return L2

def Calculate_RPN(L):
    St = []
 
    for i in L:
        if i == '+':
            St.append(int(St.pop()) + int(St.pop()))
        elif i == '-':
            St.append(-int(St.pop()) + int(St.pop()))
        elif i == '*':
            St.append(int(St.pop()) * int(St.pop()))
        elif i == '/':
            a = int(St.pop())
            b = float(St.pop())
            St.append(b/a)
        else:
            St.append(i)
 
    return St[0]


n = int(raw_input())

for _ in xrange(n):
    s = raw_input()
    print int(Calculate_RPN(Generate_RPN(String2List(s[:-1]))))

感想

やるだけなのにバグを埋め込みまくってコードを書くのにすごい時間がかかって辛かったです。あと一応AOJのシステムテストは通りましたが間違ってる可能性も大いにあるのでご注意ください。

AOJ0109: Smart Calculatorの他の人の解答を見てみたらみんな全然違う解き方をしていたのでみんなの解き方での実装もそのうちやりたいと思いました。

これ(https://gist.github.com/draftcode/1357281)とかめっちゃ参考になりそう。

参考文献

USBオーディオ変換ケーブルを買った。

PCに接続したヘッドホンの片側だけ音が聞こえなくなるということがあった。

別のヘッドホンに変えても同じ症状が起きたので、原因はヘッドホンの断線やプラグの酸化などではなくPCの差込口の方であることが分かった。

電子工作の心得があるわけでもないので自力で修理などできるはずもなく、新しいPCケースを買うのも面倒なのでしばらく放置していた。

中途半端にヘッドホンのプラグを差し込むと両方から聞こえる(ただしいくつかの音が明らかに抜け落ちている)という謎現象があったのでしばらくそれで我慢していたのだが、

USBの変換ケーブルなるものがあることを知り、試してみた。

BUFFALOの製品を買った。型番は BSHSAU01BK

価格は Amazon で 1,109 円だった。

 

f:id:kira000:20161115141640j:plain

 

https://www.amazon.co.jp/gp/product/B007WPMIN8/ref=oh_aui_detailpage_o00_s00?ie=UTF8&psc=1

使用した感じ不具合はないが、Amazon レビューなどによると、この製品に限らず USBオーディオ変換ケーブル全般に言えることとして、マイクにノイズが入るということがあるらしい。

自分は聞くだけなので関係ないけど、マイクも使う人は注意した方がいいと思う。

 

[追記]

後日談というか今回のオチ。

 

もしやと思ってマザーボードに接続されているオーディオのピンを一度抜いて、再びしっかりと差し込んだたら問題が解決した。

 

結局どこにも不具合は存在せず、ただマザーボード側のコネクタがしっかりささってなかったことが原因だったのだ。

冷静に考えるとまっさきに疑うべきポイントなんだよなぁ。

Pythonの組み込み実装のROT13を読む。

 アルファベットを任意の文字数ずらした暗号をシーザー暗号という。

シーザー暗号の中で13文字ずらしたものをとくにROT13と呼ぶ。

PythonではこのROT13が言語に組み込み実装として存在しており、thisモジュールはこのROT13でエンコードされている。

>>> print "hogefuga".decode("rot13")
ubtrshtn
>>> print "hogefuga".encode("rot13")
ubtrshtn
>>>

自明ではあるが上の出力でROT13においてはデコードとエンコードが同じ処理であることも確認できる。

組み込み実装として用意されているROT13のソースコードはthis.pyを見れば確認できる。

https://github.com/python/cpython/blob/master/Lib/this.py

23 d = {}
24 for c in (65, 97):
25     for i in range(26):
26         d[chr(i+c)] = chr((i+13) % 26 + c)
27 
28 print "".join([d.get(c, c) for c in s])

23行目で空の辞書オブジェクトを生成している。

24行目ではついつい、

for c in (65, 97):

の部分を

for c in range(65, 97):

に空目してしまいがちだが

range()関数は使っていないので注意が必要。

65と97はASCII文字コードにおけるAaである。

chr()関数はASCII文字コードにおける整数を文字に変換する関数で、逆の処理をするのがord()関数。

  • chr()
>>> for c in (65, 97):
...   for i in range(26):
...     print chr(i+c),
...
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z
>>>
  • ord()
>>> for c in ('A', 'a'):
...   for i in range(26):
...     print ord(c)+i,
...
65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
>>>

26行目の

d[chr(i+c)] = chr((i+13) % 26 + c)

d['A'] = 'N'

d['B'] = 'O'

d['C'] = 'P'

...

のようなことをしており{'A':'N', 'B':'O', 'C':'P' ...(以下略)}という辞書を生成している。

13というのがずらす文字数で0から25の整数である変数iに13を足したものの剰余をとり65もしくは97を足してchr()関数を実行することで、うまくシーザー暗号を表現している。

この13をnにすることでより汎用性の高いプログラムになりそうである。

最後のprint "".join([d.get(c, c) for c in s])だが、

"".join()はリストから文字列への変換操作である。

>>> "".join(['h', 'o', 'g', 'e'])
'hoge'

リストは内包表記を使っている。d.get(c, c)はd[c]があればその値を返しなければcをそのまま返すという意味である。

>>> d = {'A':'N', 'B':'O',}
>>> d.get('A')
'N'
>>> d.get('N')
>>> d.get('N', 'N')
'N'

引数に文字列sと整数nをとり、文字列sをn文字シフトした文字列を返す関数caesar()は次のように書ける。

def caesar(s, n):
    d = {}
    for c in (65, 97):
        for i in range(26):
            d[chr(i+c)] = chr((i+n) % 26 + c)

    return "".join([d.get(c, c) for c in s])

例えばAOJのこの問題(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0017)の仕様に合わせるのであれば、

こんな風に使える。