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

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

AtCoder CODE FESTIVAL 2016 qual B C - Gr-idian MST (Go)

競プロ AtCoder CODE FESTIVAL 2016 qual B C問題 500点 Go

irisruneです。少し時間が取れなかったので月曜から過去問です。

問題

atcoder.jp

最小全域木を生成するアルゴリズムに貪欲法の要素を加えた感じになります。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

const INF = 1000000000

type key struct {
    cost int
    open int
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n, m := nextInt(), nextInt()
    pattern := 1 << uint(n)
    keys := make([]key, m)
    for mi := 0; mi < m; mi++ {
        a, b := nextInt(), nextInt()
        open := 0
        for bi := 0; bi < b; bi++ {
            c := nextInt()
            open = open | (1 << uint(c-1))
        }
        keys[mi] = key{a, open}
    }

    dp := make([][]int, m+1)
    dp[0] = make([]int, pattern)
    // dp[0][0] = 0
    for pi := 1; pi < pattern; pi++ {
        dp[0][pi] = INF
    }

    for mi := 0; mi < m; mi++ {
        dp[mi+1] = make([]int, pattern)
        copy(dp[mi+1], dp[mi])
        for pi := 0; pi < pattern; pi++ {
            pnext := pi | keys[mi].open
            if dp[mi][pi]+keys[mi].cost < dp[mi+1][pnext] {
                dp[mi+1][pnext] = dp[mi][pi] + keys[mi].cost
            }
        }
    }

    switch {
    case dp[m][pattern-1] < INF:
        fmt.Println(dp[m][pattern-1])
    default:
        fmt.Println(-1)
    }
}

最小全域木を求めるアルゴリズムとしてはクラスカル法が有名ですが、クラスカル法の計算量は辺の数をEとするとO(E\log E)です。一方で辺の数はO(WH)であるため、クラスカル法をそのまま用いると計算が間に合いません。

そこでクラスカル法がどういうアルゴリズムかを見直してみます。

  1. 各頂点を頂点1の木とおく。
  2. 全ての辺の集合から長さの最も短い辺を取り出す。
  3. 取り出した辺が2つの木を結ぶ場合、それらをまとめて1つの木にする。
  4. 2.と3.を繰り返すと最終的に1つの最小全域木が残る。

今回の問題では、（端点の）x座標またはy座標が同じ辺の集合は長さが同じなので、そういった辺の集合ごとに考えればよさそうです。具体的には次のようなアルゴリズムで解くことができます。

  1. x座標またはy座標が同じ辺の集合をそれぞれ作る。
  2. 辺の集合の集合から、辺の長さ（コスト）の最も短い辺の集合を取り出す。
    1. そのような集合が複数ある場合は、その中の1つを取り出す（まとめて取り出さない）。
  3. 取り出した辺の集合がx軸に平行なら、辺の本数からy軸に平行で既に取り出したことのある辺の集合の数を引き、その数の辺を求める最小全域木に加える。
    1. y軸に平行な辺の集合についても同様。
  4. 2.と3.を繰り返すと最終的に最小全域木の辺の長さ（コスト）の合計が求められる。

このアルゴリズムで解が求められることを簡単な例で示します。H,W=1,p_0=1,q_0=2の場合を考えると、以下の流れで解くことができます。

  1. x座標0,1を結ぶ辺の集合、y座標0,1を結ぶ辺の集合（どちらも要素数2）を作る。
  2. コストの最も短い辺の集合はx座標0,1を結ぶ辺の集合なのでこれを取り出す。
  3. y軸に平行な辺の集合は1つも取り出したことがないので、最小全域木には辺を2本とも加える。
  4. y座標0,1を結ぶ辺の集合を取り出す。
  5. x軸に平行な辺の集合は1つ取り出しているので、最小全域木には辺を1本加える。
  6. 最終的な最小全域木の辺のコストの合計は4となる。

まず、x座標0,1を結ぶ辺の集合を取り出したときには集合に含まれるどの辺も2つの木を結ぶ辺となります。そのためすべての辺を最小全域木に加えることができます。

一方、y座標0,1を結ぶ辺の集合を取り出したときには2つの辺がどちらも同じ2つの木を結ぶ辺となります。そのため辺の集合から1本を除いて最小全域木に加えることになります。

このような考え方は問題のサイズを大きくしても成り立つので、結局上記のアルゴリズムにより解くことができます。

雑記

  • 最近のAGCでは珍しくB問題が易しめのようなので、今週はA問題とB問題をそれぞれ扱う予定です。

AtCoder ABC 142 E - Get Everything 解説AC (Go)

競プロ AtCoder ABC142 E問題 500点 Go

irisruneです。解説ACですが記事にすることはできそうでした。

問題

atcoder.jp

これも一つのbitDPではありそうですが、特殊なケースになると思います。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

const INF = 1000000000

type key struct {
    cost int
    open int
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n, m := nextInt(), nextInt()
    pattern := 1 << uint(n)
    keys := make([]key, m)
    for mi := 0; mi < m; mi++ {
        a, b := nextInt(), nextInt()
        open := 0
        for bi := 0; bi < b; bi++ {
            c := nextInt()
            open = open | (1 << uint(c-1))
        }
        keys[mi] = key{a, open}
    }

    dp := make([][]int, m+1)
    dp[0] = make([]int, pattern)
    // dp[0][0] = 0
    for pi := 1; pi < pattern; pi++ {
        dp[0][pi] = INF
    }

    for mi := 0; mi < m; mi++ {
        dp[mi+1] = make([]int, pattern)
        copy(dp[mi+1], dp[mi])
        for pi := 0; pi < pattern; pi++ {
            pnext := pi | keys[mi].open
            if dp[mi][pi]+keys[mi].cost < dp[mi+1][pnext] {
                dp[mi+1][pnext] = dp[mi][pi] + keys[mi].cost
            }
        }
    }

    switch {
    case dp[m][pattern-1] < INF:
        fmt.Println(dp[m][pattern-1])
    default:
        fmt.Println(-1)
    }
}

まず計算量の見通しを立てる必要があります。まずNについて考えると、それぞれの宝箱を開けられるかどうかを考えることになるので、O(2^N)またはO(2^NN)辺りになりそうです。なので全体の計算量はO(2^NM(\times N))辺りになると考えられます。

