あるエンジニアのAtCoder奮闘記

東京都港区にあるアミフィアブル株式会社のエンジニアが、AtCoderで解いた問題について振り返ったりしていく会社公認のブログです。

AtCoder ABC 126 F - XOR Matching (Go)

競プロ AtCoder ABC126 F問題 600点 Go

irisruneです。2本立てはタイトルも本文もごちゃごちゃするので1記事に1本がよさそうですね。

atcoder.jp

適当に試行すれば解法が出てくると聞いたのでやってみたらACできました。しかし出力時点でミスしてWAを積み重ねました。

package main

import (
    "fmt"
    "math"
    "strings"
)

func main() {
    var m, k int
    fmt.Scan(&m, &k)
    n := int(math.Pow(2.0, float64(m)))
    if n == 2 && k == 1 {
        fmt.Println(-1)
        return
    }
    if n <= k {
        fmt.Println(-1)
        return
    }

    ans := make([]int, 0)
    for i := 0; i < n; i++ {
        if i == k && k != 0 {
            continue
        }
        ans = append(ans, i)
    }
    if k != 0 {
        ans = append(ans, k)
    }

    for i := n - 1; i >= 0; i-- {
        if i == k && k != 0 {
            continue
        }
        ans = append(ans, i)
    }
    if k != 0 {
        ans = append(ans, k)
    }

    str := fmt.Sprintf("%v", ans)
    str = strings.Trim(str, "[]")
    fmt.Println(str)
}

解き方は大体解説の通りで、N\geq 2のとき、1 xor 2 xor ... xor 2^{N-1} = 0が成り立つことを用いれば条件を満たす数列を構築できます。

ただしN=1のときには先の等式は明らかに成り立たないので、

1 0

という入力に対し

1 0 1 0

などと出力してしまうとWAになってしまいます。その場合分けさえしておけば、記述が少し冗長になりがちな点を除いて躓くことはそれほどないと思います。

なお、1回のループで昇順の順列と降順の順列を同時に作って結合すると記述量が減ると思いますが、Go言語でやると降順の配列を作る処理で計算量がかかってしまいTLEしてしまいました。配列の先頭に要素を追加するときに配列長の計算量がかかるので厳しいですね。

雑記

  • 上記コードではやっていませんが、Go言語の入力処理のみを変えて過去に解いた問題を解き直してみました。

f:id:amifiable:20190522154228p:plain

f:id:amifiable:20190522154249p:plain

  • 格段に実行時間が短くなっていますね、入力がボトルネックになっていたのは確かなようです。
    • Juliaの立つ瀬がないですね…

AtCoder ABC 126 D - Even Relation / E - 1 or 2 失敗例と解き直し (Go)

競プロ AtCoder ABC126 D問題 E問題 400点 500点 Go

irisruneです。今回のコンテストは3完で冷えましたが…Unratedでしたね。

どちらもコンテスト中には解けなかったので解説ACです（正確にはE問題の解説を読んでD問題も解きました）。

ABC 126 D - Even Relation

atcoder.jp

O(N^2)のダイクストラ法で解けるような最短経路問題ばかりやってるとこういう時に躓きますね。まずは失敗例から。

package main

import (
    "fmt"
)

const INF = 10000000000

func main() {
    var n int
    fmt.Scan(&n)

    adj := make([][]int, n)
    dig := make([]int, n)
    visited := make([]bool, n)
    color := make([]int, n)
    dist := make([]int, n)
    queue := make([]int, n)
    for i := range adj {
        line := make([]int, n)
        for j := range line {
            line[j] = INF
        }
        adj[i] = line
        dig[i] = 0
        visited[i] = false
        color[i] = 0
        dist[i] = 0
        queue[i] = 0
    }

    for i := 0; i < n-1; i++ {
        var u, v, w int
        fmt.Scan(&u, &v, &w)
        adj[u-1][v-1] = w
        adj[v-1][u-1] = w
        dig[u-1]++
        dig[v-1]++
    }

    iQueue := -1
    for i := 0; i < n; i++ {
        if dig[i] > 1 {
            continue
        }
        visited[i] = true
        queue[0] = i
        iQueue++
        break
    }

    for iQueue < n-1 {
        iQueueNext := iQueue + 1
        u := queue[iQueue]
        for v, w := range adj[u] {
            if w < INF && !visited[v] {
                dist[v] = dist[u] + w
                if dist[v]%2 == 1 {
                    color[v] = 1
                }
                visited[v] = true
                iQueue++
                queue[iQueue] = v
            }
        }
        iQueue = iQueueNext
    }

    for _, c := range color {
        fmt.Println(c)
    }
}

解き方の大筋としては解説にある通り、適当な頂点からの距離が偶数の点と奇数の点で色分けすればいいです。ただ問題は距離を求めるアルゴリズムの実装ですね。

まず、木構造について葉になる点を基準点にしなければいけないという思い込みがあったために次数の算出と次数1の点の探査という無駄な処理を実装しています。 そして隣接行列を用いてしまっているので計算量メモリ共に無駄が多く、N=10^5の場合はMLEが出てしまいます。

さらにダイクストラ法を上手く適用できなさそうということに焦ってしまい、スタックではなくキューを使ってDFSを実装しようとしています。当然ながらWAは出ましたし、なんならREまで出てよくわからないことになっていました。

そんな散々な回でしたが、DFSをしっかり実装すれば問題なく解くことができました。また、隣接行列ではなく隣接リストを実装することでMLEも解決しています。

package main

import (
    "fmt"
)

type edge struct {
    tail   int
    weight int
}

func dfs(adj [][]edge, visited []bool, dist []int, color []int, v int) {
    for _, e := range adj[v] {
        if visited[e.tail] {
            continue
        }
        visited[e.tail] = true
        dist[e.tail] = dist[v] + e.weight
        if dist[e.tail]%2 == 1 {
            color[e.tail] = 1
        }
        dfs(adj, visited, dist, color, e.tail)
    }
}

func main() {
    var n int
    fmt.Scan(&n)

    adj := make([][]edge, n)
    visited := make([]bool, n)
    dist := make([]int, n)
    color := make([]int, n)
    for i := range adj {
        line := make([]edge, 0)
        adj[i] = line
    }

    for i := 0; i < n-1; i++ {
        var u, v, w int
        fmt.Scan(&u, &v, &w)
        adj[u-1] = append(adj[u-1], edge{v - 1, w})
        adj[v-1] = append(adj[v-1], edge{u - 1, w})
    }

    visited[0] = true
    dfs(adj, visited, dist, color, 0)

    for _, c := range color {
        fmt.Println(c)
    }
}

実行時間が1700ms余りとかなりギリギリなのでやはり入力を改善する必要はありそうです。

コードレビュー

  • 隣接リストに枝の終点と重みをセットで入れているが、この辺りもう少しよい書き方がある？
  • DFS関数の引数が多くてちょっとわかりにくい気もする。

E - 1 or 2

atcoder.jp

最終的にやること自体はD問題と変わりません、むしろD問題より実装は楽だと思います。まずは失敗例から。

package main

import (
    "fmt"
)

const INF = 10000000000

func main() {
    var n, m int
    fmt.Scan(&n, &m)
    adj := make([][]int, n)
    for i := range adj {
        line := make([]int, 0)
        adj[i] = line
    }
    dig := make([]int, n)
    for i := 0; i < m; i++ {
        var x, y, z int
        fmt.Scan(&x, &y, &z)
        adj[x-1] = append(adj[x-1], y-1)
        adj[y-1] = append(adj[y-1], x-1)
        dig[x-1]++
        dig[y-1]++
    }
    visited := make([]bool, n)

    ans := 0
    for i := 0; i < n; i++ {
        if !visited[i] {
            ans++
            visited[i] = true
        }
        for j := 0; j < dig[i]; j++ {
            visited[adj[i][j]] = true
        }
    }
    fmt.Println(ans)
}

とりあえずD問題の失敗例コードと比べると隣接行列を隣接リストに変えたりなど少し洗練されていますね。定数INFとかdig配列とか残骸が残っていますが。

解説にある通り、カード全体をグラフ、入力で与えられたカードの組を枝とみなして連結成分の個数を求めればよいです。そのためにDFSを使えばよいということに思い至らず探索アルゴリズムがうまく実装できていません。どこに問題があるか説明するために反例を挙げると、

4 2
1 4 1
3 4 1

