AtCoder Beginner Contest 307 B - racecar

AtCoderをやり始めた。 全然問題が解けないので、復習する。

atcoder.jp

問題

英小文字のみからなる$N$個 の文字列 $S_1,S2,...S_N$が与えられる。 $ 1以上N以下$の相異なる$整数i,j$であって、$S_i, S_j$をこの順に連結した文字列が回文となるようなものが存在するか判定せよ。 ただし、長さ$M$の文字列$T$が回文であるとは、任意の$ 1 \leq i \leq M $について、$T$の$i$文字目と$(M+1-i)$文字目が一致していることをいう。

制約

• $ 2 \leq N \leq 100 $
• $ 1 \leq |S_i| \leq 50 $
• $ Nは整数 $
• $ S_i は英小文字からなる文字列 $
• $ S_i はすべて異なる $

何も考えず書いたコード（間違い）

package main
 
import (
    "fmt"
    "strings"
)
 
func main() {
    var N int
    fmt.Scanf("%d", &N)
 
    S := make([]string, N)
    for i := 0; i < N; i++ {
        fmt.Scan(&S[i])
    }
 
    ans := "No"
    for i := 0; i < N; i++ {
        for j := i + 1; j < N; j++ {
            slice := strings.Split(S[i]+S[j], "")
            len := len(slice)
            // fmt.Println(slice)
            for k := 0; k <= len/2; k++ {
                // fmt.Println("slice", slice[k], slice[len-k-1])
                if k == len/2 {
                    ans = "Yes"
                    break
                }
                if slice[k] != slice[len-k-1] {
                    break
                }
            }
            if ans == "Yes" {
                break
            }
        }
        if ans == "Yes" {
            break
        }
    }
 
    fmt.Println(ans)
}

間違いポイント

• まず、コードは汚いけど考え方は正しかった。
• j := i + 1としているが、j := 0からすべき。でないと、網羅できないケースがでてくることに気がつけなかった。
• 文字列判定は止めるべし。

正しい解

package main

import "fmt"

func main() {
    var N int
    fmt.Scanf("%d", &N)

    S := make([]string, N)
    for i := 0; i < N; i++ {
        fmt.Scanf("%s", &S[i])
    }

    ex := false
    for i := 0; i < N; i++ {
        for j := 0; j < N; j++ {
            f := S[i]
            s := S[j]
            if s == f {
                continue
            }

            ex = chmatch(f + s)
            if ex {
                break
            }
        }
        if ex {
            break
        }
    }

    if ex {
        fmt.Println("Yes")
    } else {
        fmt.Println("No")
    }
}

func chmatch(m string) bool {
    for i := 0; i < len(m)/2; i++ {
        if m[i] == m[len(m)-1-i] {
            continue
        } else {
            return false
        }
    }
    return true
}

ポイント

• j := 0から開始して、ケースを網羅できた。
• 文字列判定をやめて、boolの判定へ変更し、スッキリさせた。
• コンテスト中は、普段のパフォーマンスが全然だせない。文字列判定とか普段使わない方法でやったり、変な焦りがあるので、徐々に克服を目指すべし。

AtCoder Beginner Contest 306 B - Base 2

AtCoderをやり始めた。 全然問題が解けないので、復習する。

atcoder.jp

問題

$0$と$1$からなる長さ$64$の数列 $ A = (A_0,A_1,...,A_{63}) $ が与えられる。 $A_0 2^0 +A_1 2^1+...+A_{63}2^{63} $を求めよ。

制約

• $ A_i は0または1 $

何も考えず書いたコード（間違い）

package main
 
import (
    "fmt"
    "strconv"
)
 
func main() {
    i2 := make([]int, 64)
    for i := 0; i < 64; i++ {
        fmt.Scanf("%d", &i2[i])
    }
 
    s2 := ""
    for i := 63; i >= 0; i-- {
        s2 += strconv.Itoa(i2[i])
    }
 
    ans, _ := strconv.ParseInt(s2, 2, 64)
 
    fmt.Println(ans)
}

間違いポイント

• int64は、最大値が9223372036854775807。 $ 64の数列 A = (A_0,A_1,...,A_{63}) が全て1の値 $ は、18446744073709551615 のため、int64では入らない。
• よって、strconv.ParseInt() も使えない。

正しい解

package main

import (
    "fmt"
    "math"
)

func main() {
    ui := make([]uint64, 64)
    for i := 0; i < 64; i++ {
        fmt.Scanf("%d", &ui[i])
    }

    var ans uint64
    for i, v := range ui {
        ans += v * uint64(math.Pow(2, float64(i)))
    }
    fmt.Println(ans)
}