ここでbitDPで解くことを考えてみます。この問題をbitDPで解くということは、以下のように箱に対するDPに帰着されるということになります。

  1. N_0個の宝箱を開ける場合の組み合わせそれぞれに対する最小費用を求める。
  2. 1.の結果を利用してN_0+1個の宝箱を開ける場合の組み合わせそれぞれに対する最小費用を求めることができる。

しかし、このようなアルゴリズムに帰着させることができないことが示せます。例えば入力例1をアレンジした以下の入力に対する解を考えます。

2 3
10 1
1
15 1
2
20 2
1 2

この場合、1個の宝箱を開ける場合の最小費用は箱1,2それぞれに対して10,15となりますが、2個の宝箱を開ける場合の最小費用は10+15=25ではなく、3番目の鍵のみ購入する20となります。

つまり、箱に対してDPを適用することはできません。今回はここで詰まってしまい解説ACすることとなりました。

結論としては、箱ではなく鍵に対してDPを適用することでこの問題を解くことができます。ナップサック問題の変形として考えると以下のような問題になります。

  1. 荷物の価値を鍵の価格、荷物の重さ（容量）を鍵に対応する宝箱の（bitによる）組み合わせに置き換える。
  2. 1,2,\ldots,M_0番目の鍵を用いることができる場合の、開けることができる宝箱の組み合わせとそのときの最小費用を求める。
  3. 2.の宝箱の組み合わせとM_0+1番目の鍵に対応する宝箱の組み合わせの論理和を求めることによって、1,2,\ldots,M_0,M_0+1番目の鍵を用いることができる場合の、開けることができる宝箱の組み合わせとそのときの最小費用を求めることができる。
  4. M個の鍵全てを用いることができる場合の、N個全ての宝箱を開けることができる最小費用が最終的な解となる。

端的に言えば、箱の状態をbitで表しつつ鍵の本数を増やしていくDPとなります。DPテーブルのサイズは箱の状態が2^N、鍵の本数がMのためO(2^NM)となります。

荷物の価値を宝箱の組み合わせ、荷物の重さを鍵の価格に置き換えるとDPとしてわかりやすいと思いますが、鍵の価格の合計は最大10^5Nとなるため、DPテーブルのサイズが10^9をやや上回り、計算が間に合わない可能性が高いです。頑張れば通せそうなスケールなので試してみたい気もします。

雑記

  • DPテーブルの要素にコスト、軸に価値が入るのがbitDPの特徴であると言えるかもしれません。適当言ってるかもしれません。

AtCoder ABC 142 F - Pure (Go)

競プロ AtCoder ABC142 F問題 600点 Go

irisruneです。ABC-F問題が自力で解けたのはこれで2度目です。

問題

atcoder.jp

グラフ理論です。何を求めればよいかが把握できるかどうかの問題だと思います。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

type vertex struct {
    num     int
    prev    *vertex
    visited []bool
}

func findCycle(n int, adj []map[int]struct{}) ([]int, bool) {
    for i := 1; i <= n; i++ {
        queue := make([]vertex, 0)
        queue = append(queue, vertex{i, nil, make([]bool, n+1)})
        for len(queue) > 0 {
            v := queue[0]
            queue = queue[1:]
            for x := range adj[v.num] {
                if v.visited[x] {
                    ret := []int{v.num}
                    for v.num != x {
                        ret = append(ret, v.prev.num)
                        v = *v.prev
                    }
                    return ret, true
                }
                visited := make([]bool, n+1)
                copy(visited, v.visited)
                visited[v.num] = true
                queue = append(queue, vertex{x, &v, visited})
            }
        }
    }
    return []int{}, false
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n, m := nextInt(), nextInt()
    adj := make([]map[int]struct{}, n+1)
    for ni := 0; ni <= n; ni++ {
        adj[ni] = make(map[int]struct{})
    }
    for i := 0; i < m; i++ {
        a, b := nextInt(), nextInt()
        adj[a][b] = struct{}{}
    }

    cycle, ok := findCycle(n, adj)
    if !ok {
        fmt.Println(-1)
        return
    }

    for i := 0; ; i++ {
        if i >= len(cycle)-1 {
            break
        }
        for j := i + 1; ; j++ {
            if j >= len(cycle) {
                break
            }
            _, ok := adj[cycle[i]][cycle[j]]
            if ok {
                cycle = cycle[i : j+1]
                i, j = 0, j-i
            }
        }
    }
    fmt.Println(len(cycle))
    for _, c := range cycle {
        fmt.Println(c)
    }
}

結論だけ言えば、元のグラフに含まれる長さが極小となる閉路が求める誘導部分グラフになります。ひとまずこれを示してみます。

まず、すべての頂点について入次数と出次数が1以上になるためにはグラフが閉路を持つ必要があります。1また、入次数と出次数がちょうど1となるためにはグラフが単一の閉路で構成される必要があります。

ここで誘導部分グラフの性質について考えてみます。元のグラフに含まれるある閉路について、その閉路を構成する頂点集合を誘導部分グラフの頂点集合とした場合、以下のことがいえます。

  1. 誘導部分グラフのすべての頂点について入次数と出次数が1以上となる。
  2. 入次数と出次数が2以上となる頂点が存在するとき、誘導部分グラフの頂点数よりも長さの短い閉路が存在する。
    1. 誘導部分グラフを構成する辺はすべていずれかの閉路を構成する。

つまり、誘導部分グラフがより長さの短い閉路を含む場合、その閉路を構成する頂点集合を新たな誘導部分グラフの頂点集合とすることができます（当然元のグラフの誘導部分グラフになります）。このとき誘導部分グラフの頂点数は減少し、また長さ2の閉路を構成する頂点集合からなる誘導部分グラフは明らかにすべての頂点の入次数と出次数が1となります。

以上より、自身より長さの短い閉路を含まない（長さが極小の）閉路が条件を満たす誘導部分グラフとなることが示せます。よって以下の手順により問題を解くことができます。

  1. 元のグラフにおいて閉路が含まれるか探索する。
    1. 閉路がない場合は条件を満たす誘導部分グラフは存在しない。
  2. 探索した閉路を構成する頂点集合を誘導部分グラフの頂点集合とおく。
  3. 誘導部分グラフにおいて閉路が含まれるか探索する。
    1. 閉路がない場合は、誘導部分グラフ自身が条件を満たす。
    2. 閉路がある場合は、探索した閉路を構成する頂点集合を誘導部分グラフの頂点集合に置き直す。

ここからは提出コードにおける実装について軽く解説していきます。