が与えられた場合出力として3を返してしまいます（2が正解）。これはカードを単純に番号順に判定しているためで、3番目のカードについて連結成分に属していないという判定をしてしまい間違った結果になってしまいます。

そんなわけで、DFSで実装したコードがこちらです。

package main

import (
    "fmt"
)

func dfs(adj [][]int, visited []bool, u int) {
    for _, v := range adj[u] {
        if visited[v] {
            continue
        }
        visited[v] = true
        dfs(adj, visited, v)
    }
}

func main() {
    var n, m int
    fmt.Scan(&n, &m)
    adj := make([][]int, n)
    for i := range adj {
        line := make([]int, 0)
        adj[i] = line
    }
    for i := 0; i < m; i++ {
        var x, y, z int
        fmt.Scan(&x, &y, &z)
        adj[x-1] = append(adj[x-1], y-1)
        adj[y-1] = append(adj[y-1], x-1)
    }
    visited := make([]bool, n)

    ans := 0
    for i := 0; i < n; i++ {
        if visited[i] {
            continue
        }
        visited[i] = true
        ans++
        dfs(adj, visited, i)
    }
    fmt.Println(ans)
}

D問題のコピペのようですが実はこちらを先にACしました。

雑記

  • 本番中にダイクストラ法のGoライブラリについて調べたりしていましたが使い方もよくわからず活用できませんでしたね。
  • DFS実装はできたので進歩はしましたが本番中に思いつく所までいきたいですね。
  • 他の社員を交えてAtCoderの問題を解いたり対談したレポートを今週中に記事にする予定です。

AtCoder ABC 104 C - All Green を嘘解法で (Julia) （おまけ：ABC 116 D - Various Sushi をJuliaで書き直し）

競プロ AtCoder ABC104 ABC116 C問題 D問題 300点 400点 Julia

irisruneです。今回もJuliaで問題を解いてみました。おまけで以前Go言語で解いた問題も解き直して実行時間など比較しています。

ABC 104 C - All Green

atcoder.jp

当時2完で冷えた回ですが、今見ても300点にしては難しいと思います。なお嘘解法でゴリ押しです。

parseInt(x)=parse(Int,x)
parseMap(x::Array{SubString{String},1})=map(parseInt,x)

function iter(d::Int, pc::Array{Int, 2}, g::Int)
    if g <= 0 return(0) end
    ret = typemax(Int)
    for i in d:-1:1
        if pc[i,1]==0 continue end
        if g <= pc[i,1] * 100i
            ret = min(ret, ceil(Int, g / 100i))
        else
            pcNext = copy(pc)
            pcNext[i, 1] = 0
            ret = min(ret, pc[i,1] + iter(d, pcNext, g - ((100i * pc[i,1]) + pc[i,2])))
        end
    end
    return(ret)
end

function main()
    d, g = readline() |> split |> parseMap

    pc = zeros(Int, d, 2)
    for i in 1:d
        pc[i, 1], pc[i, 2] = readline() |> split |> parseMap
    end

    ans = iter(d, pc, g)
    println(ans)

end

main()

アルゴリズムとしては、スコアの高い問題セットから順番に見ていき、各問題セットについて解くと仮定した時の解くべき問題数を再帰で計算してその最小値を取るというものになります。

このアルゴリズムの問題として解く問題セットの組み合わせに重複が発生するため計算量がかなり大きいです。例を挙げると、

  • 最初に500点の問題セットを解き、再帰関数内で400点の問題セットを解く場合
  • 最初に400点の問題セットを解き、再帰関数内で500点の問題セットを解く場合

このように全完する問題セットの順列の総数分の重複が発生してしまっています。そのため計算量はO(2^D D^2)と想定解答より大きくなるはずです。

なお、再帰関数のパラメータとして既に見た問題セットを記録するようにしておけば想定解と同じ計算量になるとは思います…が残念ながら上手く実装できませんでした。

全体的な感想として、やはりビット全探索は使えるに越したことはなさそうですね。

コードレビュー

  • 再帰：Recursion　反復：Iteration
    • よくやらかします。

ABC 116 D - Various Sushi

atcoder.jp

以前Go言語で解いた記事はこちら。

ami-atcoder.hatenablog.com

こちらで書いたGoのコードをほぼそのままJuliaに移植してみました。

parseInt(x)=parse(Int,x)
parseMap(x::Array{SubString{String},1})=map(parseInt,x)

pointSum(pointD, typeNum) = pointD + (typeNum * typeNum)

function main()
    n, k = readline() |> split |> parseMap
    sushi = zeros(Int, n, 2)
    for i in 1:n
        sushi[i,2], sushi[i,1] = readline() |> split |> parseMap
        # 種類が後の方が都合がよいので
    end
    sushi = sortrows(sushi, rev=true)

    pointD = 0
    typeNum = 0
    types = zeros(Int, n)
    for i in 1:k
        pointD += sushi[i, 1]
        types[sushi[i, 2]] += 1
        if types[sushi[i, 2]] == 1
            typeNum += 1
        end
    end

    ans = pointSum(pointD, typeNum)

    iRemove = k
    iAdd = k + 1

    while typeNum < k
        while iRemove > 1
            if types[sushi[iRemove, 2]] > 1
                pointD -= sushi[iRemove, 1]
                types[sushi[iRemove, 2]] -= 1
                break
            end
            iRemove -= 1
        end
        if iRemove == 1 break end
        iRemove -= 1

        while iAdd <= n
            if types[sushi[iAdd, 2]] == 0
                pointD += sushi[iAdd, 1]
                types[sushi[iAdd, 2]] += 1
                typeNum += 1
                break
            end
            iAdd += 1
        end
        if iAdd > n break end
        iAdd += 1

        ans = max(ans, pointSum(pointD, typeNum))
    end
    println(ans)
end

main()

f:id:amifiable:20190517154257p:plain

画像のように、Goよりも少し速くなっています。もっともGoは入力部分を最適化していなくてJuliaは（多分）最適化しているという違いがありますが。

バイト数で見るとJuliaの方が少し多く、Goではソートに記述量を使っていることを考えるとGoの方が記述が簡潔と言えるかもしれません（Goの入力部分を最適化するのにも記述量は必要だと思いますが）。メモリ使用量は見なかったことにしましょう。

行列を行単位・列単位でソートできるという機能を活用したのでJuliaの良いところを少し出せたとは思いますが、やはり競プロ向きといった感じではなさそうな気もします。

なお、REを出しているのは手元のJulia1.1でsortrowsではなくsortslicesを使っていたためでした。一応スクリプト言語的な立ち位置なのでCEではないんですね…

雑記

  • AtomのJuliaプラグインで書いてみましたが、エディタ部分の動作は良好だと思いました。ただREPLに複数行入力できないのが厳しいですね（Julia実行環境自体がそういう仕様ですが）。
    • IntelliJのJuliaプラグインの場合は複数行入力の方法があるのでその点では分がありますね。エディタ部分の動作に難しかないのでそこさえ何とかなれば…

AtCoder ABC 100 C - *3 or /2 でJuliaを試してみる(Julia)

競プロ AtCoder ABC100 C問題 300点 Julia

irisruneです。久々に新しい言語に挑戦してみた回です。 前置きをしておくと、今回は問題の難易度はかなり低めで言語周りの話がメインです。

なお、こちらの記事に多大な影響を受けているためこの場を借りて紹介させていただきます。

qiita.com

そもそもJuliaとは

簡単に書くと、Pythonなどのように対話環境があってコードが試しやすく、LLVMを用いてコンパイルを行うため実行が高速で、科学計算向けに基本機能として行列計算などをサポートしている至れり尽くせりのような言語です。

また、PythonやC++などのコードを使うためのパッケージなども存在しているため、既存のモジュールなどを活用することができます。

Juliaと競プロ

上記リンク先記事を見れば大体わかります。

まず、AtCoderでJuliaを使うことはできますがバージョンが0.5です。（2019年5月15日現在Julia公開バージョンは1.1） 影響としては配列（行列）の累積計算を行うaccumulate関数が使えないことなどが挙げられます。 mathモジュールが使えないKotlinに比べれば影響は少ない…かも？

他の問題としては実行時間の計測方式の関係？で必ず数百ms以上はかかってしまったりメモリ使用量が100MB以上かかったりします。 前者は意外と問題になりにくいようですが後者は64MB制限の問題で致命的ですね…

そして、標準入力で顕著ですが関数の実行の仕方によって平気で実行時間が1000ms以上変わったりします。 色々試しましたがすべてのケースで実行時間の短くなる記法が見つかっていないので悩みどころですね…

