Continue(s)

Twitter:@dn0t_ GitHub:@ogrew

晩夏なのでGolangでAtCoder精選10問を解く。

f:id:taiga006:20190912171327j:plain


晩夏は特に関係ないです。 早速やっていき。

🐬 ABC 086 A - Product (100 点)

// ABC 086 A - Product
package main

import (
    "fmt"
)

func main() {
    var a, b int
    fmt.Scanf("%d %d", &a, &b)
    if (a*b)%2 == 0 {
        fmt.Println("Even")
    } else {
        fmt.Println("Odd")
    }
}

📝メモ

OddOddstypoしてWA出したけど内緒。 fmt.Scanは遅いらしいがとりあえずはまだ影響出るレベルではない。 そうなったとき考える。

↓そのあたりはこれが参考になりそう。 qiita.com

🐬 ABC 081 A - Placing Marbles (100 点)

// ABC 081 A - Placing Marbles
package main

import (
    "fmt"
)

func main() {
    var str string
    fmt.Scan(&str)
    cnt := 0
    for i := 0; i < len(str); i++ {
        if str[i] == '1' {
            cnt++
        }
    }
    fmt.Print(cnt)
}

📝メモ

与えられるのが数字列と決まっているでやりやすい。

🐬 ABC 081 B - Shift Only (200 点)

// ABC 081 B - Shift Only
package main

import "fmt"

func main() {
    var n, cnt int
    var a []int
    fmt.Scan(&n)
    a = make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&a[i])
    }

    flag := true
    for flag {
        for i := 0; i < n; i++ {
            if a[i]%2 == 0 {
                a[i] /= 2
            } else {
                flag = false
            }
        }
        if flag {
            cnt++
        }
    }
    fmt.Print(cnt)
}

📝メモ

for flag で無限ループ。
すべてが偶数であれば一つでも偶数があればと読み間違えてWAを出した。

🐬 ABC 087 B - Coins (200 点)

// ABC 087 B - Coins
package main

import "fmt"

func main() {
    var A, B, C, X, cnt int
    fmt.Scan(&A, &B, &C, &X)

    for a := 0; a <= A; a++ {
        for b := 0; b <= B; b++ {
            for c := 0; c <= C; c++ {
                if a*500+b*100+c*50 == X {
                    cnt++
                }
            }
        }
    }
    fmt.Println(cnt)
}

📝メモ

全探索。三重ループは見るだけで心的負荷が高い。

🐬 ABC 083 B - Some Sums (200 点)

// ABC 083 B - Some Sums 
package main

import (
    "fmt"
    "log"
)

func main() {
    var n, a, b, total int
    fmt.Scan(&n, &a, &b)

    for i := 1; i < (n + 1); i++ {
        var x [3]int
        var y int
        if i >= 1000 {
            x[0] = i / 1000
        }
        if i >= 100 {
            x[1] = i / 100
        }
        if i >= 10 {
            x[2] = i / 10
        }

        y = i - x[0]*1000 - x[1]*100 - x[2]*10
        res := x[0] + x[1] + x[2] + y

        if res >= a && res <= b {
            total += i
            log.Printf("n = %d -> res:%d", i, res)

        }
    }
    fmt.Print(total)
}

📝メモ

これもA以上B以下の条件をAorBに等しくなると取り間違えて最初にWAを出してしまった。途中のデバッグログは反省として消さずに残しておく。

🐬 ABC 088 B - Card Game for Two (200 点)

// ABC 088 B - Card Game for Two
package main

import (
    "fmt"
    "sort"
)

func main() {
    var n, a int
    fmt.Scan(&n)
    arr := make([]int, n)
    for i := range arr {
        fmt.Scan(&a)
        arr[i] = a
    }
    sort.Sort(sort.Reverse(sort.IntSlice(arr)))

    var alice, bob int
    for i := range arr {
        if i%2 == 0 {
            alice += arr[i]
        } else {
            bob += arr[i]
        }
    }
    fmt.Println(alice-bob)
}

📝メモ

sort packageを使って解決。(降順にする方法がわからずに調べた。)
golangのsortに関してはいろいろ気になるところがあったので後日また記事にする。

🐬 ABC 085 B - Kagami Mochi (200 点)

// ABC 085 B - Kagami Mochi
package main

import "fmt"

func main() {
    var n int
    fmt.Scan(&n)
    d := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&d[i])
    }
    p := make(map[int]int)
    for v := range d {
        p[d[v]]++
    }
    fmt.Println(len(p))
}

📝メモ

mapを使ってカウント。問題の意図を間違えなければ非常に単純。

🐬 ABC 085 C - Otoshidama (300 点)

// ABC 085 C - Otoshidama
package main

import "fmt"

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

    for i := 0; i <= n; i++ {
        for j := 0; j <= (n - i); j++ {
            k := n - (i + j)
            total := 10000*i + 5000*j + 1000*k
            if total == y {
                fmt.Println(i, j, k)
                return
            }
        }
    }
    fmt.Println(-1, -1, -1)
}

📝メモ

素直にやったらTLEになりそうだったのでちょっと工夫した。

🐬 ABC 049 C - Daydream (300 点)

// ABC 049 C - Daydream
package main

import (
    "fmt"
    "strings"
)

func main() {

    var s string
    fmt.Scan(&s)

    s = reverse(s)
    s = strings.Replace(s, "resare", "", -1)
    s = strings.Replace(s, "esare", "", -1)
    s = strings.Replace(s, "remaerd", "", -1)
    s = strings.Replace(s, "maerd", "", -1)

    var res string
    if len(s) == 0 {
        res = "YES"
    } else {
        res = "NO"
    }
    fmt.Println(res)
}

func reverse(s string) string {
    rs := []rune(s)
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        rs[i], rs[j] = rs[j], rs[i]
    }
    return string(rs)
}

📝メモ

文字列の反転。自前で実装する必要があった。ただindexを見て反転させていくとバイト列なのでぐちゃぐちゃになってしまう。runeを使う。

y0m0r.hateblo.jp

🐬 ABC 086 C - Traveling (300 点)

// ABC 086 C - Traveling
package main

import (
    "fmt"
    "math"
)

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

    var t int
    var x, y float64
    t, x, y = 0, 0.0, 0.0 // initialized

    var tNext int
    var xNext, yNext float64

    flag := "Yes"
    for i := 0; i < n; i++ {
        fmt.Scan(&tNext, &xNext, &yNext)

        // 残り時間
        T := tNext - t
        // 目的地までの距離(マンハッタン距離)
        dist := math.Abs(xNext-x) + math.Abs(yNext-y)

        // 残り時間より必要な移動距離のほうが長い
        if T < int(dist) {
            flag = "No"
        }
        // 着いてからのあまり時間が偶数であれば行き帰りできる
        if (T-int(dist))%2 == 1 {
            flag = "No"
        }
        // updated
        t, x, y = tNext, xNext, yNext
    }
    fmt.Println(flag)
}

📝メモ

自分で解けなかったので、答えを調べる。この人の説明がわかりやすかった。

scrapbox.io


Gistにも同じコードを載せてあります。 AtCoder過去問精選10問 Golangで解いてみた · GitHub