2019-11-15

AtCoder AGC 007 B - Construct Sequences (Go)

irisruneです。最近あまりAtCoderに時間を割けていません。

問題

3つ目までの条件を満たしつつ4つ目の条件を満たすためにはどうすればよいか考える問題です。

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)
    n := nextInt()
    order := make([]int, n)
    for o := 1; o <= n; o++ {
        oi := nextInt()
        order[oi-1] = o
    }
    aArray, bArray := make([]int, n), make([]int, n)
    for i, o := range order {
        aArray[i] = n*i + o
        bArray[i] = n*(n-i-1) + o
    }
    for i, a := range aArray {
        fmt.Print(a)
        switch {
        case i == n-1:
            fmt.Println()
        default:
            fmt.Print(" ")
        }
    }
    for i, b := range bArray {
        fmt.Print(b)
        switch {
        case i == n-1:
            fmt.Println()
        default:
            fmt.Print(" ")
        }
    }
}

まず3番目までの条件を満たすことを考えます。それ自体は簡単で、例えば $a_1=1,a_2=2,\ldots,a_N=N,b_1=N,b_2=N-1,\ldots,b_N=1$ と置くことで条件を満たすことができます。

このとき $a_1+b_1=a_2+b_2=\ldots=a_N+b_N=N+1$ となるわけですが、3番目までの条件を満たしながら4番目の条件を満たそうとすると、数列の複数の要素の値を同時に変更する必要があります。

そこで、 $a_1=1,a_2=N+1,\ldots,a_N=N(N-1)+1$ と置くと、要素の値を1つずつ変えながら全ての条件を満たすことができるようになります。上記提出コードでは $a_i,b_i$ の両方に対して初期値の間隔を空けていますが、どちらかに対して処理を行えば問題なく解けると思います。計算量は $O(N)$ です。

2019-11-13

AtCoder 第二回全国統一プログラミング王決定戦予選 B - Counting of Trees （再解説） (Go)

競プロ AtCoder 第二回全国統一プログラミング王決定戦予選 B問題 300点 Go

irisruneです。前回扱った問題のアルゴリズム面についてもう少し解説したいと思います。

問題リンクと提出コードは前回記事を参照してください。

ami-atcoder.hatenablog.com

例えば以下のような入力について考えます。

6
0 1 1 2 2 3

すると、次のような木は条件を満たします。

f:id:amifiable:20191113160224p:plain

ここで他にどのような木が条件を満たすかについて考えると、頂点1を根として頂点1から距離が短い順番に見ることで以下のように考えられます。

頂点1との距離が0の頂点の配置は1通りである。
1. 頂点1との距離が0の頂点は頂点1ただ1つのみ存在することが木の存在条件である。
頂点1との距離が1の頂点の親は頂点1以外あり得ないので、配置は1通りである。
頂点1との距離が2の頂点は頂点1との距離が1の頂点を親に持つことができるため、配置は2通りである。
1. 頂点1との距離が2の頂点は2つ存在するため、それぞれ2通りとなり全体で4通りとなる。
頂点1との距離が3の頂点は頂点1との距離が2の頂点を親に持つことができるため、配置は2通りである。

以上より、各頂点について親となる頂点の候補の数（頂点1との距離が自身より1小さい頂点の数）がそれぞれの頂点の配置のパターン数となるため、全頂点についてその積をとれば答えを求めることができます。

雑記

ここしばらく忙しいのもあり、過去問を扱うことになるかもしれません。

2019-11-11

AtCoder 第二回全国統一プログラミング王決定戦予選 B - Counting of Trees (Go)

競プロ AtCoder 第二回全国統一プログラミング王決定戦予選 B問題 300点 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 MOD = 998244353

func powInt(x, y int) int {
    ret := 1
    for i := 0; i < y; i++ {
        ret *= x
        ret %= MOD
    }
    return ret
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n := nextInt()
    depth := make([]int, n)
    d := nextInt()
    if d != 0 {
        fmt.Println(0)
        return
    }
    depth[d]++
    for i := 1; i < n; i++ {
        d := nextInt()
        depth[d]++
    }
    if depth[0] > 1 {
        fmt.Println(0)
        return
    }
    ans := 1
    dPrev := 1
    for _, d := range depth {
        switch {
        case d == 0:
            dPrev = 0
            continue
        case dPrev == 0:
            fmt.Println(0)
            return
        default:
            ans *= powInt(dPrev, d)
            ans %= MOD
            dPrev = d
        }
    }
    fmt.Println(ans)
}