また、最初のケースの実行時間が非常に不安定です。 色々な記法で実行時間の比較をしようと思っていましたがこれによるものがほとんどだったので没になりました。

問題

atcoder.jp

問題自体はそれほど難しくはありません。アルゴリズムを考えるのも実装するのも簡単だと思います。

アルゴリズム概説

入力された数列の要素それぞれについて、2で割れる回数を数えて合計すれば答えが出ます。

なお、要素をすべて掛け合わせてから2で割れる回数を求めても答えが出るはずです…が、相当大きな値になってしまうので実装は難しく、BigInt型を使っても上手くいかなかったです。

コードと考察

とりあえず最も実行時間の短かったコードだけを挙げます。

parseInt(x)=parse(Int,x)
parseMap(x::Array{SubString{String},1})=map(parseInt,x)

function main()
    n = parseInt(readline())
    a = parseMap(split(readline()))

    ans = 0
    for i in 1:n
        while mod(a[i],2) == 0
            a[i] /= 2
            ans += 1
        end
    end

    println(ans)
end

main()

f:id:amifiable:20190515160737p:plain

入力をオーソドックスに関数化し、それ以外はそのまま記述しました。 関数化部分を増やしても全体の実行時間はあまり変わらず、最初のケースで時間がかかりがちだったので良い結果は出せませんでした。

ある程度わかったこととしては、

  • 入力部分はparse関数とmap関数を関数化した方が速い。
  • 入力以外の部分では関数化しないよりする方が早くなるとは限らない。
    • 逆に、関数化によりそれほど遅くなることも（最初のケース以外では）ないので関数呼び出しのオーバーヘッドを気にする必要もなさそう。
    • 最初のケースは関数を増やすと遅くなりがちだが提出の度に実行時間が変わったりしてよくわからなかった。
  • 全てのケースにおける実行時間の幅が6ms程度のため処理速度自体はそれほど悪くはないように感じる。
    • python3のfastest codeと（振れ幅が）同等というのを速いとみるか遅いとみるか。
      • 速いコードは基本的にビット演算を使っている（アルゴリズムレベルで違う）ので比較対象として不適当かもしれない。

雑記

  • IntelliJのJuliaプラグインを使ってみましたが、エディタ部分がやたら使いにくく感じたのでAtomプラグインも試してみたいと思います。
  • 複数行入力をする手段があればJupyterを使ってもよいのですが…textareaを標準入力にする手段があれば知りたいですね。

diverta 2019 Programming Contest C - AB Substrings / D - DivRem Number 失敗例と嘘解法(Go)

競プロ AtCoder diverta 2019 Programming Contest C問題 D問題 400点 500点 Go

irisruneです。久々にコンテストに参加したらUnratedになったなんとも言い難いお話。

C - AB Substrings

atcoder.jp

全探索は（O(N!)かかるため）できないとして、計算で求めるための場合分けが難しかったです。まずは失敗例を。

package main

import "fmt"

func minInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
    var n int
    fmt.Scan(&n)
    sArr := make([]string, n)
    for i := range sArr {
        fmt.Scan(&sArr[i])
    }

    cntA, cntB, cntAB := 0, 0, 0
    for _, s := range sArr {
        if s[0:1] == "B" {
            cntB++
        }
        for i := 0; i < len(s)-1; i++ {
            if s[i:i+2] == "AB" {
                cntAB++
            }
        }
        if s[len(s)-1:len(s)] == "A" {
            cntA++
        }
    }

    fmt.Println(cntAB + minInt(n-1, minInt(cntA, cntB)))
}

見ればわかるかもしれませんが、Bで始まってAで終わる文字列の数というものをカウントしていません。 すべての文字列がBで始まってAで終わる場合はN-1（と文字列中の"AB"の数の和）を返すようにしていましたがそれでは不十分でしたね。

解説読んだ後ですら3WAしましたが解説ACしたコードがこちらになります。

package main

import "fmt"

func minInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    var n int
    fmt.Scan(&n)
    sArr := make([]string, n)
    for i := range sArr {
        fmt.Scan(&sArr[i])
    }

    cntBtoA, cntToA, cntBto, cntAB := 0, 0, 0, 0
    for _, s := range sArr {
        switch {
        case s[0:1] == "B" && s[len(s)-1:len(s)] == "A":
            cntBtoA++
        case s[0:1] == "B":
            cntBto++
        case s[len(s)-1:len(s)] == "A":
            cntToA++
        }
        for i := 0; i < len(s)-1; i++ {
            if s[i:i+2] == "AB" {
                cntAB++
            }
        }
    }

    var ans int
    switch {
    case cntToA+cntBto == 0:
        ans = cntAB + maxInt(0, cntBtoA-1)
    default:
        ans = cntAB + cntBtoA + minInt(cntToA, cntBto)
    }
    fmt.Println(ans)
}

思いの外場合分けがややこしくて解説ACするのも少し苦労しました。

コードレビュー - C

  • Bで始まる文字列、Aで終わる文字列、Bで始まってAで終わる文字列それぞれの数をカウントする変数の名前をもう少しうまく付けたい。

D - DivRem Number

atcoder.jp

最初の方針から嘘解法でそのまま貫き通してしまった感じです。こちらも失敗例から。

package main

import (
    "fmt"
)

func minInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
    var n int
    fmt.Scan(&n)

    ans := 0
    for i := 1; i*i < n; i++ {
        if (n-i)%i == 0 {
            ans += (n - i) / i
        }
    }
    fmt.Println(ans)
}

少し解説をすると、m\leq\sqrt NのときはNをmで割った商がmより小さくなることはなく、 一方であまりはmより必ず小さくなるためお気に入りの数になることはありません。 そのためお気に入りの数はm>\sqrt Nに絞り込むことができますが、このままでは計算量は全探索とあまり変わりません（O(N-\sqrt N)=O(N)のため）。 しかしm>\sqrt Nのとき商は必ず\sqrt Nより小さくなるので商に対して全探索をかけることでお気に入りの数を列挙することができます。 あとはNから商の候補である値を引いた数がその値で割り切れれば、割った後の数がお気に入りの数になります。

…と言いたいところですが、例えばN=6に対して商を2とおいてしまうとお気に入りの数としてm=2が求められてしまいこれは明らかに題意を満たしません。要するに商の候補である値がNそのものの約数である場合お気に入りの数を誤判定してしまいます。

そんなわけで、判定部分を問題文により忠実にしたのが以下のコードになります。

package main

import (
    "fmt"
)

func main() {
    var n int
    fmt.Scan(&n)

    ans := 0
    for i := 1; i*i < n; i++ {
        if (n-i)%i == 0 {
            div := (n - i) / i
            if n/div == n%div {
                ans += div
            }
        }
    }
    fmt.Println(ans)
}

判定部分は少しだけ複雑になりましたが、関数minIntが不要になったためコード長自体は短くなりました。初めから不要でしたね。

コードレビュー - D

  • お気に入りの数（の候補）として変数divを使っているが、mにした方がより明確。

雑記

  • 想定パフォは1224でレートは1上昇だったらしいです。Ratedでもあまり変わりませんでしたね。
    • Cが解けていれば時間によっては青パフォどころか黄パフォがあり得たと考えるとUnratedとはいえ少し悔しいですね。

ARC 042 C - おやつ

競プロ AtCoder ARC042 A問題 100点 Go

irisruneです。今回も忙しいので過去に解いた問題の解説になります。

atcoder.jp

ナップサック問題の亜種なので簡単…ということはなく少し頭を使う必要がありそうです。

package main

import (
    "fmt"
    "sort"
)

const INF = 1000000000

func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

type Snack struct {
    a int
    b int
}

type Snacks []Snack

func (s Snacks) Len() int {
    return len(s)
}

func (s Snacks) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

func (s Snacks) Less(i, j int) bool {
    return s[i].a < s[j].a
}

func main() {
    var n, p int
    fmt.Scan(&n, &p)

    var snacks Snacks = make([]Snack, n)
    for i := range snacks {
        fmt.Scan(&snacks[i].a, &snacks[i].b)
    }
    sort.Sort(snacks)

    ansLine := make([]int, p+1)
    for i := range ansLine {
        switch i {
        case 0:
            ansLine[i] = 0
        default:
            ansLine[i] = -INF
        }
    }

    for _, s := range snacks {
        for i := p; i >= s.a; i-- {
            ansLine[i] = maxInt(ansLine[i], ansLine[i-s.a]+s.b)
        }
        ansLine[0] = maxInt(ansLine[0], s.b)
    }

    ans := 0
    for _, a := range ansLine {
        ans = maxInt(ans, a)
    }
    fmt.Println(ans)
}

