AtCoder Beginner Contest 317 C - Remembering the Days

## 問題

atcoder.jp

考察

この問題はどうやって解くのだろう。。。とモヤモヤ悩んでいる間に時間切れ。。。

解答を見ると、DFS（深さ優先探索）で導き出すのが良いとのこと。

とりあえず、Goで書いている人の解答例を見て学ぶことにする。

DFSを行うにあたり、どのようなデータを作るのが良いかを見てみるのだが、やはりmapにするのが良さそうだ。

頂点と辺の関係を以下のようなデータ（頂点に対して隣接する頂点と辺（距離）で表すデータ）にしておくのがわかり易い。

map[1:[{2 1} {3 100} {4 1000}] 2:[{1 1} {3 10}] 3:[{2 10} {1 100}] 4:[{1 1000}]]

あとは、問題文の「好きな街からスタートして同じ街を二度以上通らずに別の街へ移動するときの、通る道路の長さの和としてありえる最大値を求めてください。」に注意する。

つまり、すべての街を通らなくても良く、とにかく最大値を求めれば良いということ。

そうなると以下解答で納得がいく。まだまだ勉強不足。。。

解答

package main

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

type Town struct {
    town int
    road int
}

var maxDistance int
var visited []bool

func dfs(graph map[int][]Town, current int, distance int) {
    if distance > maxDistance {
        maxDistance = distance
    }
    visited[current] = true

    for _, Town := range graph[current] {
        if !visited[Town.town] {
            dfs(graph, Town.town, distance+Town.road)
        }
    }

    visited[current] = false
}

func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()

    var N, M int
    fmt.Fscan(in, &N, &M)

    x := make(map[int][]Town)
    for i := 0; i < M; i++ {
        var A, B, C int
        fmt.Fscan(in, &A, &B, &C)
        x[A] = append(x[A], Town{town: B, road: C})
        x[B] = append(x[B], Town{town: A, road: C})
    }

    maxDistance = 0
    visited = make([]bool, N+1)

    for i := 1; i <= N; i++ {
        dfs(x, i, 0)
    }

    fmt.Fprintln(out, maxDistance)
}

AtCoder Beginner Contest 314 C - Rotate Colored Subsequence

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

問題

atcoder.jp

問題文が長いので、理解するまでに結構な時間を使った。

私的考察

1. 入力した文字列 $S$ に対して、$i$ごとに文字を抽出する。
2. 抽出した$i$ごとに中の文字をシフトさせる。
3. 再度$i$ごとに値を取り出し、文字列を再構築。

みたいにすればOKだと思い込み実装。

結果： めっちゃメモリ使ってた。。。。orz

解き方

これは、$i$ごとに文字を抽出するのではなく、添字を抽出するのがポイント。

加えて、配列ではなくmapを使うことで、for文が3個くらい減らせる。

package main

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

func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()

    var N, M int
    fmt.Fscan(in, &N, &M)

    var S string
    fmt.Fscan(in, &S)
    ss := strings.Split(S, "")

    mp := map[int][]int{}
    for i := 0; i < N; i++ {
        var c int
        fmt.Fscan(in, &c)
        mp[c] = append(mp[c], i)
    }

    for i := 1; i <= M; i++ {
        if len(mp[i]) <= 1 {
            continue
        }
        last := ss[mp[i][len(mp[i])-1]]
        for j := len(mp[i]) - 1; j > 0; j-- {
            ss[mp[i][j]] = ss[mp[i][j-1]]
        }
        ss[mp[i][0]] = last
    }
    fmt.Fprintln(out, strings.Join(ss, ""))
}

あと、今回はいつも使用しているbufio.Scannerを使うと、うまく読み取れない問題があ出てきたので、 bufio.NewReaderとbufio.NewWriterを使用した。

うーん、このあたりも理解しておかないとこの先辛いな。。。

AtCoder Beginner Contest 312 C - Invisible Hand

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

atcoder.jp

問題

りんご市場に$N$人の売り手と ${M}$人の買い手がいます。 $i$番目の売り手は、$A_i$円以上でならりんごを売ってもよいと考えています。 $i$番目の買い手は、$B_i$円以下でならりんごを買ってもよいと考えています。

次の条件を満たすような最小の整数 $X$を求めてください。

条件：りんごを$X$円で売ってもよいと考える売り手の人数が、りんごを$X$円で買ってもよいと考える買い手の人数以上である。

制約

• $1$ $\leq$ $N$, ${M}$ $\leq$ $2$ $\times$ 10⁵
• $1$ $\leq$ $A_i$, $B_i$ $\leq$ 10⁹
• $ 入力される数値はすべて整数 $

私的考察

1. 売り手と買い手の金額をソートする。
2. 売り手を基準に買い手を見つける。
3. 売り手の数 $\leq$ 買い手の数となれば、OKだろう。。。

みたいにすればOKだと思い込み実装。

結果： まったく違う。

解き方

りんごを$X$円で売ってもよいと考える売り手の人数が、りんごを$X$円で買ってもよいと考える買い手の人数以上になる最小の整数 $X$を求める必要がある。

つまり。。。

1. 売り手と買い手の金額をソートする。
2. 0 ~ 10⁹ の金額間で、売り手の数 $\leq$ 買い手の数となる最小値を見つける。 （なお、探索は二分探索で行う）