ポイント

• int64ではなくuint64を使う。
• strconv.ParseInt()を使用せず、愚直に2進数から10進数へ変換する。

「ちょうぜつソフトウェア設計入門――PHPで理解するオブジェクト指向の活用」を読んだ感想

「ちょうぜつソフトウェア設計入門――PHPで理解するオブジェクト指向の活用」を読み終えました。

ちょうぜつソフトウェア設計入門――PHPで理解するオブジェクト指向の活用

とても勉強になったので、ざっくり感想を書いていきます。

本書を手に取った理由

表紙がかわいいですよね。

驚くべきことに、本の著者である 田中ひさてる さん 自身で表紙のイラストも描かれたとのこと。

本も書けるし、イラストも描けるし。。。めちゃすごいよこの人。。。

あと、もう一つが、@iwasimanさんの感想がとても面白かったからです。

iwasiman.hatenablog.com

特に第1章の感想を見て吹いたので、是非読んでみたいと思えました。

あと、題材にPHPを選んでいるところも良いですね。（PHPなら私でも読めるっ！）

実際読んでみた感想

マジでクリーンアーキテクチャーの説明がわかりやすい。。。

ちょいちょい出てくるイラスト漫画がいい感じの落ちになっていて、それもわかり易さに貢献している気がします。

たしかに、ボブおじさんのクリーンアーキテクチャー本を読んで、いまいちよくわからないなぁと思う人はこっちも読むとスッキリするかもしれない。。。

第2章のパッケージ原則については、個人的にちゃんとした本とか読んだことがなかったので、大変勉強になりました。

この章の内容って、どういったところから学ばれたのかなぁ。。。と、調べてみると、本の著者である 田中ひさてる さん 自身の資料を発見！

speakerdeck.com

パッケージ原則については、（個人的な学びも含めて）以下に纏めておく。

• 再利用・リリース等価の原則（Reuse-Release Equivalent Principle）REP
  • リリースされたもの（mainブランチのもの）だけを再利用せよ。
• 全再利用の原則（Common Reuse Principle）CRP
  • ひとつのパッケージに起きたコード変更は、すべて利用するか、まったく利用しないのか選ぶべし。
  • つまり、部分的に使用してはならないということ。だからこそ、パッケージは責務で分けなさい。
• 閉鎖性共通の原則（Common Closure Principle）CCP
  • ひとつの変更が必要なとき、できるかぎりひとつのパッケージだけを交換すれば済む形にせよ。
  • つまり、疎結合正を意識せよ。
• 非循環依存関係の原則（Acyclic Dependencies Principle）ADP
  • パッケージの依存が循環してはならない。つまり、パッケージ間は必ず単一方向での依存にすべし。
• 安定依存の原則（Stable Dependencies Principle）SDP
  • 依存すべきパッケージは安定しているもの（変更が発生しにくいもの）にすべし。
• 安定度・抽象度等価の原則（Stable Abstractions Principle）SAP
  • 安定度が高いと抽象度も高くなくてはならない。安定度が低いと抽象度も低くすべし。
  • ここで言う抽象は、抽象クラス、インターフェースだけでなく言語そのものやライブラリ、業務や特定の技術に依存しない時間や配列などの幅広い抽象を指している。

あと、オブジェクト指向については、「定義はない」とバッサリ言い切っていることに驚きました。

個人的には、カプセル化、抽象化、継承、ポリモーフィズムの4つの基本原則があってのオブジェクト指向だと思っていたので、「定義はない」というのに驚きました。

よくよく考えてみると、クラスのないGo言語とかでもオブジェクト指向で書けるらしいし、確かにそうだよね。。。と思う。オブジェクト指向を説明する本が、「Java」や「PHP」が多いだけで、言語依存ではないってことなんだな。。。と再認識しました。

このあたりでもうお腹いっぱい。。。。気がつけば、この時点でまだ30%も読み終わってないことに気づいて、本書のボリュームと内容の深さにすごく驚いたのを覚えています。

続いて、SOLID原則の説明やテストの話。

ここでまさかのFizzBuzzエンタープライズエーディションで説明されるとは思わなかった。。。

オブジェクト指向の「定義はない」けど、SOLIDに則していればオブジェクト指向なんじゃない？むしろ、SOLIDに則していないものをオブジェクト指向とは呼ばないんじゃない？という著者の考えが非常に興味深いし、たしかにそうだよなぁ。。。と思わされた。。。

あとは、継承よりも委譲だよ。という話とか、デザインパターンの話もありました。

このあたりも本とか読んだことない人には、オススメできそう。。。とてもわかり易い。