公式解説の解法は（部分点解法はともかく）よくわからないのでいわゆる天才解法だと自分は思いました。

自分の解法を説明すると、

  1. おやつを値段でソートする。
  2. 値段が安いおやつから選んで普通にナップサック問題を解く。
  3. 値段が0の場合の満足度を今まで選んだおやつの満足度の最大値にする。

という流れになります。ポイントは3.で、最終的に選ぶおやつの中から一番値段の安いおやつの値段を0円とみなす、というアルゴリズムを実現しています。これは、

  • 値段を0円とみなすおやつは、それより値段の安い（あるいは同じ）おやつより満足度が高い（あるいは同じ）。
  • 値段を0円とみなすおやつより値段の高い（あるいは同じ）おやつについてのみナップサック問題（動的計画法）のアルゴリズムを適用する。

以上2点を満たすことにより実現できることが言えます。よって問題を解くことができました。

…実際は解いた当時も試行錯誤して完成したコードで、割と解説に困ってるのが見て取れると思います。書いた後で解説記事があるのを見つけたので読んでみましたが、公式解説の解法をわかりやすく説明されていると思いました。

雑記

  • 割とJuliaでAtCoderやるのも何とかなりそうな気がしたので来週のどこかで扱うかもしれません。

ABC 012 D - バスと避けられない運命(Go)

競プロ AtCoder ABC012 D問題 100点 Go Julia

irisruneです。GW中はJuliaについて色々調べたりしていました、その辺の諸々は雑記に。

atcoder.jp

少し忙しいので解説が難しくない問題を選びました。GW前の記事とジャンルが一緒ですね。

package main

import (
    "fmt"
)

const INF = 1000000000

func minInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func dijkstra(adj [][]int, s int, n int) {
    dist := make([]int, n)
    for i := range dist {
        switch {
        case i == s:
            dist[i] = 0
        default:
            dist[i] = INF
        }
    }
    visited := make([]bool, n)
    visited[s] = true

    base := s
    for {
        next := -1
        minD := INF
        for i := range dist {
            if visited[i] {
                continue
            }
            dist[i] = minInt(dist[i], dist[base]+adj[base][i])
            if dist[i] < minD {
                next = i
                minD = dist[i]
            }
        }
        if next == -1 {
            break
        }
        base = next
        visited[next] = true
    }
    for i, d := range dist {
        adj[s][i] = d
        adj[i][s] = d
    }
}

func main() {
    var n, m int
    fmt.Scan(&n, &m)

    adj := make([][]int, n)
    for i := range adj {
        line := make([]int, n)
        for j := range line {
            switch {
            case i == j:
                line[j] = 0
            default:
                line[j] = INF
            }
        }
        adj[i] = line
    }

    for i := 0; i < m; i++ {
        var a, b, t int
        fmt.Scan(&a, &b, &t)
        adj[a-1][b-1] = t
        adj[b-1][a-1] = t
    }

    for i := 0; i < n; i++ {
        dijkstra(adj, i, n)
    }

    ans := INF
    for i := 0; i < n; i++ {
        maxD := 0
        for j := 0; j < n; j++ {
            maxD = maxInt(maxD, adj[i][j])
        }
        ans = minInt(ans, maxD)
    }
    fmt.Println(ans)
}

制約条件が非常に緩いため、実装自体はダイクストラ法を知っていれば難しくないと思います。どちらかといえば国語の問題と言えそうなくらいに問題文がややこしく、

高橋君は、バスに乗っている時間が最も長くなってしまうような、最悪のケースを常に想定します。 この、最悪なケースのバスに乗っている時間が、出来るだけ短くなるような場所に引っ越そうと思っています。

追記：なお、最悪のケースとは、バスに乗る時間の合計が最も短くなるように、乗るバスを選択した時に、最もバスに乗る時間の合計が長くなってしまうような位置に会社があるケースのことを指します。また、自宅から会社に行く際に、高橋君が乗るバスを選ぶことができ、高橋君はバスに乗る時間の合計が最も短い経路を選択するものとします。

このような文となっており、何を求めればよいかがよくわからなくなりがちです。 これは問題文を逆に辿っていけば多少わかりやすくなり、

  • 高橋君はバスに乗る時間の合計が最も短い経路を選択する→最短経路を求める
    • バスに乗る時間の合計が最も短くなるように→同上
  • 最もバスに乗る時間の合計が長くなってしまう→最短経路の最大値（ある地点から最も遠い場所までの最短経路）を求める
  • 最悪のケースのバスに乗っている時間が、できるだけ短くなるような場所→最短経路の最大値が最小になる出発点を求める

といった形でそれぞれのバス停を始点としたときの最短経路をダイクストラ法で求めればよいことがわかります。

なお、隣接行列を用いるとO(N^3)時間かかりますが、優先度付きキューを用いると計算量を減らすことができそうです。制約条件が2\leq N\leq 300なのでどちらにせよ問題なく間に合いますが。

コードレビュー

  • 計算結果を記録する（2次元）配列を用意するのが面倒だったため隣接行列に計算結果を記録しているが、少しわかりにくくなっていると思われる。
    • 計算量の削減になるかという思いもあったが、おそらく変わらないと思われる。

雑記

  • 機械学習に使えそうな言語として割と新しい言語であるJuliaに目を付けて文法や特徴など調べていました。結論としては今は使う理由がなさそうという残念な結果でした。
    • 競プロに使うという点では、実行時間にコンパイル時間が含まれるなどの理由で不利がついてしまう。
      • TLEしない程度の差なら使えないこともない…？
    • また、VSCodeのJuliaプラグインがあまり高性能ではなくテスト実行などが上手くできなかった。
      • Atomプラグインについては試していないのでそちらなら上手くいくかもしれない。
    • Kaggle（機械学習）に使うという面では、（ある程度以上の計算を行うなら）実行速度が速いらしいこと、PycallでPythonのライブラリを呼び出せることなどからソロでやるならば使い勝手は悪くなさそう。
      • KaggleのカーネルでJuliaがサポートされていないので自前の環境でなんとかする必要がある。
        • Google ColabでJuliaが使えたりするらしいので意外とどうにかなりそう。
        • カーネルのみ使用可能なコンペもあるようなのでその場合当然使えない。
      • チームでやる場合どうしてもPythonに比べてマイナーな言語なので問題が出ると思う。
        • 学習コストは高くなさそうなので頑張って布教すればチームでJuliaを使うことも可能…？

ARC 008 C - THE☆たこ焼き祭り2012(Go)

競プロ AtCoder ARC008 C問題 100点 Go

irisruneです。明日からGWです、休みの人もそうでない人も充実した10日間を過ごせればよいですね。

atcoder.jp

なんと6年以上前の問題です。タイトルから問題文まで突っ込みどころが多すぎますが、推定難易度532点相当らしいです。

package main

import (
    "fmt"
    "math"
    "sort"
)

const INF = 1000000000.0

type person struct {
    x float64
    y float64
    t float64
    r float64
}

func time(thrower, receiver person) float64 {
    d := math.Sqrt(math.Pow((thrower.x-receiver.x), 2.0) + math.Pow((thrower.y-receiver.y), 2.0))
    v := math.Min(thrower.t, receiver.r)
    return d / v
}

func dijkstra(adj [][]float64, dt []float64, n int) {
    visited := make([]bool, n)
    s := 0
    dt[s] = 0.0
    visited[s] = true
    for {
        for i, v := range visited {
            if v {
                continue
            }
            dt[i] = math.Min(dt[i], dt[s]+adj[s][i])
        }

        next := -1
        minT := INF
        for i, v := range visited {
            if v {
                continue
            }
            if dt[i] < minT {
                next = i
                minT = dt[i]
            }
        }

        if next == -1 {
            break
        }
        visited[s] = true
        s = next
    }
}

func main() {
    var n int
    fmt.Scan(&n)
    people := make([]person, n)
    for i := range people {
        fmt.Scan(&people[i].x, &people[i].y, &people[i].t, &people[i].r)
    }

    adj := make([][]float64, n)
    for i := range adj {
        adj[i] = make([]float64, n)
    }

    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            adj[i][j] = time(people[i], people[j])
        }
    }

    dt := make([]float64, n)
    for i := range dt {
        dt[i] = INF
    }
    dijkstra(adj, dt, n)

    sort.Sort(sort.Reverse(sort.Float64Slice(dt)))
    maxT := 0.0
    for i, t := range dt {
        if i == n-1 {
            break
        }
        maxT = math.Max(maxT, t+float64(i))
    }
    fmt.Println(maxT)
}