みたいにすればOK。

GO言語には、sort.Search()と呼ばれる「二分探索を使用して、$f(i)$が true である[0,n)の最小インデックスを返す」関数がある。

この関数を使って、二分探索する金額に対して、$X$円で売ってもよいと考える売り手の人数と$X$円で買ってもよいと考える買い手を見つける。

以下のようになる。

package main

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

var sc *bufio.Scanner

func scanInt() int {
    sc.Scan()
    i, _ := strconv.Atoi(sc.Text())
    return i
}

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

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

    N, M := scanInt(), scanInt()

    A := make([]int, N)
    for i := 0; i < N; i++ {
        A[i] = scanInt()
    }

    B := make([]int, M)
    for i := 0; i < M; i++ {
        B[i] = scanInt()
    }

    sort.Ints(A)
    sort.Ints(B)

    start := 0
    end := int(1e9) + 1 /* 10^9 + 1*/
    for {
        v := (start + end) / 2
        sell := sort.Search(N, func(i int) bool { return A[i] > v })
        buy := M - sort.Search(M, func(i int) bool { return B[i] >= v })


        if start == end {
            break
        }

        if sell < buy {
            start = v + 1
        } else if buy <= sell {
            end = v
        }
    }
    fmt.Println(start)
}

AtCoder Beginner Contest 309 B - Rotate

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

atcoder.jp

問題

$N$行$N$列のマス目が与えられる。上から$i$行目、左から$j$列目のマスには整数$A_{i,j}$が書かれています。ここで、$A_{i,j}$は$0$か$1$であることが保証されます。 マス目の外側のマスに書かれた整数を時計回りに$1$個ずつずらしたときのマス目を出力してください。 ただし、外側のマスとは、$1行目$、$N行目$、$1列目$、$N列目$のいずれか$1$つ以上に属するマスの集合のことを指します。

制約

• $ 2 \leq N \leq 100 $
• $ 0 \leq A_{i,j} \leq 1（1 \leq i、j \leq N） $
• $ 入力される数値はすべて整数 $

解き方

これは、入力値$A_{i,j}$を文字列の配列で受け取り。

文字列をうまく加工して、処理させる。

Go言語の文字列操作を理解できていなかったことが敗因なので、以後注意する。

正しい解

package main

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

var sc *bufio.Scanner

func scanInt() int {
    sc.Scan()
    i, _ := strconv.Atoi(sc.Text())
    return i
}

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

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

    N := scanInt()

    A := make([]string, N)
    for i, _ := range A {
        A[i] = scanString()
    }

    B := make([]string, N)
    t := ""
    for i, v := range A {
        if i == 0 {
            // 一番上
            t = v[N-1:]
            B[i] = A[i+1][:1] + v[:N-1]
        } else if i < N-1 {
            // 真ん中
            B[i] = A[i+1][:1] + v[1:N-1] + t
            t = A[i][N-1:]
        } else {
            // 一番下
            B[i] = v[1:] + t
        }
    }

    for _, v := range B {
        fmt.Println(v)
    }
}

AtCoder Beginner Contest 308 C - Standings

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

atcoder.jp

問題

$1$から$N$の番号が付いた$N$人がコイントスを何回かしました。人$i$は$A_i$回表を出し、$B_i$回裏を出したことが分かっています。 人$i$のコイントスの成功率は$\dfrac{A_i}{A_i+B_i}$で定義されます。人$1,...,N$の番号を、成功率の高い順に並び替えよ。 成功率が同じ人が複数いる場合、その中では人の番号が小さい順になるように並び替えよ。

制約

• $ 2 \leq N \leq 2 \times 10^{5} $
• $ 0 \leq A_i、B_i \leq 10^{9} $
• $ A_i + B_i \geq 1 $
• $ 入力される数値はすべて整数 $

解き方

この問題、簡単そうに見えて難しい。実際、解けなかった。。。

素直に、成功率を$\dfrac{A_i}{A_i+B_i} \lt \dfrac{A_j}{A_j+B_j}$で比較すると、まず通らない。。。

floatで比較すると落ちるケースが入っているため、分母を落として、int64で比較するのが良いらしい。

分母を落とすと$A_i({A_j+B_j}) \lt A_j({A_i+B_i})$で比較できる。

あとは、成功率が同じ場合、番号で比較した結果を入れることに注意する。

標準入力もbufio.Scannerを使う方がfmt.Scanfより早いとのことなので、今後はこちらを使っていくようにする。

正しい解

package main

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

var sc *bufio.Scanner

type person struct {
    id, a, b int
}

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

    N := scanInt()
    p := make([]person, N)
    for i, _ := range p {
        p[i].id = i + 1
        p[i].a, p[i].b = scanInt(), scanInt()
    }

    sort.Slice(p, func(i, j int) bool {
        n := p[i].a*(p[j].a+p[j].b) - p[j].a*(p[i].a+p[i].b)
        if n == 0 {
            return p[i].id < p[j].id
        }
        return n > 0
    })

    ans := make([]string, 0, N)
    for _, v := range p {
        ans = append(ans, strconv.Itoa(v.id))
    }
    fmt.Println(strings.Join(ans, " "))
}

func scanInt() int {
    sc.Scan()
    i, _ := strconv.Atoi(sc.Text())
    return i
}