最後に、個人的に一番面白く感じたのが「9-4 ウォータフォールの幻影」。

個人的にはアジャイル開発経験が無いので、なんとも言えない部分はあれど、ウォーターフォール開発が歴史の中で色々と言われ続けたのも納得ですし、アジャイル開発も正しいアジャイル開発をしないと結局は上手く行かない。というのも納得です。

これだけアジャイル、アジャイル言われ続けて、未だウォータフォール開発を行っている会社が多い理由を個人的に考えてみると、まだまだアジャイル開発経験のない会社が多く、その理由として、新しい開発プロセスに挑戦するのを恐れていたり、そもそも正しいアジャイル開発手法を知らない・わからない。だから、未だウォータフォール開発を行っている会社が多いんじゃないかなぁ。。。

うちの会社もだいたいそれだしなぁ。。。

「9-4 ウォータフォールの幻影」は個人的にとても興味深い話だったので、とても楽しく読むことができました。

さいごに

「ちょうぜつソフトウェア設計入門――PHPで理解するオブジェクト指向の活用」は、表紙かわいくて、内容も深く、ボリュームもたっぷりなので、めちゃおすすめです。🎉🎉🎉

設計技法「動的計画法」を学ぶ

最近はアルゴリズムを勉強している。

なかなか頭に入ってこないので、アウトプットをして整理する。

なお、今回は設計技法「動的計画法」の話。

動的計画法は、Dynamic Programming。よくDPと言われる。

DPを一言で説明することは難しい。。。らしく、抽象的な説明しかできない。

「与えられた問題全体を一連の部分的問題に分解し、各部分問題に対する解をメモ化しながら、小さな部分問題からより大きな部分問題へと順に解を求めていく手法」とのこと。

つまり、問題全体を見て解くのではなく、部分的問題に分解して問題を少しづづ解いていくような手法ということ。（たぶん）

動的計画法を用いれば、以下のような問題を解くことが可能とのこと。

• ナップサック問題
• スケジューリング問題
• 発電計画問題
• 編集距離（diffコマンド）
• 音声認識パターンマッチング問題
• 文章の分かち書き
• 隠れマルコフモデル

というわけで、ナップサック問題を考えてみる。

- ナップサック問題

N個の品物があり、i(=0,1,...N-1)番目の品物の重さは weight i, 価値は value jで与えられる。
このN個の品物から、重さの総和がWを超えないように、いくつか選ぶとする。選んだ品物の価値の総和として考えられる最大値を求めよ。（ただし、Wやweight iは0以上の整数とする）

動的計画法は、「部分的問題に分解して問題を少しづづ解いていくような手法」なので、どこが部分問題にできるのかを考える。

以下のような、ある程度の部分問題にすべきパターンがあるので、当てはめて考えてみる。

N個の対象物（0,1,2...,N-1）に関する問題に対して、最初のi個の対象物（0,1,2...i-1）に関する問題を部分問題として考える。

ナップザック問題に対して、上記パターンを当てはめると以下のようになる。

dp[i]（最初のi個）の品物（0,1,2...i-1）までの中から重さの総和がWを超えないように選んだ時の、価値の総和の最大値

しかし、これだと dp[i] から dp[i+1] をした時に、 i を選ぶか選ばないかの2通りの選択肢を検討することになるが、品物 i を加えることにしたときに、重さの合計がWを超えるかがわからない。

つまり、1次元配列では i を選ぶか選ばないかの2通り考える部分問題にならなくなり、詰まってしまう。

なので、以下のように変更する。

dp[i][j]（最初のi個）の品物（0,1,2...i-1）までの中から重さの総和がwを超えないように選んだ時の、価値の総和の最大値

これなら、2次元配列になり、重さと価値の表が完成する。

ためしに、 N=3, W=7 とする。値は {i, j} として、 {2, 9}, {5, 1}, {3, 10} とする。

一旦すべて i を選んでみると以下のような2次元配列が完成する。

//     0 1 2  3  4  5  6  7 ←W（w=0,1,2...W）
// 0 [0 0 0  0  0  0  0  0]
// 1 [0 0 9  9  9  9  9  9]
// 2 [0 0 9  9  9 10 10 10]
// 3 [0 0 9 19 19 20 20 20]
//  ↑N
// 

dp[0][j] の列は、何も品物を加えないということなので、すべての値が 0 となる。

dp[1][2] で価値 9 になったことがわかる。

dp[2][5] で価値 9 から 1 が加えられて 10 になったことがわかる。

dp[3][3] で価値 9 から 10 が加えられて 19 になったことがわかる。