問題文や制約は少し長いですが解き方は単純で、

  1. たこ焼きを投げる人と受け取る人のペアすべてについて、たこ焼きを投げるのにかかる時間を求める。
  2. 『あなた』から他の参加者すべてに対して、（他の参加者を経由して）たこ焼きを投げるのにかかる時間を求める。
  3. 2.の結果を降順にソートする。
  4. 3.についてたこ焼きを投げるのにかかる時間が長い人から順番にたこやきを投げるシミュレーションを行う。

つまり（有向）グラフの最短経路問題に集約されます。同じ人はたこ焼きを1秒に1個しか投げられないという条件はありますが、『あなた』からある参加者にたこ焼きを投げるのにかかる時間は（最短経路を使う限り）常に一定のため、この条件は『あなた』についてのみ考えればよいです。

計算量についてですが、今回のグラフは有向多重完全グラフとでもいうべき代物なので（有向）辺の本数がN(N-1)本にも及びます。そのためダイクストラ法などで最短経路を求めるのにO(N^2)時間かかってしまいます。そもそも（有向）辺の長さを求める（隣接行列を作成する）時点でO(N^2)時間かかるとは思いますが…

間違っても最短経路の最大値をそのまま解としてはいけません（親切にも入力例1が反例となっています）。

コードレビュー

  • ダイクストラ法のループ回数はN-1で決まっているはずなので無限ループを使うのはあまりよくないと思う。
    • この書き方すると割とよくbreak忘れます。
    • アルゴリズムだけ覚えて自己流でコード書いてるので他の人の実装を参考にしてもよさそうですね。
  • 『あなた』から他の参加者にたこ焼きを投げるシミュレーションを行う部分で『あなた』自身へ投げる手順を除外する処理について。
    • 末尾要素をスキップするためだけに毎回条件分岐をかけるのはあまりよくはないですね。
      • rangeを使わずにループ幅を決める
      • ループの前に末尾要素（『あなた』自身へ投げる時間）を除外する
        • Goのスライスを使っているので計算コストもかからないしこっちの方がわかりやすいですね。

雑記

  • GW中はブログの更新を停止します。
  • GW中は螺旋本や蟻本辺りをやるかRustをやるかKaggleに取り組んでみるか考え中です。

ARC 048 B - AtCoderでじゃんけんを (Go)

競プロ AtCoder ARC048 B問題 100点 Go

irisruneです。本田圭佑選手とゲーセンのじゃんけんゲームはどっちの方が強いんでしょうかと思いました。

atcoder.jp

多分アルゴリズムを考えること自体はそこまで難しくはないと思うのですが、実装はやや重いと思います。

package main

import (
    "fmt"
    "sort"
)

type Person struct {
    i    int
    rate int
    hand int
    win  int
    lose int
    draw int
}

type People []Person

func (p People) Len() int {
    return len(p)
}

func (p People) Swap(i, j int) {
    p[i], p[j] = p[j], p[i]
}

type ByRateHandI struct {
    People
}

func (b ByRateHandI) Less(i, j int) bool {
    if b.People[i].rate != b.People[j].rate {
        return b.People[i].rate < b.People[j].rate
    }
    if b.People[i].hand != b.People[j].hand {
        return b.People[i].hand < b.People[j].hand
    }
    return b.People[i].i < b.People[i].i
}

type ByI struct {
    People
}

func (b ByI) Less(i, j int) bool {
    return b.People[i].i < b.People[j].i
}

type Group struct {
    cumSum int
    hand1  int
    hand2  int
    hand3  int
}

func main() {
    var n int
    fmt.Scan(&n)

    var people People = make([]Person, n)
    for i := range people {
        fmt.Scan(&people[i].rate, &people[i].hand)
        people[i].i = i
        people[i].win, people[i].lose, people[i].draw = 0, 0, 0
    }

    sort.Sort(ByRateHandI{people})

    groups := []Group{}
    group := Group{0, 0, 0, 0}
    rateNow := 0
    for i, p := range people {
        if p.rate != rateNow {
            group.cumSum = i
            groups = append(groups, group)
            group.hand1, group.hand2, group.hand3 = 0, 0, 0
            rateNow = p.rate
        }
        switch p.hand {
        case 1:
            group.hand1++
        case 2:
            group.hand2++
        default:
            group.hand3++
        }
    }
    group.cumSum = n
    groups = append(groups, group)

    iGroup := 0
    for i, p := range people {
        if i >= groups[iGroup].cumSum {
            iGroup++
        }
        people[i].win += groups[iGroup-1].cumSum
        people[i].lose += n - groups[iGroup].cumSum

        switch p.hand {
        case 1:
            people[i].win += groups[iGroup].hand2
            people[i].lose += groups[iGroup].hand3
            people[i].draw += groups[iGroup].hand1 - 1
        case 2:
            people[i].win += groups[iGroup].hand3
            people[i].lose += groups[iGroup].hand1
            people[i].draw += groups[iGroup].hand2 - 1
        default:
            people[i].win += groups[iGroup].hand1
            people[i].lose += groups[iGroup].hand2
            people[i].draw += groups[iGroup].hand3 - 1
        }
    }
    sort.Sort(ByI{people})
    for _, p := range people {
        fmt.Println(p.win, p.lose, p.draw)
    }
}

とりあえず解き方の大筋を。

  1. 元の並び順を保持しながら参加者をレートでソートする（今回は昇順）。
  2. 参加者が1名以上該当するレート毎に、合計人数の累積和とグー/チョキ/パーそれぞれの人数（累積和ではない）を記録する。
  3. 2.の情報を用いて各参加者毎に対戦結果を計算する。
  4. 参加者を元の並び順でソートし直して出力する。

まず、1.と4.でソートを2回行う必要がある関係で、ただでさえ煩わしいGoのソートなのにソート処理だけでそれなりの行数使っています。1.のソートでレート以外の要素も使ったからというのはあるのですが。

そしてこの問題の一番の肝になると思われる2.の部分についてですが、参加者をレート毎にグループ化することでレートでの勝敗と手での勝敗をそれぞれ計算するための情報を記録しています。まずレートのグループ毎に人数の累積和を取ることによってレートでの勝敗結果が線形時間で計算できます。一方グループ内のグー/チョキ/パーそれぞれの人数を記録しておくことで手での勝敗結果も線形時間で計算できます。

以上のアルゴリズムで問題を解いたわけですが、ソートを行っているため計算量はO(N\log N)と解説より多めにかかってしまっています。制約条件が1\leq N \leq 10^5なので遅い言語だと少し最適化が必要かもしれませんね。参加者1人なんてケースあったの今気付いたんですが大会とは一体。

コードレビュー（と見せかけたアルゴリズム面のレビュー）

  • 上でも少し触れたが、1.でのソート対象はレートだけでよい（Goのパッケージは不安定ソートだが今回影響はないため）。
  • 累積和と言いつつ実は求め方が累積和ではない。
  • グループの配列を作成する部分や参加者毎の勝敗情報を計算する部分の処理がやや煩雑でわかりにくい。

雑記

  • 昔のコンテストの問題で配点が大体100点だったりするのはまだいいのですが、101点の問題はAC難易度かなり高くてつらいですね。
  • 社内でRustが話題に出てたので軽く調べましたが入出力が既によくわからないですね…OCaml触ったことはあるのですが。
  • 俺の勝ち！とかどこかでねじ込もうかと思ったけど流石にはっちゃけすぎだと思ったのでやめました。

Tenka1 Programmer Contest 2019 C - Stones をGoで解こうとしたら罠にハマりました (Go,Kotlin)

競プロ AtCoder Tenka1 Programmer Contest 2019 300点 Go Kotlin

irisruneです。最近コンテスト時間に予定が被ってて参加できないのがよくないですね。

atcoder.jp

アルゴリズム面は結論から言えば累積和を使いました。それで解けるはずだったんですけどね…

package main

import (
    "fmt"
)