まず条件を満たす木が存在する場合について考えると、基本的な解法は以下の通りです。

頂点1との距離ごとに頂点数をカウントする。
から頂点1との距離の最大値まで順番に見て、以下の数値をそれぞれ掛け合わせる。
1. （距離 $i-1$ の頂点数）の（距離 $i$ の頂点数）乗した値。
掛け合わせた後の値が求める解になる。

次に条件を満たす木が存在しない場合について考えます。それは以下の場合です。

頂点1と頂点1の距離が0でない。
頂点1と頂点1以外の頂点との距離が0である。
頂点1との距離 $i\geq1$ の頂点が存在し、距離 $i-1\geq0$ の頂点が存在しない。

このうち3.については、上記の解法のように距離の最大値を記録しておくことで自然と解消されます（提出コードでは個別に条件分岐させています）。残り1.と2.については個別に条件分岐させる必要はありますがそれほど難しくはありません。

以上のようにして解を求めることができます。全体の計算量は $O(N)$ となります。

雑記

C問題がかなり難しいようなのでD問題が解ければ（解説ACでもある程度わかれば）それを、厳しければ過去問を扱う予定です。
- 今回の記事を見返してみると解法のとっかかりについてノータッチなので、その辺りの説明をするかもしれません。

2019-11-08

AtCoder AGC 019 B - Reverse and Compare (Go)

競プロ AtCoder AGC019 B問題 500点 Go

irisruneです。GoのLanguage Owner入りをのんびり目指していきたいです。

問題

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 main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    s := nextStr()
    n := len(s)
    cnt := make(map[rune]int)
    for _, r := range s {
        _, ok := cnt[r]
        switch {
        case ok:
            cnt[r]++
        default:
            cnt[r] = 1
        }
    }

    ans := 1 + (n * (n - 1) / 2)
    for _, c := range cnt {
        ans -= c * (c - 1) / 2
    }
    fmt.Println(ans)
}

両端の文字が同じ部分文字列を反転させることを考えます。部分文字列の長さが3以上であるとき、反転の結果生まれる文字列は両端の文字を除いた部分文字列を反転させた結果と同じ文字列となります。一方部分文字列の長さが2以下であるときは反転の結果生まれる文字列は元の文字列と同じ文字列となります。よって、両端の文字が同じ部分文字列は操作対象から除外していいケースということになります。

そのため、文字列から任意の2文字を取り出したとき両端の文字が同じとなる組み合わせの数を全体の組み合わせの数から引くことにより答えを求めることができます。同じ2文字を取り出す組み合わせ数は、文字列を構成する各文字種についてそれぞれ何文字存在するかをカウントすることで求めることができます。そのため、全体の組み合わせ数に反転操作を1回も行わない場合を含むことに気をつければ問題を解くことができます。計算量は $O(|S|)$ となります。

ところで、両端の文字が違う部分文字列の反転によって生まれる文字列は全て違う文字列になることを証明していませんが、簡単な例で操作をしてみることで直感的には示せるので、問題を解くだけならそれでよいと思います（厳密な証明は公式解説でされています）。

雑記

今週は企業コンテストが土曜日にあるので忘れずに参加したいです。

2019-11-06

AtCoder AGC 040 A - >< (Go)

競プロ AtCoder AGC040 A問題 300点 Go

irisruneです。今週のコンテストは1完でまた水パフォでした。

問題

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 main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    s := nextStr()
    ans := 0
    mode := '>'
    span, peak := 0, 0
    for _, r := range s {
        switch {
        case r == mode:
            span++
        case r == '>':
            peak = span
            ans += (span * (span + 1)) / 2
            span = 1
            mode = r
        case peak >= span:
            ans += (span * (span - 1)) / 2
            span = 1
            mode = r
        case peak < span:
            ans += (span - peak)
            ans += (span * (span - 1)) / 2
            span = 1
            mode = r
        }
    }
    switch {
    case mode == '<':
        ans += (span * (span + 1)) / 2
    case peak >= span:
        ans += (span * (span - 1)) / 2
    case peak < span:
        ans += (span - peak)
        ans += (span * (span - 1)) / 2
    }
    fmt.Println(ans)
}

簡単なケースについて各 $A_i$ の最小値を考えてみます。例えば<<<>>という入力に対しては、 $0,1,2,3,1,0$ となり、一方で<<>>>という入力に対しては、 $0,1,3,2,1,0$ となります。ここから考えると、各要素の最小値について以下のように示せます。