まず閉路の探索について、各頂点からBFSで探索を行う形で実装しています。その際、既に訪れた頂点を各探索の頂点ごとに持たせているため少しややこしい実装になっています。計算量はO(N^2)です。

次に極小の閉路を求める部分について、求めた閉路に余分な辺が含まれるかどうかを隣接頂点の集合を用いて判定し、閉路を縮小させていく形で実装しています。計算量はO(N^2)です2。

以上より、全体の計算量はO(N^2)となります3。

雑記

  • E問題はまだ解けてません。解説ACでもいいと思うのですが、単純に記事を書くことが難しいのが難点です。

  1. 正確にいえば、どの頂点から出発しても元の頂点に戻ってくることができる（どの頂点についてもその頂点を含む閉路が存在する）グラフである必要があります。↩

  2. ある頂点が隣接頂点の集合に含まれるかの判定にハッシュマップを用いているのでO(N(N+M))にはならないと思います。↩

  3. 辺の入力を受け取る部分については、辺の数がO(N^2)となるので結局O(N^2)となります。↩

AtCoder ABC 142 D - Disjoint Set of Common Divisors (Go)

競プロ AtCoder ABC142 D問題 400点 Go

irisruneです。もう9月も終わりですが、残暑が続きますね。

問題

atcoder.jp

アルゴリズムは単純なので難易度は比較的低いですが、素因数分解が必要なため割と面倒な問題です。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func gcd(a, b int) int {
    if a < b {
        a, b = b, a
    }
    if a%b == 0 {
        return b
    }
    return gcd(b, a%b)
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    a, b := nextInt(), nextInt()
    gcd := gcd(a, b)

    ans := 1
    gcdCopy := gcd
    for d := 2; d*d <= gcd; d++ {
        if gcdCopy%d != 0 {
            continue
        }
        ans++
        for gcdCopy%d == 0 {
            gcdCopy /= d
        }
    }
    if gcdCopy > 1 {
        ans++
    }
    fmt.Println(ans)
}

2数が互いに素であるとき、2数の最大公約数が1であるということがいえます。そのため、A,Bの正の公約数の中から互いに素なものを選ぶとき、1あるいは素数のみを選ぶことが最適であるといえます。

結局A,Bの正の公約数はA,Bの最大公約数の約数であるため、A,Bの最大公約数を素因数分解することで解を求めることができます。

なお、素因数分解は2から\lfloor \sqrt{M} \rfloorまでの数でMを割ればいいだけなのですが、ループ回数の基準になる値と除算の対象が同一なので値のコピーを行う必要があったり、最後に残った数が1あるいは（\lceil\sqrt{M}\rceil以上の）素数になることに注意する必要があったり、色々面倒です。

Mが小さければ2からMまでの素数を予め列挙しておくと楽になるのですが、エラトステネスの篩を用いてもO(M\log\log M)の計算量となってしまうので今回はこの手法を用いることができません。妥協して2から\sqrt{M}までの素数を列挙してもあまりメリットはなさそうです。

雑記

  • E問題が厳しいので今週は過去問を2回取り扱うことになるかもしれません。

AtCoder Mujin Programming Challenge 2017 B - Row to Column (Go)

競プロ AtCoder Mujin Programming Challenge 2017 B問題 1300点 Go

irisruneです。1300点問題が解けたのは嬉しいです。

問題

atcoder.jp

得点が高いですが、アルゴリズムや実装の難しさよりも数学パズル寄りの問題だとは思います。

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
)

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

const INF = 1000000000

type row struct {
    num    int
    blacks int
}

type rows []row

func (r rows) Len() int {
    return len(r)
}

func (r rows) Swap(i, j int) {
    r[i], r[j] = r[j], r[i]
}

func (r rows) Less(i, j int) bool {
    return r[i].blacks < r[j].blacks
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n := nextInt()
    board := make([][]bool, n)
    for i := range board {
        board[i] = make([]bool, n)
        s := nextStr()
        for j, r := range s {
            if r == '#' {
                board[i][j] = true
            }
        }
    }

    var rows rows = make([]row, n)
    for i, line := range board {
        rows[i].num = i
        for _, b := range line {
            if b {
                rows[i].blacks++
            }
        }
    }
    sort.Sort(sort.Reverse(rows))

    if rows[0].blacks == 0 {
        fmt.Println(-1)
        return
    }

    ans := INF
    for _, r := range rows {
        if n-r.blacks > ans {
            break
        }
        count := 1
        for i := range board {
            if board[i][r.num] {
                count -= 1
                break
            }
        }
                count += (n - r.blacks)
        if ans > count {
            ans = count
        }
    }

    for j := 0; j < n; j++ {
        for i := range board {
            if !board[i][j] {
                ans++
                break
            }
        }
    }

    fmt.Println(ans)
}

まずはロボットの操作によってマス目がどのように変化するか考えてみます。すると以下のことがいえます。

  1. すべてのマスが黒の行を記憶することで、任意の列のすべてのマスを黒にすることができる。
  2. 白のマスが1つでも存在する行を記憶したならば、塗り替えた列には白のマスが最低1つは存在する。
  3. 黒のマスが存在しないとき、塗り替えた後も黒のマスは存在しない。

ここから、行うべき操作の手順が以下のように示せます。

  1. 黒のマスが存在しなければ、すべてのマスを黒にすることができないと判定する。
  2. すべてのマスが黒の行が存在するならば、白のマスが1つでも存在する列を塗り替える。
  3. すべてのマスが黒の行が存在しないならば、マスを塗り替えることですべてのマスが黒の行を生成する。
    1. i列目が黒の行を記憶することでi行目のすべてのマスを黒にすることができる。
    2. 黒のマスが1つでも存在する行を記憶してi列目を塗り替えることでi列目が黒の行を生成することができる。

こちらの手順から、出力すべき値が以下のように導き出せます。

  1. 黒のマスが存在しなければ、-1を出力する。
  2. すべてのマスが黒の行が存在するならば、白のマスが1つでも存在する列の数を出力する。
  3. すべてのマスが黒の行が存在しないならば、1\leq i \leq Hにおける以下の最小値を出力する。
    1. i列目が黒の行が存在するならば、i行目の白のマスの数。
    2. i列目が黒の行が存在しないならば、i行目の白のマスの数+1。