func minInt(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

func main() {
    var n int
    var s string
    fmt.Scan(&n, &s)

    cumSum := make([]int, n+1)
    cumSum[0] = 0
    for i := 0; i < n; i++ {
        if []rune(s)[i] == '#' {
            cumSum[i+1] = cumSum[i] + 1
        } else {
            cumSum[i+1] = cumSum[i]
        }
    }

    minAns := n
    for i := 0; i <= n; i++ {
        ans := cumSum[i] + ((n - i) - (cumSum[n] - cumSum[i]))
        minAns = minInt(minAns, ans)
    }
    fmt.Println(minAns)
}

解き方の大筋は大体解説の通りです。

  1. 最終形として左から白い石が連続し、残りが黒い石であればよい。
  2. 最終形として考えられるのは高々N+1通りである。
  3. それぞれについて色を変える石の数を求めればよい。
  4. 最終形の白い石と黒い石の境目（端の場合もある）の左右について白い石と黒い石の個数がわかれば3.を求められる。
  5. 4.は黒い石の数について累積和を用いることで求められる。

といった形で解くことができます。計算量もO(N)で問題ないはずなのでジャッジにかけてみましょう。

f:id:amifiable:20190422112752p:plain

f:id:amifiable:20190422112806p:plain

どうして…

仕方ないのでKotlinで書いたほぼ同じプログラムがこちらになります。

fun main(args: Array<String>){
    val n = readLine()!!.toInt()
    val s = readLine()!!

    val lCumSum = mutableListOf(0)
    for(i in 1..n) {
        lCumSum.add(lCumSum[i - 1] + if(s[i-1] == '#') 1 else 0)
    }

    var minAns = n
    for(i in 0..n) {
        val ans = lCumSum[i] + ((n - i) - (lCumSum[n] - lCumSum[i]))
        minAns = listOf(minAns, ans).min()!!
    }
    println(minAns)
}

GoのコードとKotlinのコードの相違点は

  • Goは文字列をrune配列にキャストしてから文字比較をしている。
  • Kotlinは累積和を求める際にリストに要素を順番に追加している。

このくらいしかなく、入力も2つしかないのでそこで差が付くとも考えられないですね。

ということは文字列をrune配列にキャストする操作が計算量大きいんでしょうか。そう思って急遽書き直してみました。

package main

import (
    "fmt"
)

func minInt(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

func main() {
    var n int
    var s string
    fmt.Scan(&n, &s)

    cumSum := make([]int, n+1)
    cumSum[0] = 0
    for i := 0; i < n; i++ {
        if s[i:i+1] == "#" {
            cumSum[i+1] = cumSum[i] + 1
        } else {
            cumSum[i+1] = cumSum[i]
        }
    }

    minAns := n
    for i := 0; i <= n; i++ {
        ans := cumSum[i] + ((n - i) - (cumSum[n] - cumSum[i]))
        minAns = minInt(minAns, ans)
    }
    fmt.Println(minAns)
}

f:id:amifiable:20190422112826p:plain

問題なく通りましたね。やはり長い文字列をrune配列にキャストすると計算量が増大するようです。 軽く調べた感じその辺に言及してるサイトとかは見つかりませんでした。

1文字だけ見るのに毎回部分文字列を使うのは不格好なので避けたかったのですが、こんな罠があるなら仕方ないようですね…

と思いましたが、他の人の提出を見たところfor rangeで回すと計算量かからずにrune単位で処理できるようです。 考えてみれば当然なんですが、長さNの文字列を[]runeに変換するのに計算量O(N)かかるのでループ毎にキャストしてたらO(N^2)になってしまうんですよね。

なのでfor rangeで回すのが一番スッキリしていて、それでうまくいかないケースではループの外でキャストしておけばよいという感じですね。

  • 定数倍最適化するなら部分文字列を使った方がいいかも？

雑記

  • ABC/ARC相当と言われていたコンテストのD問題に600点って見えるのですが集団幻覚でも見てるのでしょうか。
    • Beginnerの方、4完4人って大惨事では？

ABC 116 D - Various Sushi (Go)

競プロ ABC116 AtCoder D問題 400点 Go

irisruneです。回転寿司なんかに行くとできるだけ多くの種類のネタを食べる派です。

atcoder.jp

多分実装が難しい部類の問題じゃないでしょうか。結構ゴリゴリ書いたので長めです。

package main

import (
    "fmt"
    "sort"
)

type susi struct {
    t int
    d int
}

type sushi []susi

func (s sushi) Len() int {
    return len(s)
}

func (s sushi) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

func (s sushi) Less(i, j int) bool {
    return s[i].d < s[j].d
}

func maxInt(a, b int) int {
    switch {
    case a > b:
        return a
    default:
        return b
    }
}

func main() {
    var n, k int
    fmt.Scan(&n, &k)

    var sushi sushi = make([]susi, n)
    for i := range sushi {
        fmt.Scan(&sushi[i].t, &sushi[i].d)
    }
    sort.Sort(sort.Reverse(sushi))

    pointD := 0
    typeNum := 0
    types := make([]int, n+1)
    for i := 0; i < k; i++ {
        pointD += sushi[i].d
        types[sushi[i].t]++
        if types[sushi[i].t] == 1 {
            typeNum++
        }
    }
    pointSum := pointD + (typeNum * typeNum)

    iRemove := k - 1
    iAdd := k
    for typeNum < k {
        for ; iRemove > 0; iRemove-- {
            if types[sushi[iRemove].t] > 1 {
                pointD -= sushi[iRemove].d
                types[sushi[iRemove].t]--
                break
            }
        }
        if iRemove == 0 {
            break
        }
        iRemove--

        for ; iAdd < n; iAdd++ {
            if types[sushi[iAdd].t] == 0 {
                pointD += sushi[iAdd].d
                types[sushi[iAdd].t]++
                typeNum++
                break
            }
        }
        if iAdd == n {
            break
        }
        iAdd++

        pointSum = maxInt(pointSum, pointD+(typeNum*typeNum))
    }
    fmt.Println(pointSum)
}

今回は構造体の配列とそのソートまで実装して解いてみました。配列を作ることすらままなかった頃に比べると色々できるようになってきたと思います。

アルゴリズムの大筋は解説の通りなのですが、このコードの特徴は優先度付きキューなどを用いていないところです。 そのためどのようにして解いているかというと、

  • i=1,2,...,nについてネタt_iを食べた数を記録しておく。
  • おいしさの総和とネタの種類数を求めておく。
  • N個の寿司をおいしさで降順ソートしておき、取り除く寿司を探索するインデックスを記録しておく。
    • さらに、追加する寿司を探索するインデックスも記録しておく。
  • 記録したインデックスを用いて食べる寿司を入れ替える操作を行い、おいしさの総和とネタの種類数を更新する。

ポイントは、食べた寿司そのものを記録するのではなく、おいしさの総和とそれぞれのネタを食べた数を記録しておくことです。 これにより、全体の計算量は優先度付きキューを用いた場合よりさらに少ないO(N)になる…はずです、多分。

コードレビュー

  • ほとんどの処理を関数に退避していないのでmain関数が肥大化している。
    • ループ部分と独立して最初においしい寿司だけを食べる部分もあるのでさらに肥大化している。
  • 計算量削減のための変数iRemove,iAddの扱いが特殊でわかりにくい。
  • sushiに複数形がないから構造体susiの配列としてsushiを定義するというよくわからないことになっている。

雑記

  • 1114msかかってるのは多分入力のせいだと思うのでそろそろfmt.Scan以外も使えるようにしておきたいですね。

square869120Contest #6 C Infinite Grid ※嘘解法/バグありAC (Go)

競プロ AtCoder square869120Contest #6 400点 Go

irisruneです。400点問題は解けましたが記事執筆中にバグに気付きました、最後に書くので考えてみてください。

atcoder.jp

10^9個ではなく数百個くらいでも変わらないかな？とは思っていましたが、それを解法に結び付けるには至りませんでした。結構強引に解こうとしたのでコードは長いです。

package main

import (
    "fmt"
)

func searchRoute(board []string, boardRoute [][][]bool, h int, w int) {
    for i := h - 1; i >= 0; i-- {
        for j := w - 1; j >= 0; j-- {
            if j == w-1 {
                for k := 0; k < h; k++ {
                    if k > i {
                        boardRoute[i][j][k] = ([]rune(board[i])[j] == '.') && boardRoute[i+1][j][k]
                    } else if k == i {
                        boardRoute[i][j][k] = ([]rune(board[i])[j] == '.')
                    } else {
                        boardRoute[i][j][k] = false
                    }
                }
            } else {
                if i == h-1 {
                    for k := 0; k < h; k++ {
                        boardRoute[i][j][k] = (boardRoute[i][j+1][k] && ([]rune(board[i])[j] == '.'))
                    }
                } else {
                    for k := 0; k < h; k++ {
                        boardRoute[i][j][k] = ((boardRoute[i+1][j][k] || boardRoute[i][j+1][k]) && ([]rune(board[i])[j] == '.'))
                    }
                }
            }
        }
    }
}

func checkToGoal(boardRoute [][][]bool, h int) bool {
    for i := 0; i < h-1; {
        iNext := i
        for j := h - 1; j > i; j-- {
            if boardRoute[i][0][j] {
                iNext = j
                break
            }
        }
        if iNext == i {
            return false
        }
        i = iNext
    }
    return true
}

func checkRoop(boardRoute [][][]bool) bool {
    for i, lineRoute := range boardRoute {
        if lineRoute[0][i] {
            return true
        }
    }
    return false
}

func main() {
    var h, w int
    fmt.Scan(&h, &w)

    board := make([]string, h)
    for i := range board {
        fmt.Scan(&board[i])
    }

    boardRoute := make([][][]bool, h)
    for i := range boardRoute {
        lineRoute := make([][]bool, w)
        for j := range lineRoute {
            route := make([]bool, h)
            lineRoute[j] = route
        }
        boardRoute[i] = lineRoute
    }

    searchRoute(board, boardRoute, h, w)
    if checkToGoal(boardRoute, h) && checkRoop(boardRoute) {
        fmt.Println("Yay!")
    } else {
        fmt.Println(":(")
    }
}

解き方の方針は、

  1. 元のボードの各マスから右端のマスそれぞれに到達可能かを動的に求める。
  2. 左上のマスから右下のマスまでボードを繋げた時に（左端→右端→左端→右端…と辿って）有限回で到達可能か検査する。
  3. いずれかの行で同じ行の左端から右端へ到達可能かを検査する。
  4. 2.と3.を両方満たすならば条件を満たすと判定する。

という形です。一番複雑になったのは1.で、3重ループを回している上にボードの下端や右端での処理が個別になされています。

2.と3.を満たせば条件を満たすことの証明をしてみます、まず2.自体が必要条件になっていることは明らかだと思います。 ただし検査方法がやや強引で、

  1. 左上から到達できる右端マスで一番下のものを探す。
  2. 到達した右端マスと同じ行の左端マスからも同様に到達できる右端マスで一番下のものを探す。
  3. 最終的に右下に到達したらtrueを返す。

という形になっています。この検査を行うために3次元配列を作ったり色々面倒なことをしていると言ってもいいです。

次に3.ですが、条件になっている[10^9]回（実質的に無限回）で右下に到達できることと、有限回で右下に到達できることはイコールではありません。 問題ページの入力例4がまさにそれで、1枚のボード内では右下に到達することができますが2枚目のボードの右端に到達することすらできません。

ボードが非常に多くの枚数繋がっている条件下では、どこかの行で右にのみ移動して左端から右端に到達できる必要があります。この場合、有限回で右下に到達できるならボードの枚数がどれほど多くても同様に右下に到達することができます。

コードレビュー

  • 3重ループにif文が組み合わさってネストが非常に深い。
  • ルート構築処理における代入文が長くわかりにくい。

雑記

  • 今回は文字列から（部分文字列ではなく）文字を取り出す手法を導入しました。覚えることがまだまだありますね。

  • D問題は自力70点の解説460点でした。あと少しだったんですけどね。

バグについて

実はこのテストケースが右下に到達できないという判定になります。

6 5
....
###.
..#.
#.#.
#.##
#...

原因についてですが、右端の到達できるマスのうち一番下のマスについてしか次のステップで見ていないためです。 むしろこれでよくACできましたね

ABC 124-D Handstand を累積和を用いて解いてみる(Go)

競プロ AtCoder ABC124 D問題 Go

irisruneです。新しめのABC-D問題を扱うのは久々ですね。

atcoder.jp

解説だけでも3種類の解き方が示されていますが、 今回用いた解き方は累積和を用いたしゃくとり法に少し近い解き方です。見た瞬間はUnion-Find木使うのかと思いました。

package main

import (
    "fmt"
)

func maxInt(a, b int) int {
    switch {
    case a >= b:
        return a
    default:
        return b
    }
}

func main() {
    var n, k int
    var str string
    fmt.Scan(&n, &k, &str)

    var partLength []int
    prevChar := str[0:1]
    cnt := 1
    for i := 1; i < n; i++ {
        if str[i:i+1] == prevChar {
            cnt++
        } else {
            partLength = append(partLength, cnt)
            prevChar = str[i : i+1]
            cnt = 1
        }
    }
    partLength = append(partLength, cnt)

    var cumSum []int
    cumSum = append(cumSum, 0)
    for i := range partLength {
        cumSum = append(cumSum, cumSum[i]+partLength[i])
    }
    if str[0:1] == "0" {
        cumSum = append([]int{0}, cumSum...)
    }
    if str[n-1:n] == "0" {
        cumSum = append(cumSum, n)
    }

    if len(cumSum) <= 2*k+2 {
        fmt.Println(n)
    } else {
        maxRet := 0
        for i := 0; i < len(cumSum)-(2*k+1); i += 2 {
            maxRet = maxInt(maxRet, cumSum[i+(2*k+1)]-cumSum[i])
        }
        fmt.Println(maxRet)
    }

}

解き方の方針は、

  1. 0と1の連続する部分列の長さの配列を作る。
  2. その配列について累積和の配列を作る。
  3. 0が0個連続する部分列から始まり、1が任意の個数連続する部分列で終わるように累積和の配列の先頭と末尾に要素を足す。
  4. i=0,2,4,...について、i+2K+1+1(=i+2L+2)番目とi番目の累積和の差の最大値を求めて解とする。ただし、累積和の配列長がi+2k+2以下の場合はNを解とする。

と少しややこしいものになっています。重要な処理は太字にした3.の部分ですが、4.の処理を単純にするためのものなので全体的に簡単に説明したいと思います。

入力例2について2.まで処理が終わった状況を例示してみます。 1行目は部分列の長さの配列、2行目は補足としてそれぞれ0と1とどちらの連続する部分列かを表したもの、1行空けて4行目は累積和の配列です。

3 1 1 1 1 1 2 2 2
1 0 1 0 1 0 1 0 1

3 4 5 6 7 8 10 12 14

さて、入力例2ではK=2なので、0の連続する部分列を1が連続する部分列に2つ変換することができます。 その場合最も1が連続する部分列が長くなるのは、1が連続する部分列で始まり1が連続する部分列で終わる2K+1個の部分列を繋げるように変換した場合です。

その部分列の長さは、末尾側の1が連続する部分列までの累積和から、先頭側の1が連続する部分列の手前の0が連続する部分列の累積和を引いたものになります。 これを求めるために、先頭に0が連続する長さ0の部分列を追加すると、

0 3 4 5 6 7 8 10 12 14

となるので、累積和の差を先頭から2個ずつインデックスをずらして求めた最大値が解となります。まあ、累積和の求め方の関係で先頭に0はどうしてもついてくるのですが。

入力例1については、元の配列の先頭が0、末尾が0のために先頭と末尾それぞれに1が連続する長さ0の部分列を追加する必要があります。さらに0が連続する長さ0の部分列が先頭に来るように、これも先頭に追加することで解を求めることができます。

入力例3については、各種処理を行った結果得られる累積和の配列の長さが2しかないので、元の配列の長さである1をそのまま解とすることになります。

以上のように各入力例についての解き方を示すことができ、残りの入力に対しても解くことができたわけですが…説明が非常に難しいですね。

コードレビュー

  • 累積和周りの処理アルゴリズムがコードからわかりにくい。
  • 部分列に分割するところは仕方ないとしても累積和は部分列の長さから配列長をある程度は予測できるので、makeで初期化した方が処理時間は短く済む可能性がある。

雑記

  • int用のmax関数を自前で実装したり、switch文やrange文を使ったりすると結構読みやすくなってきたと思います。

  • 次回はsquare869120Contestで解けた問題から一番配点（部分点）の高いものを扱う予定です。

    • パッと見て300点は最低でも解けるはず。

ABC 078-D ABS (Go) / CADDi 2018-D Harlequin (Java)

競プロ AtCoder ABC078 CADDi 2018 D問題 企業コン500点 Go Java

irisruneです。ゲーム理論系の問題で500点ばかり見るのは気のせいでしょうか。

今回は解いた問題の実装が軽かったのと、似たような問題が過去にあったので久々の2本立てです。

ABC 085-D ABS

atcoder.jp

あまり入出力例が多いとボロが出るから例3,4は自明なものを選んだのだと思いました。

package main

import (
    "fmt"
    "math"
)

func main() {
    var n, z, w int
    fmt.Scan(&n, &z, &w)
    arrA := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&arrA[i])
    }
    ans := math.Abs(float64(arrA[n-1] - w))
    if n > 1 {
        if math.Abs(float64(arrA[n-2]-arrA[n-1])) > ans {
            ans = math.Abs(float64(arrA[n-2] - arrA[n-1]))
        }
    }

    fmt.Println(int(ans))
}