『要素の左側が>あるいは数列の左端』かつ『要素の右側が<あるいは数列の右端』である場合、最小値は0となる。
『要素の左側が>あるいは数列の左端』かつ『要素の右側が>』である場合、最小値は右隣の要素の最小値より1大きな値となる。
『要素の左側が<』かつ『要素の右側が<あるいは数列の右端』である場合、最小値は左隣の要素の最小値より1大きな値となる。
『要素の左側が<』かつ『要素の右側が>』である場合、最小値は左隣の要素の最小値と右隣の要素の最小値とで大きい方の値より1大きな値となる。

このうち1.から3.までは簡単に求められ、4.も値を一時的に記憶しておくなどすれば求めることができます。計算量は $O(N)$ です。

雑記

公式解説にあるように、『要素の左側に連続する<の数』と『要素の右側に連続する>の数」とで大きい方の値を取ると、上記1.から4.までの性質をすべて包含するためより簡潔に求めることができます。
- ここに気づくことができればABC-C問題相当と言えるかもしれませんが、一般的に見てABC-D問題相当くらいの難易度になると思います（6問形式のABC基準です）。

2019-11-01

AtCoder AGC 032 B - Balanced Neighbors (Go)

競プロ AtCoder AGC032 B問題 700点 Go

irisruneです。気づけばもう11月となり、今年の終わりも近づいてきました。

問題

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 main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n := nextInt()
    adj := make([]map[int]struct{}, n+1)
    for i := 1; i < n+1; i++ {
        adj[i] = make(map[int]struct{}, n)
        for j := 1; j < n+1; j++ {
            if i == j {
                continue
            }
            adj[i][j] = struct{}{}
        }
    }

    m := n
    if n%2 == 1 {
        m = n - 1
    }
    for i := 1; i < m-i+1; i++ {
        delete(adj[i], m-i+1)
        delete(adj[m-i+1], i)
    }

    k := 0
    for i := 1; i < n+1; i++ {
        k += len(adj[i])
    }
    fmt.Println(k / 2)
    for i := 1; i < n+1; i++ {
        for j := range adj[i] {
            if i < j {
                fmt.Println(i, j)
            }
        }
    }
}

このような問題は小さいケースで試行することで規則性を導き出すアプローチを取るのがよいです。例えば $N=4,5$ について条件を満たすグラフを考えると以下のようなグラフになります。

f:id:amifiable:20191101120029p:plain f:id:amifiable:20191101120044p:plain

間に辺を持たない頂点同士の集合について考えると、図で示すように高々2つの頂点からなる集合が構成されます。また、全ての頂点集合について集合内の頂点のラベルの和が等しくなることがわかります。

この性質より、以下のようにして問題を解くことができます。

全体を完全グラフとおく。
グラフの頂点集合を高々２つの頂点からなる頂点集合に分割する。分割の方法はの偶奇による。
1. $N$ が偶数のときは、集合内の頂点のラベルの和を $N+1$ とおく。
2. $N$ が奇数のときは、集合内の頂点のラベルの和を $N$ とおく。
各頂点集合について、集合内の頂点間の辺を削除する。

計算量は完全グラフの構成に $O(N^2)$ 、辺の削除に $O(N)$ かかるので全体としては $O(N^2)$ となり、十分間に合います。

雑記

最近はGo1.6用の環境構築も兼ねてdocker周りで色々していることが多いです。

2019-10-30

AtCoder E - Gluttony 解説AC (Go)

競プロ AtCoder ABC144 E問題 500点 Go

irisruneです。AtCoderの数学問題は注目を集めやすい印象です。

問題

atcoder.jp

大きなポイントが2つあり、どちらが欠けても上手くいかない問題です。

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
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n, k := nextInt(), nextInt()
    aArray, fArray := make([]int, n), make([]int, n)
    for i := range aArray {
        aArray[i] = nextInt()
    }
    sort.Sort(sort.IntSlice(aArray))
    for i := range fArray {
        fArray[i] = nextInt()
    }
    sort.Sort(sort.Reverse(sort.IntSlice(fArray)))

    min, max := 0, fArray[0]*aArray[n-1]
    for min < max {
        x := (min + max) / 2
        kRemain := k
        for i := range aArray {
            require := aArray[i] - (x / fArray[i])
            if require > 0 {
                kRemain -= require
            }
        }
        switch {
        case kRemain >= 0:
            max = x
        case kRemain < 0:
            min = x + 1
        }
    }
    fmt.Println(min)
}