このようにして導き出した値が（1.の場合を除き）操作回数の最小値となることは以下により示せます。

  1. すべてのマスが黒の列を塗り替える必要はないので、一連の操作で白のマスが1つでも存在する列の数が増えることはない。
  2. すべてのマスが黒の行が存在しないならば、塗り替えた列には白のマスが最低1つは存在するので、白のマスが1つでも存在する列の数が減ることはない。
  3. 1.と2.より、すべてのマスが黒の行を生成する過程と白のマスが1つでも存在する列を塗り替える過程は独立であるとみなすことができる。

雑記

  • この問題のDifficultyが2000強あったので（得点の割に低い気はしますが）、解いた問題では最高Difficultyだと思っていました。
    • 実際は以前記事にしましたAGC035-Cの方がDifficultyが高かったです。こちらもかなりパズル寄りの問題ですね。

AtCoder AGC 038 A - 01 Matrix (Go)

競プロ AtCoder AGC038 A問題 300点 Go

irisruneです。やはりAGCはB問題が安定しないと手が出し辛いです。

問題

atcoder.jp

いつものAGC-Aらしく数学パズル的な問題です。嘘解法ではないはずですが実行時間1978msでした。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    h, w, a, b := nextInt(), nextInt(), nextInt(), nextInt()

    for hi := 0; hi < b; hi++ {
        for wi := 0; wi < a; wi++ {
            fmt.Print("1")
        }
        for wi := a; wi < w; wi++ {
            fmt.Print("0")
        }
        fmt.Println("")
    }
    for hi := b; hi < h; hi++ {
        for wi := 0; wi < a; wi++ {
            fmt.Print("0")
        }
        for wi := a; wi < w; wi++ {
            fmt.Print("1")
        }
        fmt.Println("")
    }
}

入力例1に対しての出力例1がミスリードになっています。A,Bは各行、各列について0,1の少ない方の数となるので、B=1のときには1列目に1を2個（0を1個）配置することができます。同様にA=1のときには3行目に1を2個（0を1個）配置することができるので、以下のような出力が可能です。

100
100
011

この考え方は制約を満たす任意のH,W,A,Bに対して拡張可能なので、どのような入力に対しても条件を満たす行列を出力することができます。

なお、上記のコードの計算量はO(HW)です。その割に実行時間がかなりギリギリだったのはどうしてでしょう…？Print関数を何回も呼び出しているのがよくない可能性はありそうです。

雑記

  • 使う文字列は高々2通りしかないので、文字列を作成してからループで出力するアルゴリズムを組んだ方が圧倒的に速いです。
    • 計算量はO(H+W)で済みますし、計算時間も5msしかかかりませんでした。

AtCoder ABC 141 E - Who Says a Pun? (Go) ※嘘解法

競プロ AtCoder ABC141 E問題 500点 Go

irisruneです。実行時間1945msはかなり攻めた嘘解法だと思いました。

問題

atcoder.jp

一見愚直に解けそうに見えますが工夫が必要な問題です。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

type node struct {
    len      int
    idxs     []int
    children map[rune](*node)
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n, s := nextInt(), nextStr()
    rs := []rune(s)

    root := node{0, make([]int, n), make(map[rune](*node), 0)}
    for i := 0; i < n; i++ {
        root.idxs[i] = i
    }
    queue := []*node{&root}
    ans := 0
    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        if cur.idxs[len(cur.idxs)-1]-cur.idxs[0] < cur.len {
            continue
        }
        ans = cur.len
        for _, idx := range cur.idxs {
            if idx+cur.len >= n {
                continue
            }
            r := rs[idx+cur.len]
            child, ok := cur.children[r]
            switch {
            case ok:
                child.idxs = append(child.idxs, idx)
            default:
                child = &(node{cur.len + 1, []int{idx}, make(map[rune](*node), 0)})
            }
            cur.children[r] = child
        }
        for _, child := range cur.children {
            queue = append(queue, child)
        }
    }

    fmt.Println(ans)
}

制約上、計算量がO(N^2)であれば十分間に合います。そしてSの連続する部分文字列の数はO(N^2)であるため、各部分文字列の位置と合わせて記憶しつつ文字列比較を行うことで愚直に解くことができそうです。

しかし単純な文字列比較を行うための計算量はO(N)であるため、全体の計算量はO(N^3)となってしまい到底間に合いません。文字列比較にローリングハッシュを用いるという解法が公式解説にて別解として示されていますが、今回は別の手法で解きました。

今回の手法は枝刈りBFSに近いものです。探索木の構造としては、右端をSの右端に固定したN個の部分文字列について、1文字目の文字種毎に開始位置の集合を節点として持ち、その子として2文字目の文字種毎に開始位置の集合を節点として持ち…という構造になっています。ちなみに探索木の根は0文字目の文字種（当然そのようなものはないため空あるいは任意文字とでも定義します）に対する開始位置の集合(1,2,\ldots,N)です。

探索にかかる計算量は節点ごとの集合の要素数の和の定数倍となります。枝刈りを無視すると各階層毎に合計N個の要素（部分文字列）があるので、計算量はO(N^2)と推測されます。しかし実行時間が2秒近いことを考えるとどこかに見落としがあるか、あるいは定数倍の部分で計算量が増大しているかもしれません。

枝刈りによって階層毎の要素数がN/1,N/2,\ldots,N/Nと減少していくので（実際は要素数が2を下回る節点そのものが枝刈りされるためもっと減ります）、計算量はO(N\log N)と推測することもできますが、明らかに実行時間やループ回数に見合っていないのでおそらく正しい推察ではありません。

雑記

  • 上記コードで各節点に子の集合を持たせようとはしていますが、特に意味はなかったことに気付きました。
  • 初めてZ-Algorithmというものの存在を知りました、内容はまだ殆ど理解していないです。
    • セグメント木を理解していなかったりなど知識面で躓くことは多いので、難しめの問題に必要なアルゴリズムやデータ構造も身に付けたいです。

AtCoder ABC141 D - Powerful Discount Tickets (Go)

競プロ AtCoder ABC141 D問題 400点 Go

irisruneです。D問題が大体安定して解けるようになっている辺り成長を感じますね。

問題

atcoder.jp

Go言語にとってソート以上の鬼門と言えるであろうヒープを使う問題です。

package main