ACに至った発想としては、

  • ゲーム理論的には石を何個でも取れる石取りゲームのようなもの。
    • YさんはXさんにとっての最悪手を取る点では同じ。
  • カードを全て引いてしまうか1枚残すかの手をXさんが取ることで、Yさんの取れる手はなくなる。
  • 上記の2つの手を取った際のスコアは計算・比較可能。
    • スコアの比較結果によって、最後の石を取った側が勝ちか負けかが変わる。

なので、（山札の初期枚数が1枚でなければ）Xさんが取れる手は2つに絞られるのでそれぞれのスコアを計算して、 スコアが高い方を出力すればよいと考えられます。

なお無証明ACです。解説ではちゃんと証明がされています。

CADDi 2018-D Harlequin

caddi2018b.contest.atcoder.jp

この頃JavaSilverの勉強をしていたので、この問題もJavaでやっていました。

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        String winner = "second";
        for(long i = 0; i < n; i++){
            long a = sc.nextLong();
            if(a % 2 == 1){
                winner = "first";
                break;
            }
        }
        System.out.println(winner);
    }
}

先ほどの問題を石取りゲームに例えるのは少し強引な部分がありますが、この問題は石取りゲームそのものですね。

  • N色のりんごが実っています
    • →N個の山があります
  • 一度に選ぶりんごは全て異なる色でなければならない
    • →同じ山からは1個までしか石を取れない