その後、dp[3][5]で価値 19 から 1 が加えられて 20 になったことがわかる。

つまり、2次元配列になったことで、 i+1 される前の値は、 i からわかるような表になっていることがわかる。

これを整理すると、以下のようになる。

i番目の品物を選んだ後に {i+1, w} になるので、選ぶ前は {i, w-weight[i]} に価値（ value[i] ）を加算することでわかる。

つまり、i番目の品物を選ぶ場合は、 max(dp[i+1][w], dp[i][w - weight[i]) + value[i]) で最大値を更新。

i番目の品物を選ばないのであれば、 max(dp[i+1][w], dp[i][w]) で据え置く。

これをコードで書くと以下のようになる。

package main

import (
    "fmt"
)

// - ナップサック問題
// N個の品物があり、i(=0,1,...N-1)番目の品物の重さは weight i, 価値は value jで与えられる。
// このN個の品物から、重さの総和がWを超えないように、いくつか選ぶとする。選んだ品物の価値の総和として考えられる最大値を求めよ。（ただし、Wやweight iは0以上の整数とする）

func chmax(a *int, b int) {
    if *a < b {
        *a = b
    }
}

func main() {
    // 3 7
    // 2 9 { w, v }
    // 5 1
    // 3 10

    var N, W int
    fmt.Scanf("%d", &N)
    fmt.Scanf("%d", &W)

    weight := make([]int, N)
    value := make([]int, N)
    for i := 0; i < N; i++ {
        fmt.Scanf("%d %d", &weight[i], &value[i])
    }

    // [   0 1 2 3 4 5 6 7<=W
    // 0 [0 0 0 0 0 0 0 0]
    // 1 [0 0 0 0 0 0 0 0]
    // 2 [0 0 0 0 0 0 0 0]
    // 3 [0 0 0 0 0 0 0 0]
    //  N
    // ]

    var dp = make([][]int, N+1)
    for i := 0; i <= N; i++ {
        dp[i] = make([]int, W+1)
    }

    for i := 0; i < N; i++ {
        for w := 0; w <= W; w++ {
            // i 番目の品物を選ぶ場合
            if w-weight[i] >= 0 {
                chmax(&dp[i+1][w], dp[i][w-weight[i]]+value[i])
            }
            // i 番目の品物を選ばない場合
            chmax(&dp[i+1][w], dp[i][w])
        }
    }

    // [   0 1 2  3  4  5  6  7<=W
    // 0 [0 0 0  0  0  0  0  0]
    // 1 [0 0 9  9  9  9  9  9]
    // 2 [0 0 9  9  9  9  9 10]
    // 3 [0 0 9 10 10 19 19 19]
    //  N
    // ]

    fmt.Println("解答 =>", dp[N][W]) // 19
}

これで、ナップザック問題が解ける。

動的計画法は、むちゃくちゃ難しい。。。問題に対して、部分問題にどう落とし込むのか。が、かなり重要な気がした。

使いこなすまでに、相当な訓練が必要だと思う。

次は、二分探索法かな。。。

設計技法「再帰」を学ぶ

最近はアルゴリズムを勉強している。

なかなか頭に入ってこないので、アウトプットをして整理する。

なお、今回は設計技法「再帰」の話。

一連の処理の中で、自分自身を呼び出すことを「再帰呼び出し」と言う。

「再帰呼び出しを行う関数」のことを「再帰関数」と言う。

以下、1からNまでの総和を計算する再帰関数の例を書く。

package main

import (
    "fmt"
)

func recursive(N int) int {
    fmt.Printf("recursive(%d)を呼び出しました。\n", N)
    if N == 0 {
        return 0
    }
    result := N + recursive(N-1)
    fmt.Printf("%dまでの和 = %d\n", N, result)
    return result
}

func main() {
    recursive(5)
}

// recursive(5)を呼び出しました。
// recursive(4)を呼び出しました。
// recursive(3)を呼び出しました。
// recursive(2)を呼び出しました。
// recursive(1)を呼び出しました。
// recursive(0)を呼び出しました。
// 1までの和 = 1
// 2までの和 = 3
// 3までの和 = 6
// 4までの和 = 10
// 5までの和 = 15

再帰関数にはある程度テンプレートが決まっており、以下のようになる。

func 関数名 (引数) {
  if ベースケース {
    return ベースケースに対する値
  }
  // 再帰呼び出しを行う
  関数名(次の引数)
  return 答え
}

ここで、再帰関数を使ってフィボナッチ数列を求める再帰関数を考える。