まずは、どのようにメンバーを割り当てるかについて考える必要があります。直感的にはメンバーの消化コストを昇順に、料理の食べにくさを降順に並べてそれぞれの順番通りに対応させればよさそうで、実際そのような割り当てが最適となります。詳しい証明は公式解説にありますが、任意の割り当て方から損のないように最適な割り当て方に変換することが可能なためです。

しかし、最適な修行の割り振り方を求めることは簡単ではありません。直感的には最も完食に時間のかかるメンバーについて修行を行うことを繰り返せばコンテストの成績を最適にすることができそうですが、この方法は少なく見積もっても修行回数分の計算量がかかってしまいます。これは例えヒープを用いたとしても覆らないため、最適解を直接求めることはできなさそうです。

そこで、成績を $x$ 秒以内にするために必要な修行回数を求めることを考えてみます。すると、修行回数は計算量 $O(N)$ で求めることができ、 $K$ と比較することで成績を $x$ 秒以内にすることができるか判定することができます。つまり、下限値を $0$ 、上限値を適当な値（ $A_i,F_i$ それぞれの最大値の積がよさそうです）とおいて二分探索を行うことで、達成できる成績の最適値が求められます。このとき全体の計算量は $O(N\log(\max A_iF_i))$ となり十分間に合います。

雑記

コンテスト本番では成績から修行回数を求め二分探索をするという発想に至らず、解くことができませんでした。
- Difficultyはそれほど高くなかったので精進不足なのだと思います。
- 解説PDFではメンバーの割り当て9割、二分探索1割といった配分だったので驚きました。

2019-10-28

AtCoder ABC 144 D - Water Bottle (Go)

競プロ AtCoder ABC144 D問題 400点 Go

irisruneです。コンテストはE問題の解法がどうにも思いつきませんでしたが、水パフォは出ました。

問題

atcoder.jp

直球の数学問題ですが、D問題だけあって割と面倒な問題です。

package main

import (
    "bufio"
    "fmt"
    "math"
    "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)
    a, b, x := nextInt(), nextInt(), nextInt()
    v0 := a * a * b
    v1 := v0 - x
    switch {
    case v1 <= x:
        fmt.Println(math.Atan((float64(v1)*2.0)/float64(a*a*a)) * (180.0 / math.Pi))
    case v1 > x:
        fmt.Println(90.0 - (math.Atan((float64(x)*2.0)/float64(a*b*b)) * (180.0 / math.Pi)))
    }
}

図を描かないことには始まらない問題なので、まずは図を描いてみます。既にネタバレが見えていますが、すぐに思い浮かぶのは左側の図になると思います。

f:id:amifiable:20191028135330p:plain

この直方体の水筒において、横の辺の長さが $a$ 、縦の辺の長さが $b$ 、描写上省略されている奥行きは $a$ です。また、水色の領域は水の入っている領域のため体積が $x$ です。描写上水筒そのものではなく水位を傾けて表現していますが、水位と上辺の成す角度が求める角度となります。

ここで左側の図について考えると、水筒の体積 $v_0$ や求める角度 $\theta$ について以下の等式が成り立ちます。

$v_0 = a^2b, v_0 - x = a(a\tan\theta)a/2 \Rightarrow \theta = \arctan(2(a^2b - x) / a^3)$

これより角度を直接求めることができますが、図を2つ示していたことからわかるように場合分けが必要となります。場合分けの条件は $x$ が $v_0/2$ より大きいか小さいかです。大きい場合は前述の数式で解くことができ、小さい場合は $\theta'=\arctan(2(a^2b-x)/ab^2)$ で解くことができます（正確には90°から引いた角度が求める角度となります）。

雑記

奥行きを省略した図を描いて考える場合、水の体積 $x$ を面積 $x/a$ に置き換えた方が考えやすいかもしれません。
数学問題は検索でどうにかなることも多いですが、この問題については三角関数の扱い方がわかっていないと検索もままならない印象です。
- 弧度法とラジアンの変換まで求められているのでやはり数学的知識の比重が大きめだと思います。
公式解説によれば角度を直接求めるより2分法を用いる方が素直な解き方らしいです。いずれにせよ三角関数を用いる必要はあります。

2019-10-25

AtCoder ARC 074 / ABC 062 C - Chocolate Bar (Go)

競プロ AtCoder ARC074 ABC062 C問題 400点 Go

irisruneです。最近台風の接近が多く関東の天気は荒れがちですね。