import (
    "bufio"
    "container/heap"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

type Heap []int

func (h Heap) Len() int {
    return len(h)
}

func (h Heap) Less(i, j int) bool {
    return h[i] > h[j] // reversed-Heap
}

func (h Heap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *Heap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *Heap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n, m := nextInt(), nextInt()

    h := &Heap{}
    heap.Init(h)
    for i := 0; i < n; i++ {
        heap.Push(h, nextInt())
    }

    for j := 0; j < m; j++ {
        (*h)[0] /= 2
        heap.Fix(h, 0)
    }

    ans := 0
    for _, v := range *h {
        ans += v
    }
    fmt.Println(ans)
}

ある商品に対してY枚の割引券を使う操作は、1枚の割引券を使った後にY-1枚の割引券を使う操作と等価です（厳密な証明は公式解説を参照してください）。これにより割引券を1枚ずつ、その時点で最も高い商品に対して使う手法で解を求めることができます。

その際必要な計算量について考えると、愚直に実装した場合は最も高い商品を探す処理にO(N)かかるため、全体でO(NM)かかってしまい間に合いません。つまり最も高い商品を探す処理にO(\log N)以下の計算量となるように実装する必要があると考えられます（一応O(\sqrt{N})でもよいですが、探索・ソートアルゴリズムの計算量ではあまり見かけないと思います）。

ここでヒープ（あるいは優先度付きキュー）を用いることで全体の計算量をO((N+M)\log N)に抑えることができます。これはヒープの初期化処理がO(N\log N)、要素の追加・削除（更新）がO(\log N)、最大要素の取得がO(1)の計算量で行えるためです。

ところで、他の方法として仮に二分探索を用いるとすると、以下のような実装が考えられます。

  1. 全商品をソートする。
  2. 最も高い商品に割引券を使う。
  3. 割引券を使った商品が入る場所を二分探索によって求める。
  4. 求めた場所に割引券を使った商品を入れる。
  5. 割引券がある限り2.～4.を繰り返す。

この実装は一見問題ないように思えますが、4.の配列に対する挿入処理でO(N)の計算量がかかってしまいます。そのため結局全体の計算量がO(NM)となってしまうのでこの実装は使えません。

結局、配列を用いる場合は探索あるいは挿入がボトルネックになってしまうので、配列以外のデータ構造を用いることになると思います。

雑記

  • Goでヒープを使うためには、単純にソートインタフェース以上の数のメソッドを定義する必要があり手間がかかってしまいます。
    • ソートは最近のバージョンで実装の簡略化が可能になりましたが、ヒープは特にそういうこともないので使わずに済むならそれに越したことはないですね。
  • 今週はABC141-Eの嘘解法か最近解けた1300点問題かのどちらかについて書く予定です。前者の方が書きにくそうなので折れたら後者を書きます。

AtCoder ARC059 E - キャンディーとN人の子供 / Children and Candies (Go)

競プロ AtCoder ARC059 E問題 400点 800点 Go

irisruneです。今回は部分点込みの解説になるのでコードの分量が多めなのと、式を使った解説が多くなっています。

問題

atcoder.jp

部分点解法は典型的な…？DP問題、満点解法はその発展となっています。

部分点解法（400点）

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

const MOD = 1000000007

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n, c := nextInt(), nextInt()

    aArray := make([]int, n)
    for ni := range aArray {
        aArray[ni] = nextInt()
    }
    bArray := make([]int, n)
    for ni := range bArray {
        bArray[ni] = nextInt()
        if aArray[ni] != bArray[ni] {
            fmt.Println(-1)
            return
        }
    }

    dp := make([][]int, c+1)
    for ci := range dp {
        dpLine := make([]int, n)
        dp[ci] = dpLine
    }

    for ci, dpLine := range dp {
        for ni := range dpLine {
            if ci == 0 {
                dp[ci][ni] = 1
                continue
            }
            if ni == 0 {
                dp[ci][ni] = dp[ci-1][ni] * aArray[ni] % MOD
                continue
            }
            dp[ci][ni] = (dp[ci][ni-1] + (dp[ci-1][ni] * aArray[ni] % MOD)) % MOD
        }
    }
    fmt.Println(dp[c][n-1])
}

コードを見ればわかる通りA_i=B_iの場合は単純なDPで解くことができます。計算量はO(CN)となるため十分間に合います。

DPで解けることを示す前に全探索できないか考えてみましょう。区別できないC個のキャンディーをN人の子供に配る場合の数は_{N+C-1}C_C通りです1。これはN=400,C=400のとき非常に大きな数となるため、全探索は現実的ではありません。

そこでDPで解くことを考えます。C=C_0,N=N_0のときのf(x_1,x_2,\ldots,x_N)の値をF(C_0)(N_0)とおきます。このとき、F(C_0)(N_0)=x_{N_0}F(C_0-1)(N_0)+F(C_0)(N_0-1)が成り立つのでDPにより解くことができます。

満点解法

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

const MOD = 1000000007
const UBOUND = 400

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n, c := nextInt(), nextInt()

    aArray := make([]int, n)
    for ni := range aArray {
        aArray[ni] = nextInt()
    }
    bArray := make([]int, n)
    for ni := range bArray {
        bArray[ni] = nextInt()
    }

    powMat := make([][]int, UBOUND+1)
    for r := range powMat {
        pow := make([]int, UBOUND+1)
        for i := range pow {
            if r == 0 {
                pow[i] = 1
                continue
            }
            pow[i] = (powMat[r-1][i] * i) % MOD
        }
        powMat[r] = pow
    }
    powCumSumMat := make([][]int, UBOUND+1)
    for r := range powCumSumMat {
        powCumSum := make([]int, UBOUND+1)
        for x := range powCumSum {
            if x == 0 {
                powCumSum[x] = powMat[r][x]
                continue
            }
            powCumSum[x] = (powCumSum[x-1] + powMat[r][x]) % MOD
        }
        powCumSumMat[r] = powCumSum
    }

    dp := make([][]int, c+1)
    for ci := range dp {
        dpLine := make([]int, n)
        dp[ci] = dpLine
    }

    for ci, dpLine := range dp {
        for ni := range dpLine {
            if ni == 0 {
                dp[ci][ni] = powCumSumMat[ci][bArray[ni]] - powCumSumMat[ci][aArray[ni]-1]
                switch {
                case dp[ci][ni] < 0:
                    dp[ci][ni] += MOD
                default:
                    dp[ci][ni] %= MOD
                }
                continue
            }
            for cj := 0; cj <= ci; cj++ {
                switch {
                case powCumSumMat[cj][bArray[ni]]-powCumSumMat[cj][aArray[ni]-1] < 0:
                    dp[ci][ni] += dp[ci-cj][ni-1] * (powCumSumMat[cj][bArray[ni]] - powCumSumMat[cj][aArray[ni]-1] + MOD) % MOD
                default:
                    dp[ci][ni] += dp[ci-cj][ni-1] * ((powCumSumMat[cj][bArray[ni]] - powCumSumMat[cj][aArray[ni]-1]) % MOD) % MOD
                }
                dp[ci][ni] %= MOD
            }
        }
    }
    fmt.Println(dp[c][n-1])
}