なので、全ての山について石の個数が2(=1+1)の倍数の状態で手番が回ってくると負け、それ以外の状態なら勝ちということになります。

この問題はゲーム理論を少し学んでいればかなり簡単だと思います。300点くらいなのでは。

雑記

  • PythonエンジニアとJavaSilverを同時期に取りましたがPythonはよくわからないです。
    • コンパイル言語の機械学習の本とかほとんど見かけないのが辛いですね。

ABC 085-D Katana Thrower (Kotlin/Go)

競プロ AtCoder ABC085 D問題 Kotlin Go

irisruneです。この問題を選んだ理由は最近発売された某ゲームを連想したからです。

今回は構造体の配列が作れなくてGoを断念したのでKotlinで解いていましたが、 後でGoで解き直したので両方のコードを掲載します。

atcoder.jp

初見だとそれほど難しくなさそうに見えたのですが、1回目のACまでに2WAしたりと結構苦戦しました。 まずは解説を見ずに解いたKotlinのコードです。

class Katana(val at : Int, val th : Int)

fun ceilDiv(t : Int, d : Int) : Int{
    return if(t % d > 0) t / d + 1 else t / d
}

fun thrower(attacker : Katana, lKatana : MutableList<Katana>, h : Int, n : Int) : Pair<Int, Int>{
    var cnt = 0
    var hp = h
    for(i in 0..(n - 1)){
        if(hp <= attacker.th) return Pair(cnt, hp)
        if(lKatana[i].th <= attacker.at) return Pair(cnt, hp)
        hp -= lKatana[i].th
        cnt++
        if(hp <= 0) return Pair(cnt, hp)
    }
    return Pair(cnt, hp)
}

fun battle(attacker : Katana, lKatana : MutableList<Katana>, h : Int, n : Int) : Int{
    var (cnt, hp) = thrower(attacker, lKatana, h, n)
    if(hp <= 0) return cnt
    hp -= attacker.th
    cnt++
    if(hp <= 0) return cnt

    return cnt + ceilDiv(hp, attacker.at)
}

fun main(args: Array<String>){
    val (n, h) = readLine()!!.split(" ").map(String::toInt)

    val lKatana = mutableListOf<Katana>()
    for(i in 0..(n-1)){
        val (at, th) = readLine()!!.split(" ").map(String::toInt)
        lKatana.add(Katana(at, th))
    }

    lKatana.sortByDescending { it.at }
    val attacker = lKatana[0]
    lKatana.removeAt(0)

    lKatana.sortByDescending { it.th }
    println(battle(attacker, lKatana, h, n - 1))
}

基本方針としては、

  • 振る用の武器を予め確保しておく。
  • それ以外の武器で、振る用の武器を振るより投げる攻撃力の高い武器を投げる攻撃力が高い順に投げる。
  • 最後の一撃として振る用の武器を仮想的に投げておく。
  • 振る用の武器を振って魔物を倒す。

という形で、途中で魔物が倒れたり振る用の武器を投げて倒せる状態になったりした場合には処理を中断します。 2WAしたのは振る用の武器以外を投げた後に魔物が倒れているかどうかの判定をしていなかったためです。

反省点としては、

  • 制約条件を読み飛ばしていたため、振る攻撃力より投げる攻撃力が必ず高いことに途中で気付いた。
    • 問題文はしっかり読みましょう。
  • 振る用の武器とそれ以外の武器を区別した結果処理が煩雑になっている。
    • 振る用の武器を投げて倒せるかどうかの判定を毎回入れたりしている点など。
  • 振る用の武器を振る前に投げていることから、振る用の武器とそれ以外の武器を区別する意味がないことに気付いておきたかった。
    • そればかりか、振る攻撃力と投げる攻撃力を個別に考えることができるので処理が簡略化できる。

…というのを解説を読んだ時点では理解していなくて、翌朝になって突然理解しました。 その結果Goでもなんとか実装できるようになったのでGoで解き直したのがこちらです。

package main

import (
    "fmt"
    "sort"
)

func ceilDivInt(end int, div int) int {
    if end%div > 0 {
        return end/div + 1
    }
    return end / div
}

func battle(h int, attack int, arrB []int) int {
    var cnt = 0
    for i := range arrB {
        if arrB[i] < attack {
            break
        }
        h -= arrB[i]
        cnt++
        if h <= 0 {
            break
        }
    }
    if h <= 0 {
        return cnt
    }
    return cnt + ceilDivInt(h, attack)
}

func main() {
    const nCity = 5
    var n, h int
    fmt.Scan(&n, &h)
    var arrA, arrB []int
    for i := 0; i < n; i++ {
        var a, b int
        fmt.Scan(&a, &b)
        arrA = append(arrA, a)
        arrB = append(arrB, b)
    }
    sort.Sort(sort.Reverse(sort.IntSlice(arrA)))
    sort.Sort(sort.Reverse(sort.IntSlice(arrB)))

    var attack = arrA[0]

    fmt.Println(battle(h, attack, arrB))
}

関数が1個減ったり、構造体（クラス）を使わなくてよくなったりと簡略化されました。

こちらの反省点として、早期returnのために除算の切り上げ処理を関数化したりしているのですが、 Goはif文の処理部分で1文のみであっても中括弧が必須なためreturn文のみにしても簡略化しきれておらず、 あまり関数化の恩恵が大きくないような気はします。 関数名で処理を説明できたりするので恩恵がないこともないはずですが。

雑記

f:id:amifiable:20190410130208p:plain

  • 多少アルゴリズムが違いますが、Kotlinの方がGoより速いですね…
    • KotlinとGoで時間のかかる問題が違うのがよくわからないです。

追記

f:id:amifiable:20190410142656p:plain

  • Kotlinでも2回目と同じアルゴリズムで解いてみたところもっと速くなりました。
    • Goの方がパッケージ提供されてるソートが弱かったりするんでしょうか。

さらに追記

f:id:amifiable:20190411175608p:plain

  • 下から順に、
    • 配列（のスライス）を初めから容量nで生成して拡張処理を行わないようにした。
    • 入力の際に振る攻撃力の最大値を求めることでソートする配列を2個から1個に減らした。
    • 除算して切り上げる処理を関数でなく直接行うようにした。
  • わけなのですが、あまり計算時間が変わらないですね…
    • 入力処理の問題だとしても、Kotlinより遅いのはよくわからないですね。