問題

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
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    h, w := nextInt(), nextInt()
    ans := h * (((w + 2) / 3) - (w / 3))
    if (((h+2)/3)-(h/3))*w < ans {
        ans = (((h + 2) / 3) - (h / 3)) * w
    }
    for hi := 0; hi <= h; hi++ {
        blocks := []int{hi * ((w + 1) / 2), hi * (w / 2), (h - hi) * w}
        sort.Sort(sort.IntSlice(blocks))
        if blocks[2]-blocks[0] < ans {
            ans = blocks[2] - blocks[0]
        }
    }
    for wi := 0; wi <= w; wi++ {
        blocks := []int{((h + 1) / 2) * wi, (h / 2) * wi, h * (w - wi)}
        sort.Sort(sort.IntSlice(blocks))
        if blocks[2]-blocks[0] < ans {
            ans = blocks[2] - blocks[0]
        }
    }
    fmt.Println(ans)
}

板チョコを3分割する方法としては次の2つが考えられます。

縦あるいは横に平行に3分割する。
縦あるいは横に2分割し、片方を垂直に（横あるいは縦に）2分割する。

縦に分割する場合を求めれば横に分割する場合も同様に求められるので、縦に分割する場合を考えます。まずは1.について、横の長さによって以下のように場合分けができます。

横の長さが3の倍数であれば、分割した板チョコはすべて同じ大きさ（面積の最大値と最小値との差は0）。
横の長さが3の倍数でなければ、分割した板チョコの面積の最大値と最小値との差は縦の長さに等しい。
1. 分割した板チョコの縦の長さはそれぞれ等しく、横の長さの差は1であるため。

よって計算量 $O(1)$ で求めることができます。

次に2.について、こちらは縦に2分割する位置 $O(W)$ 通りについて考えます。すると分割された片方のチョコを横に分割する方法としてはなるべく均等になるように分割すればよいので、面積の最大値と最小値との差は計算量 $O(1)$ で求めることができます。そのため、全体の計算量としては $O(W)$ となります。

縦と横を反転しても同様に求められるので、最終的な計算量としては $O(H+W)$ となり十分間に合います。特に2.の計算について全探索を行うと計算量は $O(HW)$ となってしまいますが、なるべく均等に分割すればよいという点に着目することで計算量を削減することができます。

雑記

もう少し詰めれば、2.の計算について最初の分割を行う方法を絞り込むことにより計算量を削減することができるかもしれません。

2019-10-23

AtCoder ABC 143 E - Travel by Car (Go)

競プロ AtCoder ABC143 E問題 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 = 10000000000

type info struct {
    supply int
    fuel   int
}

type infoes []info

func less(info1, info2 info) bool {
    if info1.supply != info2.supply {
        return info1.supply < info2.supply
    }
    return info1.fuel >= info2.fuel
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n, m, l := nextInt(), nextInt(), nextInt()
    adj := make([][]int, n)
    for i := range adj {
        adj[i] = make([]int, n)
        for j := range adj[i] {
            if i != j {
                adj[i][j] = INF
            }
        }
    }
    for k := 0; k < m; k++ {
        a, b, c := nextInt(), nextInt(), nextInt()
        if c <= l {
            adj[a-1][b-1], adj[b-1][a-1] = c, c
        }
    }

    dist := make([]infoes, n)
    for i := range dist {
        dist[i] = make(infoes, n)
        dist[i][i] = info{0, l}
        for j := range dist[i] {
            if i != j {
                dist[i][j] = info{INF, 0}
            }
        }
        remain := make(map[int]struct{})
        for j := 0; j < n; j++ {
            remain[j] = struct{}{}
        }
        for len(remain) > 0 {
            u := -1
            for k := range remain {
                if u == -1 || less(dist[i][k], dist[i][u]) {
                    u = k
                }
            }
            delete(remain, u)
            for v, a := range adj[u] {
                if a > l {
                    continue
                }
                next := dist[i][u]
                if next.fuel < a {
                    next.supply++
                    next.fuel = l
                }
                next.fuel -= a
                if less(next, dist[i][v]) {
                    dist[i][v] = next
                }
            }
        }
    }

    q := nextInt()
    for p := 0; p < q; p++ {
        s, t := nextInt(), nextInt()
        ans := dist[s-1][t-1].supply
        switch {
        case ans == INF:
            fmt.Println(-1)
        default:
            fmt.Println(ans)
        }
    }
}

ある町を始点としたときに各町への最短距離をどのように表せばよいか考えてみます。このとき補給回数と燃料タンクの残量とのセットを距離として用いるのがよさそうです。すると、ある町から各町へ向かうときの補給回数の最小値がダイクストラ法により求められます。あとはすべての町を始点にしてダイクストラ法をそれぞれ適用すれば任意の2つの町の組み合わせについて補給回数の最小値が求められます。