こちらもDPをベースとした解法となります。計算量はO(C\max(A_i,B_i)+C^2N)となりますが、制限時間が4秒なのでまだ間に合う範囲です。

まずはf(x_1+x_2+\ldots+x_N)について部分点解法と同様に求める方針を考えてみましょう。その場合全体の計算量はO(CN\times (\max(A_i,B_i))^N)となってしまい到底間に合いません。そのため\sum^{B_1}_{A_1}\ldots\sum^{B_N}_{A_N}f(x_1+x_2+\ldots+x_N)を一つの塊としてDPで求める必要があります。

部分点解法と同様に、C=C_0,N=N_0のときの\sum^{B_1}_{A_1}\ldots\sum^{B_N}_{A_N}f(x_1+x_2+\ldots+x_N)の値をF(C_0)(N_0)とおきます。すると、F(C_0)(N_0)=(F(C_0-0)(N_0-1))(A_{N_0}^0+(A_{N_0}+1)^0+\ldots+B_{N_0}^0)+(F(C_0-1)(N_0-1))(A_{N_0}^1+\ldots+B_{N_0}^1)+\ldots+(F(C_0-C_0)(N_0-1))(A_{N_0}^{C_0}+\ldots+B_{N_0}^{C_0})が成り立ちます。2

あとはこの関係式を基に実装をすればよいですが、注意点が2つあります。

  1. 愚直に実装すると計算量がO(C^2N\times C\max(A_i, B_i))となってしまうので、累積和を前計算で求める（計算量C\max(A_i, B_i)）ことによりDPの計算量をO(C^2N)に抑える必要があります。
  2. 累積和から部分和を計算する際に減算を行うため、剰余の計算のために正負の場合分けを行う必要があります。

以上2点に注意すればDPにより解を求めることができます。

雑記

  • そもそもDPに帰着できないと部分点を取ることすらままならないですが、C=3,N=2くらいの簡単なケースで式をこねくり回すような道筋しか思いつきません。
    • 同じように式をこねくり回したら満点解法まで辿り着けたので、アプローチとしては間違ってないのかもしれませんね。

  1. 具体的な計算方法は長くなるので重複組合せで検索していただければと思います。↩

  2. x_{N_0}=A_{N_0}=B_{N_0}で部分点の条件を満たすとき、F(C_0)(N_0)=x_{N_0}^0F(C_0-0)(N_0-1)+(x_{N_0}^1F(C_0-1)(N_0-1)+\ldots))=F(C_0)(N_0-1)+x_{N_0}F(C_0-1)(N_0)と変換できるので、部分点解法と同様の関係式となります。↩

AtCoder ABC140 D - Face Produces Unhappiness (Go)

競プロ AtCoder ABC140 D問題 400点 Go

irisruneです。青パフォを出すのはなかなか難しいですね。

問題

atcoder.jp

律儀にシミュレートしようとすると難しく思える問題ですが、解き方は意外と単純です。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

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

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    var n, k int
    fmt.Scan(&n, &k)
    var s string
    fmt.Scan(&s)
    rs := append([]rune(s), 'L')

    count := n
    mode := 'R'
    for i, r := range rs {
        switch {
        case mode == 'R' && r == 'L':
            count--
            if i > 0 && i < n {
                count--
            }
            mode = 'L'
        case mode == 'L' && r == 'R':
            mode = 'R'
        }
    }

    fmt.Println(minInt(n-1, count+(2*k)))
}

結論から書くと、初期状態で幸福である人の数をMとおくと\max(N-1,M+2K)が解となります。計算量はO(1)と言いたいところですが、初期状態で幸福である人の数を調べる処理がボトルネックとなるのでO(N)です。

まずはある人が幸福である条件を整理してみます。問題文では目の前に人がいて、かつ目の前の人が自分と同じ方向を向いている場合幸福であると定義されていますが、目の前に人がいないケースは両端の人にしか発生し得ません。そこで、1番目の人の西隣に東を向いている人を、N番目の人の東隣に西を向いている人を配置すれば、目の前に人がいるかどうか考える必要はありません。当然、追加で配置した人は幸福ではないことに注意が必要です。

次にどのように操作を行えば幸福である人を効率よく増やすことができるか考えます。例えば入力例1について考えてみましょう。入力例1の人の並びは以下の通りです。

LRLRRL

出力例1の解説では(l,r)=(2,5)と選びましたが、(l,r)=(4,5)と選んだ場合を考えてみます。このとき操作後の人の並びは以下の通りです。

LRRRRL

このとき、西から2,3,4番目の人が幸福となり、出力例1と同様の結果が導き出せます。他に、(l,r)=(2,2),(3,3)のときも同様の結果が導き出せます。つまり、LR...RLあるいはRL...LRと表される区間の両端を除いた部分を反転させることにより幸福である人を効率よく増やすことができます。

...で省略された部分の内訳は問いませんが、LR...RLの内訳はすべてR、RL...LRの内訳はすべてLであるとおいても問題ないので以降はこのようにおきます。

幸福である人を効率よく増やすとここまで書いてきましたが具体的に何人ずつ増やすことになるか考えてみましょう。例えばLR...RLの両端を除いた区間を反転させることを考えます。するとLL...LLという並びになるわけですが、...の部分は反転を行ったところで幸福である人の人数は変わりません（これは...の内訳に関わりません）。一方で東側の2人は反転前は幸福でなかったのが反転後は幸福となり、全体で幸福である人の数は2人増えます。RL...LRについても同様です。

つまり操作1回ごとに幸福である人の数は2人増えるわけですが、どのようなケースについてこのような操作が行えなくなるか考える必要があります。実は操作を繰り返して辿り着くケースは次の4通りであることがわかります。

LL...LL

RR...RR

LL...LLRR...RR

RR...RRLL...LL

このうち1つ目と2つ目のケースは、幸福である人の数がN-1となりこれ以上増やせないことがわかります。一方で3つ目と4つ目のケースは1回の操作で1つ目のケースまたは2つ目のケースに遷移させることが可能です。この操作で増える幸福である人の数は1人のみですが、幸福である人の数の上限をN-1と定義しておくことで、2人増えるとみなすことができます。

