swiftのNumeric構造体を作りInt型の時だけmod計算する【競技プログラミング】

はじめに

• タイトルを見ても、何を言いたいのか伝わりづらくてゴメンナサイ。なろう系小説も長いタイトルのわりに雰囲気しか伝わらないよね？同じようなものだと思って欲しい。
• 先日、正方行列の構造体を作ったけど、正方行列の要素がInt型の時だけmodして要素の中身を軽量化しようとしたら頭がこんがらがったから、そこだけ切り出したのが今回の投稿です。
• swiftは型定義をしっかりやらないといけないので、慣れるまでは大変だね。まぁ。慣れたら慣れたで、pythonみたいな型が適当な言語が気持ち悪くて馴染めなくなるんだけど。

加算代入演算「+=」のみを実装したNumeric構造体

• まず、mod導入前の、シンプルなNumeric構造体を作る。ちなみにNumericは「加減算と乗算が出来る」という制約を持つプロトコルです。

struct Num<T:Numeric> {
    private var data:T

    init(_ data:T){
        self.data = data
    }
    
    static func +=(left:inout Self,right:Self){
        left.data += right.data
    }
}

var (dbl1,dbl2) = (Num(11.1),Num(22.2))
var (int1,int2) = (Num(11),Num(22))

dbl1 += dbl2
print(dbl1) // Num<Double>(data: 33.3)

int1 += int2
print(int1) // Num<Int>(data: 33)

要素の型がIntの時だけmを法とした要素とする構造体

• 競技プログラミングでは、解答の数値が大きくなるとき、modにより数を小さくすることが多いため、Int型の時にmod計算するように機能を追加する。

struct Num<T:Numeric> {
    private var data:T
    let m : Int? // 追加①

    init(_ data:T){
        self.m = nil // 追加②
        self.data = data
    }
    init(_ data:T,m:Int? = nil) where T==Int{ // 追加③
        self.m = m
        if let mod = m {
            self.data = data % mod
        } else {
            self.data = data            
        }
    }
    
    static func +=(left:inout Self,right:Self){
        left.data += right.data
    }
    static func +=(left:inout Self,right:Self) where T==Int { // 追加④
        left.data += right.data
        if let mod = left.m { left.data %= mod }
    }
}

var (dbl1,dbl2) = (Num(11.1),Num(22.2))
var (int1,int2) = (Num(11,m:13),Num(22)) // 追加⑤int1でm=13

dbl1 += dbl2
print(dbl1) // Num<Double>(data: 33.3, m: nil)

int1 += int2
print(int1) // Num<Int>(data: 7, m: Optional(13))

• 上記のように、型ジェネリックTについて、通常はNumericプロトコルに属すところ、更に細分化して、Int型に属すときは、mの中身がnilでなければ、イニシャライザinitと演算子+=で、mod計算を行わせている。
• 上記の計算例では、m=13としたため、mod計算前は33となっていた値が、7となっている。

累乗計算の関数powもNumeric用とInt用を別に用意する

• まず、「*=」関数を「+=」と同様に作成する。当然、Intではmod対応版を用意している。
• mod対応は「*=」関数の中で行うので、関数powの中ではmod計算の為のコードは書かない。よって、Numeric用もInt用も中身のコードが全く同じとなるが、「*=」がNumeric版とInt版の二種類有るので、powもInt版の「*=」を使いたければ、要素がInt版である制約を宣言しないと駄目。
• ちなみに、累乗計算を高速に行うために、繰り返し二乗法を採用してます。

    static func *=(left:inout Self,right:Self){
        left.data *= right.data
    }
    static func *=(left:inout Self,right:Self) where T==Int { // 追加④
        left.data *= right.data
        if let mod = left.m { left.data %= mod }
    }    
    
    func pow(_ n:Int)->Self {
        var ans = self
        var x = self
        var i = n - 1
        while i > 0 {
            if i % 2 == 1 {ans *= x}
            x *= x
            i >>= 1
        }
        return ans
    }
    // Int制約版のpow関数
    func pow(_ n:Int)->Self where Self == Num<Int> {
        var ans = self
        var x = self
        var i = n - 1
        while i > 0 {
            if i % 2 == 1 {ans *= x}
            x *= x
            i >>= 1
        }
        return ans
    }

var (dbl1,dbl2) = (Num(11.0),Num(22.0))
var (int1,int2) = (Num(11,m:13),Num(22)) // 追加⑤int1でm=13

dbl1 *= dbl2
print(dbl1) // Num<Double>(data: 242.0, m: nil)
dbl1 = dbl1.pow(2)
print(dbl1) // Num<Double>(data: 58564.0, m: nil)

int1 *= int2
print(int1) // Num<Int>(data: 8, m: Optional(13))
int1 = int1.pow(2)
print(int1) // Num<Int>(data: 12, m: Optional(13))
// Int制約版のpow関数をコメントアウトしたときの結果
print(int1) // Num<Int>(data: 64, m: Optional(13))

• 上記で、Int制約版のpow関数は、制約無しのpow関数と「where Self == Num」以外は違いがない。しかし、このInt制約版のpow関数を用意しないと、mod13が反映されず、8の二乗の64がそのまま出力される。

おわりに

• 今回初めて、関数を「where T == Int」でオーバーロードしたけど、引数が全く同じ型名Selfでも、オーバーロードできるんだね。
• 最初の考えでは、追加①②は元の構造体定義で書けるけど、追加③④は、以下のようにextensionで追加定義するしかないと思っていたよ。

extension Num where T==Int{
    init(_ data:T,m:Int? = nil){
        self.mod = m
        if let mod = m {
            self.data = data % mod
        } else {
            self.data = data            
        }
    }
    
    static func +=(left:inout Self,right:Self){
        left.data += right.data
        if let mod = left.m { left.data %= mod }
    }
}

• 今回は勉強になりました。つか、この辺のジェネリックを用いたswiftのテクニックをまとめたテキストないかなぁ。でも、swiftは不人気言語だから無さそうだね。