ダイクストラ法1回の計算量は道の数が $O(N^2)$ なので優先度付きキューを使おうと使うまいと $O(N^2)$ になります。 $Q$ が $O(N^2)$ であることを考慮すると、全体の計算量は $O(N^3)$ となります。

雑記

公式解法はワーシャルフロイド法を用いるという観点で見れば非常にスマートだと思います。
- 上記の最短距離の考え方ではワーシャルフロイド法が適用できないので、ダイクストラ法でゴリ押すしかありませんでした。

2019-10-21

AtCoder ABC 143 D - Triangles (Go)

競プロ AtCoder ABC143 D問題 400点 Go

irisruneです。コンテストは当日になってうっかり存在を忘れてしまいました。

問題

atcoder.jp

3重ループは通りませんが2重ループなら通る制約設定が重要です。

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
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n := nextInt()
    lArray := make([]int, n)
    for i := range lArray {
        lArray[i] = nextInt()
    }
    sort.Sort(sort.IntSlice(lArray))

    ans := 0
    for i := 0; i < n-2; i++ {
        for j := i + 1; j < n-1; j++ {
            kLeft := sort.SearchInts(lArray[j+1:], lArray[j]-lArray[i])
            kRight := sort.SearchInts(lArray[j+1:], lArray[j]+lArray[i])
            ans += kRight - kLeft
        }
    }
    fmt.Println(ans)
}

2辺を選んだときに残り1辺の候補数がいくらか確認すればよいですが、愚直に解くと3重ループになってしまい間に合いません。そこで残り1辺の候補数を2分探索で求めるようにすれば、全体の計算量が $O(N^2\log N)$ となり間に合います。

雑記

今週のE問題はグラフ問題なのでできれば解いておきたいと思います。

2019-10-18

AtCoder AGC 024 C - Sequence Growing Easy (Go)

競プロ AtCoder AGC024 C問題 700点 Go

irisruneです。AtCoder用の手元環境をもう少し整備したい思いです。

問題

atcoder.jp

700点の割には単純な問題だと思います。

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)
    n := nextInt()

    ans := 0
    aPrev := 0
    for i := 0; i < n; i++ {
        a := nextInt()
        switch {
        case a > i || a > aPrev+1:
            fmt.Println(-1)
            return
        case a == aPrev+1:
            ans++
        default:
            ans += a
        }
        aPrev = a
    }
    fmt.Println(ans)
}

入力例1について、0 1 / 1 2のように1ずつ増加する部分列で分解してみます。すると、後者の部分列を2回の操作で生成した後に、前者の部分列を1回の操作で生成するという手順が見えてきます。このように、1ずつ増加する部分列を後ろから組み上げていくことで全体の数列を $A$ と等しくすることができます。

ここで考えるのは以下の2点です。

どのような場合に $A$ と等しくすることができるか。
操作回数は最小で何回になるか。

$A$ と等しくすることができない場合について考えると、数列0 1 2 ...の各要素と同じ位置でより大きな値が入る場合が挙げられます。また連続する2つの要素について、前の要素より後の要素が2以上大きい場合にも $A$ と等しくすることができません。逆にそれ以外の場合は $A$ と等しくすることができます。

残った操作回数の最小値は以下のようにして求めることができます。

要素を前から順番に見て、前の要素より値がちょうど1大きい場合は回数を1増やす。
前の要素と同じかそれ以下の値の場合は、その値の数だけ回数を増やす。

雑記

またコンテスト参加していない期間が長かったので今週のコンテストは出られるように準備をしておきます。

2019-10-16

AtCoder ABC 080 D - Recording (Go)

競プロ AtCoder ABC080 D問題 400点 Go

irisruneです。先週はコンテストがなかったので今週は過去問を扱います。

問題

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
}

type event struct {
    time    int
    mode    string
    channel int
}

type events []event

func (e events) Len() int {
    return len(e)
}

func (e events) Swap(i, j int) {
    e[i], e[j] = e[j], e[i]
}