ここまでの過程により、並んでいる人の人数、初期状態で幸福である人の数、操作可能な回数の3つがわかれば操作後に幸福である人の最大数が求められるようになりました。

最後に初期状態で幸福である人の数の求め方ですが、上記提出コードではRLという部分文字列の出現回数を数えることにより求めています。この部分文字列に相当する人はどちらも幸福ではないため、出現回数を2倍した数が幸福でない人の数となります。ただし両端の人については場合分けをせざるを得ません。序盤に書いたように両端に追加で人を配置して考えたとしても、追加した人は幸福ではないため結局場合分けが必要になってしまいます。

雑記

  • 記事を書いていて気付きましたが、部分文字列の出現回数を数えるだけでよいので上記コードのようなややこしい処理をせずとも初期状態の調査は可能でしたね。
    • stringsパッケージを用いればfor文を使う必要性すらありませんでした。

AtCoder ABC140 C - Maximal Value (Go)

競プロ AtCoder ABC140 C問題 300点 Go

irisruneです。台風の影響により、今週は火・水・金の投稿となります。

問題

https://atcoder.jp/contests/abc140/tasks/abc140_c

B_iからA_iを逆算するにはどうすればいいかという問題です。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

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

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n := nextInt()

    ans := 0
    bPrev := -1
    for i := 0; i < n-1; i++ {
        b := nextInt()
        switch {
        case i == 0:
            ans += b
        default:
            ans += minInt(b, bPrev)
        }
        bPrev = b
    }

    fmt.Println(ans + bPrev)
}

A_iからB_iを求める方法として、問題文でB_i\geq\max(A_i,A_{i+1})が示されています。逆にB_iからA_iを求める方法を考えると、A_i\leq\min(B_{i-1},B_i)となることがわかります。

ここから不等号を等号に置き換えるだけでA_iの最大値を求められますが、A_i(1\leq i\leq N)に対してB_i(1\leq i\leq N-1)であるため、A_0,A_Nについては求め方が異なることに注意が必要です。具体的にはA_0\leq B_1,A_N\leq B_nと置き換える必要があります。

なお、B_{-1},B_N=\inf(\geq 10^5)とおいてB_iの数列の両端に追加すると、A_0,A_nについても他のA_iと同様に求めることができるためコードがより簡潔になります。

雑記

  • 今週は水曜日にABC140-D、金曜日にARC059-E（部分点+満点）を投稿予定です。

AtCoder AGC006 B - Median Pyramid Easy

競プロ AtCoder AGC006 B問題 400点 Go

irisruneです。ABC-F問題の壁は厚いですね。

問題

atcoder.jp

順列をどのように構築すればよいかがわかれば、順列が存在し得るかどうかも自然とわかります。あるいは小規模なケースで試してみるのもよさそうです。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n, x := nextInt(), nextInt()

    if x <= 1 || x >= 2*n-1 {
        fmt.Println("No")
        return
    }

    values := make([]int, 0)
    for v := 2; v < 2*n-1; v++ {
        if v != x {
            values = append(values, v)
        }
    }

    fmt.Println("Yes")
    for i := 0; i < 2*n-1; i++ {
        switch {
        case i == n-2:
            fmt.Println(x)
        case i == n-1:
            switch {
            case x < n:
                fmt.Println(1)
            default:
                fmt.Println(2*n - 1)
            }
        case i == n:
            switch {
            case x < n:
                fmt.Println(2*n - 1)
            default:
                fmt.Println(1)
            }
        default:
            fmt.Println(values[0])
            values = values[1:]
        }
    }
}

直感的に考えると、N-1段目では最小・最大の数（1,2N-1）が存在せず、N-2段目では2,2N-2が存在せず、…といった具合で最終的に1段目にはNしか存在し得ないように思えます。

とはいえそうはならないだろうということも直感的に想像できると思います。例えばN=3で3段目が3,2,1,4,5の場合には2段目の時点で3が存在しません。このとき、2段目は2,2,4となるので1段目は2となります。

ここで先の例について考えると、2段目で同じ数が2回（連続で）現れるように構成するとその数が1段目になるということがわかります。同様に考えると、K+1段目の中央3か所のうち連続する2か所に同じ数が現れる場合K(\gt1)段目の中央3か所のうち連続する2か所に同じ数が現れることがわかります。

つまりN-1段目の中央3か所のうち連続する2か所にxが現れるよう順列を構成すれば1段目にxが入ります。またそのような構成はx=2,3,\ldots,2N-2に対して存在するため、x=1,2N-1を除く場合について順列を構成することができます。

順列の構成方法は様々だと思いますが、上記コードでは以下のようなアルゴリズムで実装しています。

  1. 中央の3か所以外は2,3,\ldots,x-1,x+1,\ldots,2N-2を左から順番に入れる。
  2. 中央の3か所のうち左側はxを入れる。残り2か所は以下のように入れる。
    1. x\lt Nならば中央に1、右側に2N-1を入れる。
    2. x\geq Nならば中央に2N-1、右側に1を入れる。

なおN=2のときはどのように配置しても1段目に2が入るので、上記のアルゴリズムをそのまま用いることができます。

雑記

  • Difficulty1552ですが800点問題が解けました。おそらく来週金曜の記事にすると思います。

AtCoder ABC139 E - League (Go) 失敗例と成功例（嘘解法？）

競プロ AtCoder ABC139 E問題 500点 Go

irisruneです。今週は解説の難しい問題ばかりで少し難儀しますね。

問題

atcoder.jp

実装するだけの問題とみせかけて、アルゴリズムを考える必要がある問題です。

失敗例

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n := nextInt()

    aMat := make([][]int, n)
    for i := range aMat {
        aRow := make([]int, n-1)
        for j := range aRow {
            aRow[j] = nextInt() - 1
        }
        aMat[i] = aRow
    }

    day := 0
    for {
        matched := make(map[int]struct{})
        for i, aRow := range aMat {
            if len(aRow) == 0 {
                continue
            }
            _, exist1 := matched[i]
            if exist1 {
                continue
            }
            _, exist2 := matched[aRow[0]]
            if exist2 {
                continue
            }
            j := aMat[aRow[0]][0]
            if i == j {
                matched[i] = struct{}{}
                matched[aRow[0]] = struct{}{}
                aMat[i] = aMat[i][1:]
                aMat[aRow[0]] = aMat[aRow[0]][1:]
            }
        }
        if len(matched) == 0 {
            for _, aRow := range aMat {
                if len(aRow) > 0 {
                    fmt.Println(-1)
                    return
                }
            }
            fmt.Println(day)
            return
        }
        day++
    }
}