• フィボナッチ数列とは？ ⇒ 「1,1,2,3,5,8,13,21,34,55…」と続く数列のことで、前2つの値を加算してできる数列のこと。

フィボナッチ数列の漸化式は以下になる。

• F0 = 0
• F1 = 1
• Fn = Fn-1 + Fn-2 (n=2,3,4…)

なお、漸化式とは、ある数列に対して規則性を表す等式のことを指す。

フィボナッチ数列の場合、F0 = 0、 F1 = 1の条件式が成り立つ場合、Fn = Fn-1 + Fn-2 (n=2,3,4…)という規則性があるということ。

package main

import (
    "fmt"
)

func fibo(N int) int {
    fmt.Printf("fibo(%d)を呼び出しました。\n", N)
    if N == 0 {
        return 0
    } else if N == 1 {
        return 1
    }

    result := fibo(N-1) + fibo(N-2)
    fmt.Printf("%d 項目 = %d\n", N, result)

    return result
}

func main() {
    fibo(5)
}

// fibo(5)を呼び出しました。
// fibo(4)を呼び出しました。
// fibo(3)を呼び出しました。
// fibo(2)を呼び出しました。
// fibo(1)を呼び出しました。
// fibo(0)を呼び出しました。
// 2 項目 = 1
// fibo(1)を呼び出しました。
// 3 項目 = 2
// fibo(2)を呼び出しました。
// fibo(1)を呼び出しました。
// fibo(0)を呼び出しました。
// 2 項目 = 1
// 4 項目 = 3
// fibo(3)を呼び出しました。
// fibo(2)を呼び出しました。
// fibo(1)を呼び出しました。
// fibo(0)を呼び出しました。
// 2 項目 = 1
// fibo(1)を呼び出しました。
// 3 項目 = 2
// 5 項目 = 5

このフィボナッチ数列のコードは、作成したものの「同じ計算を何度も実行していて効率が極めて悪い」という問題がある。

上記結果を見ても、 fibo(3) , fibo(2) , fibo(1) , fibo(0) を何度か呼び出しているのがわかる。

そもそもフィボナッチ数列は再帰関数を用いなければ、for文（計算量: O(N))でできる問題なので、再帰関数を用いると無駄な計算があることがわかる。

fibofor := [6]int{0, 1}
for n := 2; n < 6; n++ {
    fibofor[n] = fibofor[n-1] + fibofor[n-2]
    fmt.Printf("%d 項目 = %d\n", n, fibofor[n])
}

// 2 項目 = 1
// 3 項目 = 2
// 4 項目 = 3
// 5 項目 = 5

再帰関数で無駄な計算をさせない方法の1つがメモ化（キャッシュとも言う）。

つまり、1度計算した結果を変数に保存しておく方法。

func mfibo(n int, memo []int) int {
    fmt.Printf("func mfibo(%d) を呼びました\n", n)
    if memo[n] != -1 {
        fmt.Println("メモ化した値を返しました")
        return memo[n]
    }

    if n == 0 {
        memo[0] = 0
        return 0
    } else if n == 1 {
        memo[1] = 1
        return 1
    }

    memo[n] = mfibo(n-1, memo) + mfibo(n-2, memo)

    return memo[n]
}

func main() {
    // memo初期化
    memo := make([]int, 6)
    for i, _ := range memo {
        memo[i] = -1
    }

    mfibo(5, memo)
    fmt.Println("memo => ", memo)
}

// func mfibo(5) を呼びました
// func mfibo(4) を呼びました
// func mfibo(3) を呼びました
// func mfibo(2) を呼びました
// func mfibo(1) を呼びました
// func mfibo(0) を呼びました
// func mfibo(1) を呼びました
// メモ化した値を返しました
// func mfibo(2) を呼びました
// メモ化した値を返しました
// func mfibo(3) を呼びました
// メモ化した値を返しました
// memo =>  [0 1 1 2 3 5]

再帰関数は複雑なコードをシンプルに表現することができる手法。

しかし、無駄な計算量コストが増えてしまいがちなので、メモ化して無駄な計算コストを防ぐことが大事だということを学んだ。

アルゴリズムとは無関係の話だが、Go言語は再帰を使うと遅くなるらしい。。。

ymotongpoo.hatenablog.com

原因は、再帰関数の引数などを保管する「スタック領域」がGo言語はデフォルトが小さい、かつスタック領域の大きさを最小にするような最適化を行わないかららしい。。。

つまり、再帰呼び出しを行う度に一定量のスタック領域を食いつぶしていくイメージなのかな。。。

あと、再帰をつかったときの計算量がよくわからない。。。今後の課題である🤔

次は、「動的計画法」をやる。