func (e events) Less(i, j int) bool {
    return e[i].time < e[j].time
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n, _ := nextInt(), nextInt()
    var events events = make([]event, n*2)
    for i := 0; i < n; i++ {
        s, t, c := nextInt(), nextInt(), nextInt()
        events[i*2] = event{s*2 - 1, "start", c}
        events[i*2+1] = event{t * 2, "end", c}
    }
    sort.Sort(events)
    ans := 0
    channels := make(map[int]int)
    for _, e := range events {
        switch {
        case e.mode == "start":
            _, ok := channels[e.channel]
            switch {
            case ok:
                channels[e.channel]++
            default:
                channels[e.channel] = 1
                if len(channels) > ans {
                    ans = len(channels)
                }
            }
        case e.mode == "end":
            channels[e.channel]--
            if channels[e.channel] == 0 {
                delete(channels, e.channel)
            }
        }
    }
    fmt.Println(ans)
}

直感的に、各時刻について同時に放送される番組数が最大となるときを考えると、そのときの番組数が解となります。しかし時刻の最大値 $T'\leq10^5$ であるため、計算量 $O(NT')$ となるようなアルゴリズムでは実行時間が足りません。そこで、番組の開始と終了をそれぞれイベントとして考えると、イベントを時刻でソートした配列について先頭から順番に見ていくことで同時に放送される番組数の推移を追うことができます。イベント数は $2N$ であるため実行時間的にも問題ありません。

具体的なアルゴリズムとしては、以下の通りになります。

番組の開始イベントについては発生時刻を $2s_i-1$ 、終了イベントについては発生時刻を $2t_i$ とおく。
$2N$ 個のイベントを発生時刻でソートした配列をおく。
配列の先頭からチェックし、開始イベントであれば増やし、終了イベントであれば番組数を減らす。
番組数の推移から最大値を求める。

しかしこれではWAとなってしまいます。どういうことかといえば、ここまで~~不要だと思っていたので~~着目していなかったチャンネルが関係してきます。問題文には以下のように示されています。

また、録画機は、あるチャンネルの時刻 $S$ から $T$ までを録画するとき、時刻 $S-0.5$ から時刻 $T$ までの間、他のチャンネルの録画に使うことができません。（ただし時刻 $S-0.5$ を含み、時刻 $T$ を除く）

よく読むと他のチャンネルの録画に使うことができないとしか書いておらず、同じチャンネルの録画に使うことはできるのです。実は入出力例1でも、時刻 $7$ から $8$ までの番組と時刻 $8$ から $12$ までの番組を同じ録画機で録画できることが示されています。つまり求めるべきは同時に放送される番組の数ではなく、同時に放送されるチャンネルの数となります。それを踏まえ上記アルゴリズムに多少の変更を加えれば解くことができました。

雑記

入力例1がコーナーケースになりきれていなかったのでサンプルケースは弱かったですが、説明はされていたのでちゃんと読んでいないのが悪いだけでした。

2019-10-11

AtCoder AGC 039 B - Graph Partition (Go)

競プロ AtCoder AGC039 B問題 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
}

func solve(n, iMin int, adj [][]int) int {
    vertexes := make([]int, n)
    count := 1
    vertexes[iMin] = count
    queue := make([]int, 0)
    queue = append(queue, iMin)
    for {
        for len(queue) > 0 && vertexes[queue[0]] == count {
            u := queue[0]
            queue = queue[1:]
            for v, a := range adj[u] {
                switch {
                case a == 0:
                    continue
                case vertexes[v] == 0:
                    vertexes[v] = count + 1
                    queue = append(queue, v)
                case vertexes[v] == count-1 || vertexes[v] == count+1:
                    continue
                default:
                    return -1
                }
            }
        }
        if len(queue) == 0 {
            break
        }
        count++
    }
    return count
}

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

    adj := make([][]int, n)
    for i := range adj {
        adj[i] = make([]int, n)
        s := nextStr()
        for j, r := range s {
            if r == '1' {
                adj[i][j] = 1
            }
        }
    }

    /*
        divMin := n
        iMins := make([]int, 0)
        for i := range adj {
            div := 0
            for _, a := range adj[i] {
                div += a
            }
            switch {
            case div < divMin:
                divMin = div
                iMins = []int{i}
            case div == divMin:
                iMins = append(iMins, i)
            }
        }
    */

    ans := -1
    /*
        for _, iMin := range iMins {
            cnt := solve(n, iMin, adj)
            if cnt > ans {
                ans = cnt
            }
        }
    */
    for i := 0; i < n; i++ {
        cnt := solve(n, i, adj)
        if cnt > ans {
            ans = cnt
        }
    }
    fmt.Println(ans)
}