こちらは1日毎に行える試合を求めていく手法です。各選手の試合予定をキューで持っておくと先頭要素が直近で予定された対戦相手となります。そのため、その日の間にマッチングしていない選手同士でキューの先頭要素が互いに対応する2選手について試合を行えると判定できます。あとは試合の存在しない日が発生したらループを止めて出力するだけです。

この手法の何が失敗だったかについてですが、計算量は大会の日数をDとおくとO(ND)となります。一方でD\leq N(N-1)/2のため、全体の計算量はO(N^3)となってしまい流石に厳しいです。例えば以下のような入力例の場合に計算量は最悪となります。

4
2 3 4
1 3 4
1 4 2
1 3 2

成功例

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

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

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n := nextInt()

    aMat := make([][]int, n)
    for i := range aMat {
        aRow := make([]int, n-1)
        for j := range aRow {
            aRow[j] = nextInt() - 1
        }
        aMat[i] = aRow
    }

    days := make([]int, n)
    for {
        matched := false
        for i := range aMat {
            for {
                if len(aMat[i]) == 0 {
                    break
                }
                other := aMat[i][0] // len(aMat[other]) > 0
                if i != aMat[other][0] {
                    break
                }
                day := maxInt(days[i], days[other]) + 1
                days[i], days[other] = day, day
                aMat[i], aMat[other] = aMat[i][1:], aMat[other][1:]
                matched = true
            }
        }
        if !matched {
            for _, aRow := range aMat {
                if len(aRow) > 0 {
                    fmt.Println(-1)
                    return
                }
            }
            ans := 0
            for _, d := range days {
                ans = maxInt(ans, d)
            }
            fmt.Println(ans)
            break
        }
    }
}

こちらは各選手に対して試合日程を決定する手法です。ある選手に対して試合を行える限り行うという処理を全選手に対して行い、1試合でも行えばまた全選手に対して処理を行うということを繰り返します。終了条件は失敗例の方と似ていて、試合を行う選手が一人も発生しない場合です。

この手法の計算量はO(N^2)になると思って実装したのですが、理論的に証明できていない状態です。N人の選手を一通りチェックすると少なくとも1試合は行うことになりますが、これだけでは結局計算量はO(N^3)になりそうです。考え直してみると嘘解法の可能性が高い気がします。

雑記

  • 公式解説を見ると全然思いつきもしない手法だったので、おそらく実装力よりアルゴリズム力の方が要求される問題でしたね。

AtCoder ABC139 D - ModSum (Go)

競プロ AtCoder ABC139 D問題 400点 Go

irisruneです。暑さも多少和らいで雨も収まり過ごしやすくなったように思います。

問題

atcoder.jp

理論立てて考えないと、あまりに単純な解法すぎて戸惑うかもしれません。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n := nextInt()
    fmt.Println((n * (n - 1)) / 2)
}

結論から記すと、i\lt NのときP_i=i+1、P_N=1とおくことで\sum^N_1M_i=1+2+\ldots+(N-1)+0=N(N-1)/2となり、これが最大値です。

各M_iを最大化することを考えると、M_i=iとおくのが直感的によさそうに思えます。ただしM_Nに限ってはM_N\lt Nであることが推察できるのでとりあえずP_N=1,M_N=0とおきます。実はこれだけで上記の解になるわけですが、この道筋では最大値であることを証明するのは困難だと思います。

証明は公式解説にもある通りですが、まずP_i=1,2,\ldots,Nに対してM_i\leq0,1,\ldots,(N-1)であることから解の上界が求められ、それが上記の解と一致するため最大値であることが示せます。

雑記

  • 今週の予定は水曜にE問題、金曜に過去問（F問題が解けなければ）の予定です。

AtCoder ABC125 C - GCD on Blackboard (Go)

競プロ AtCoder ABC125 C問題 300点 Go

irisruneです。先週のコンテストはC問題もD問題も難しかったので過去問（リベンジ）回です。

問題

atcoder.jp

累積GCDなるフレーズが一時トレンド入りしたりしました。累積和と微妙に扱いが異なる点に注意が必要です。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func GCD(a, b int) int {
    if a < b {
        a, b = b, a
    }
    if a%b == 0 {
        return b
    }
    return GCD(b, a%b)
}

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

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n := nextInt()
    aArray := make([]int, n)
    for i := range aArray {
        aArray[i] = nextInt()
    }

    leftCumGcd, rightCumGcd := make([]int, n), make([]int, n)
    leftCumGcd[0] = aArray[0]
    for i := 1; i < n; i++ {
        leftCumGcd[i] = GCD(leftCumGcd[i-1], aArray[i])
    }
    rightCumGcd[n-1] = aArray[n-1]
    for i := n - 2; i >= 0; i-- {
        rightCumGcd[i] = GCD(rightCumGcd[i+1], aArray[i])
    }

    ans := 1
    for i := 0; i < n; i++ {
        switch {
        case i == 0:
            ans = maxInt(ans, rightCumGcd[i+1])
        case i == n-1:
            ans = maxInt(ans, leftCumGcd[i-1])
        default:
            ans = maxInt(ans, GCD(leftCumGcd[i-1], rightCumGcd[i+1]))
        }
    }
    fmt.Println(ans)
}

N\geq2より、選んだ整数を他のいずれかの整数と同じ値に書き換えることができるため、整数を書き換える操作はその整数を除外する操作に置き換えることができます。つまり各整数についてそれを除外した残りの値の最大公約数を求めて最大値を取ればよいです。

ここで最大公約数の性質について考えてみると、

  1. 入力に2つの整数をとり、出力として1つの整数を返す。
  2. 結合法則（と交換法則）が成り立つ。

という面から加算や乗算と同じような性質を持つことがわかります。ここから累積最大公約数（累積GCD）を考えるとよさそうに思えます。

ただし、累積和（加算）に対する減算、累積積（乗算）に対する除算といったものが累積GCDには存在しません。つまり単純な（一方向の）累積GCDからは部分GCDを求めることができません。

実は両端から（両方向に）累積GCDを計算すると上手くいきます。どういうことかというと、1つを除いた残りの整数について最大公約数を求めればよいため、両端からの累積GCDに対して最大公約数を計算するという手法を使うことができます。

雑記

  • 今回は雑記のネタがないです。