まず、条件を満たす分割が可能となるのはグラフが2分グラフである場合のみです。何故なら、 $V_1,V_3,\ldots$ の各集合間を結ぶ辺は存在せず、また各集合内の頂点を結ぶ辺も存在しないことが条件となるためです（ $V_2,V_4,\ldots$ についても同様のことがいえます）。

分割の最大数は解説の通りグラフの直径をワーシャルフロイド法などにより求めてしまえば簡単に求めることができます。今回は2分グラフの判定法を流用する形で求めましたが、思い違いにより手こずってしまいました。

最初は次数が最小の任意の頂点のみからなる集合 $V_1$ を始点とすれば最大の分割が得られると考えていました。しかしその提出はWAでした。そのため次に次数が最小の頂点が複数ある場合、それぞれを $V_1$ とおいたときの分割数の最大値を求めることにしましたが、これもまたWAでした。実は以下のようなグラフがコーナーケースになってしまいます。

f:id:amifiable:20191011133834p:plain

このグラフにおいて次数が最小の頂点は $8$ ですが、 $V_1=\{8\}$ とおくと分割数は4となります。しかし $V_1=\{1\},\{4\},\{7\}$ のいずれかの場合は分割数が5となります。

結局最大の分割を求めるために頂点の次数を考える意味はなく、しかもすべての頂点の次数が同じ場合はすべての頂点を始点とおいて分割数を求める必要があるため計算量は精々定数倍削減できる程度です。

そのため、次数を考慮せずすべての頂点を始点とおいて分割数を求めたところ無事ACとなりました。計算量としてはワーシャルフロイド法を用いた場合と同様に $O(N^3)$ となります。

雑記

台風には気を付けて3連休を過ごしましょう。

2019-10-09

AtCoder AGC 039 A - Connection and Disconnection (Go)

競プロ AtCoder AGC039 A問題 300点 Go

irisruneです。流石に残暑も落ち着いてきた感じです。

問題

atcoder.jp

単純に見えて意外と考えることが多い問題です。

package main

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

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 culculate(s string) int {
    rs := []rune(s)
    cnt := 0
    for i := 1; i < len(rs); i++ {
        if rs[i] == rs[i-1] {
            rs[i] = '*'
            cnt++
        }
    }
    return cnt
}

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

    switch {
    case k%2 == 0:
        s2 := strings.Join([]string{s, s}, "")
        s4 := strings.Join([]string{s2, s2}, "")
        ans2, ans4 := culculate(s2), culculate(s4)
        diff := ans4 - ans2
        fmt.Println(ans2 + (diff * ((k / 2) - 1)))
    case k%2 == 1:
        s3 := strings.Join([]string{s, s, s}, "")
        ans1, ans3 := culculate(s), culculate(s3)
        diff := ans3 - ans1
        fmt.Println(ans1 + (diff * (((k + 1) / 2) - 1)))
    }
}

ものすごく単純に見ると、文字列 $S$ について必要な操作回数を求め、それを $K$ 倍することになります。しかし $S$ を連結したときの繋ぎ目について考慮されていないのでこれは誤りです。では連結したときの繋ぎ目となる文字を見ればよさそうに思えますが、実際は繋ぎ目となる文字だけでなくその周辺の文字も見る必要があるため処理がやや複雑になりがちです。

そこで連結したときに必要な操作回数が何回増えるかを考えることにしてみます。つまり、 $S$ について必要な操作回数と $S$ を $2$ 個連結した文字列について必要な操作回数を求め、その差分を $K-1$ 倍したものを $S$ について必要な操作回数に足すことで解が求められそうです。しかしこれも以下のような入力例で誤りとなります。

aaa
3

文字列aaaについて必要な操作回数は $1$ 回、文字列aaaaaaについて必要な操作回数は $3$ 回、文字列aaaaaaaaaについて必要な操作回数は $4$ 回となり、上記のアルゴリズムで求められる $5$ 回という解は誤りであることがわかります。要するに、 $S$ によっては文字列を $1$ 個ずつ連結したときに増える操作回数が一定でないため、上記のアルゴリズムが適用できません。

少し考察すると、上記のアルゴリズムが適用できない例は $S$ が単一の文字で構成されていて、かつ $|S|$ が奇数であるときに限られることがわかります。つまり $S$ を $2$ 個連結した文字列を $1$ 個ずつ連結したときに増える操作回数を求めれば、上記のアルゴリズムを少し変形することで解を求めることができます。当然 $K$ の偶奇による場合分けが必要となりますが、連結の繋ぎ目について考えるよりは実装は簡単になると思います。

雑記

B問題は解けそうで解けない微妙な状態です。