More than 3 years have passed since last update.

AtCoder過去問精選10問でGolangと触れ合ってみませんか？

Last updated at 2019-12-18Posted at 2019-10-23

【概要】

「AtCoder に登録したら次にやること～これだけ解けば十分闘える！過去問精選 10 問～」の記事にて @drken さんがまとめてくださっているAtCoderに登録したてのエンジニアが解くべき精選１０問をGolangで解答します。
Golangをこれから学習する方は Tour of Go などで入門した次のステップとして問題に取り組んでみることをオススメします。

【対象者】

Golangの基礎構文は勉強したけど、実装に自信がない方
Golangで競技プログラミングをやってみたい方（Golangに拘りなく競技プログラミングをやってみたい方は@drkenさんの記事の方をオススメします）

【本題】

第 1 問: ABC 086 A - Product (100 点)

- 問題概要

二つの正整数 $a$ , $b$ が与えられます。 $a$ と $b$ の積が偶数か奇数か判定してください。

- 制約

$1 ≤ a,b ≤ 10000$
$a, b$ は整数

- 考え方

偶数判定のアルゴリズムとしては剰余算を使ったものとビット演算を使ったものの２種類が存在します。ここではよりポピュラーである剰余算を使って実装します。

fmt.Println はよく使うので標準出力の方法は知っていましたが、Golangで標準入力をしたことがなかったためそこだけ調べました。 fmt.Scan の詳細は Go 言語で標準入力から読み込む競技プログラミングのアレ --- 改訂第二版を参照していただければと思います。

なお実際の開発においては整数以外が入力されたらとか例外を考える必要がありますが、競技プログラミングにおいては考える必要がありません。

- 解答

package main
import (
    "fmt"
)

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

    if a*b%2==0 {
        fmt.Println("Even")
    } else {
        fmt.Println("Odd")
    }
}

第 2 問: ABC 081 A - Placing Marbles (100 点)

- 問題概要

0 と 1 のみから成る 3 桁の番号 s が与えられます。1 が何個含まれるかを求めてください。

- 考え方

文字列をループで回して一文字づつ判定を行うのもいいですが、せっかくなのでstringsパッケージに何かいい関数がないかと思い調べてみました。そしたらPHPで言うところの substr_count のような関数である
strings.Count という関数を発見しました。

- 解答

package main
import (
    "fmt"
    "strings"
)

func main(){
    var a string
    fmt.Scan(&a)
    fmt.Println(strings.Count(a, "1"))
}

第 3 問: ABC 081 B - Shift Only (200 点)

- 問題概要

黒板に $N$ 個の正の整数 $a_1, ..., a_N$ が書かれています。
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます。

黒板に書かれている整数すべてを， 2 で割ったものに置き換える。

すぬけ君は最大で何回操作を行うことができるかを求めてください。

- 考え方

各$a_i$に対して割り切れなくなるまで2で除算を繰り返して除算を行った回数の最小値を求めます。
最小値の初期値は非常に大きい数値としたいためInt64の最大値である 9223372036854775807 としています。
完全に私感ですがこういう問題は再帰で解答したくなります。

（追記）
Int64の最大値である 9223372036854775807 を数値リテラルとして扱っていましたが、 @c-yan さんのご指摘を参考に math.MaxInt64 を使用するよう修正しております。

- 制約

$1 ≤ N ≤ 200$
$1 ≤ A_i ≤ 10^9$

- 解答

package main

import (
    "fmt"
    "math"
)

func visit(cnt, a int) int {
    if a%2 == 1 {
        return cnt
    }
    return visit(cnt+1, a/2)
}

func main() {
    var n, a, cnt int
    var min int = math.MaxInt64
    fmt.Scan(&n)
    for i := 0; i < n; i++ {
        fmt.Scan(&a)
        cnt = visit(0, a)
        if cnt < min {
            min = cnt
        }
    }
    fmt.Println(min)
}

第 4 問: ABC 087 B - Coins (200 点)

- 問題概要

500 円玉を $A$ 枚、100 円玉を $B$ 枚、50 円玉を $C$ 枚持っています。これらの硬貨の中から何枚かを選び、合計金額をちょうど $X$ 円にする方法は何通りあるでしょうか？

- 制約

$0 ≤ A,B,C ≤ 50$
$A + B + C ≥ 1$
$50 ≤ X ≤ 20000$
$A,B,C$ は整数である
$X$ は $50$ の倍数である

- 考え方

$A,B,C$ の制約が緩いため3重ループを行ったとしても計算量は 51^3 = 132651 と非常に小さいため愚直に3重ループを行います（時間制約、メモリ制約にもよるのですが $10^8$ 程度なら時間内に実行し終えるかなという認識です）

- 解答

package main

import "fmt"

func main() {
    var a, b, c, x int
    fmt.Scan(&a, &b, &c, &x)

    cnt := 0

    for i := 0; i <= a; i++ {
        for j := 0; j <= b; j++ {
            for k := 0; k <= c; k++ {
                if i*500+j*100+k*50 == x {
                    cnt++
                }
            }
        }
    }

    fmt.Println(cnt)
}

第 5 問: ABC 083 B - Some Sums (200 点)

- 問題概要

$1$ 以上 $N$ 以下の整数のうち、$10$ 進法で各桁の和が $A$ 以上 $B$ 以下であるものについて、総和を求めてください。

- 制約

$1 ≤ N ≤ 10^4$
$1 ≤ A ≤ B ≤ 36$
入力はすべて整数

- 考え方

10進数の取り扱いに関しての問題です。今回は各桁の値を扱う必要があるので 10 による剰余算と除算の繰り返しを行います。３問目と同じく再帰関数を用いて解答していますがforループでも問題ないです。

- 解答

package main

import (
    "fmt"
)

func visit(x int) int {
    if x == 0 {
        return 0
    }
    return visit(x/10) + x%10
}

func main() {
    var n, a, b int
    fmt.Scan(&n, &a, &b)
    res := 0
    for i := 1; i <= n; i++ {
        sum := visit(i)
        if a <= sum && sum <= b {
            res += i
        }
    }
    fmt.Println(res)
}

第６問: ABC 088 B - Card Game for Two (200 点)

- 問題概要

$N$ 枚のカードがあり、$i$ 枚目のカードには $a_i$ という数が書かれています。
Alice と Bob はこれらのカードを使ってゲームを行います。ゲームでは 2 人が交互に 1 枚ずつカードを取っていきます。Alice が先にカードを取ります。
2 人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2 人とも自分の得点を最大化するように最適戦略をとったとき、Alice は Bob より何点多くの得点を獲得できるかを求めてください。

- 制約

$N$ は $1$ 以上 $100$ 以下の整数
$a_i$ は $1$ 以上 $100$ 以下の整数

- 考え方

2 人とも自分の得点を最大化するように最適戦略をとったとき

というのは各手番において場に残っているカードの中から最大値のカードを選択するとなります。ちなみに部分問題（今回の場合は各手番）において局所最適解を求める（今回の場合は最大値のカードを選択する）ということを繰り返すアルゴリズムを貪欲法と言います。

また最終的な解答はAlice, Bobそれぞれ何点獲得出来るか？ではなくてAliceはBobより何点多くの得点を獲得できるかなので、それぞれの得点を求めて差分を求める方法でもAliceの得点を加点・減点を繰り返す方法でもどちらでもいいです。例えば、カードが $1, 3, 5, 7, 9$だった場合に

$(9 + 5 + 1) - (7 + 3) = 5$
$+ 9 - 7 + 5 - 3 + 1 = 5$

のどちらのアルゴリズムであっても最終的な値は変わらないということです。（私は後者でアルゴリズムで解答しております。）

各手番において最大値を求めるとオーダーが増加するのでソートを行います。

- 解答

package main

import (
    "fmt"
    "sort"
)

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

    cards := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&cards[i])
    }
    sort.Ints(cards)

    res := 0
    operator := 1
    for i := n - 1; i >= 0; i-- {
        res += cards[i] * operator
        operator *= -1
    }
    fmt.Println(res)
}

第７問: ABC 085 B - Kagami Mochi (200 点)

- 問題概要

$X$ 段重ねの鏡餅 $(X ≥ 1)$ とは、$X$ 枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。例えば、直径 $10$、$8$、$6$ センチメートルの餅をこの順に下から積み重ねると $3$ 段重ねの鏡餅になり、餅を一枚だけ置くと $1$ 段重ねの鏡餅になります。
ダックスフンドのルンルンは $N$ 枚の円形の餅を持っていて、そのうち $i$ 枚目の餅の直径は $d_i$ センチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。

- 制約

1 ≤ N ≤ 100
1 ≤ d_i ≤ 100
入力値はすべて整数である。

- 考え方

競技プログラミングの問題は国語能力を問われているのか、やたら文章が冗長で要約されていない事が多々あります。この問題もやたら長いですが要約すると

$N$ 個の整数 $d[0],d[1],…,d[N−1]$ が与えられます。
この中に何種類の異なる値があるでしょうか？

となります。

(追記)
@c-yan さんの指摘によりmapとlenを活用すると分かりやすいと気づきました。なおmapの要素に使用している $1$ は特に意図はないです。

- 解答

package main

import "fmt"

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

    nums := map[int]int{}
    for i := 0; i < n; i++ {
        var tmp int
        fmt.Scan(&tmp)
        nums[tmp] = 1
    }
    fmt.Println(len(nums))
}

第８問: ABC 085 C - Otoshidama (300 点)

- 問題概要

10000 円札と、5000 円札と、1000 円札が合計で $N$ 枚あって、合計金額が $Y$ 円であったという。このような条件を満たす各金額の札の枚数の組を 1 つ求めなさい。そのような状況が存在し得ない場合には -1 -1 -1 と出力しなさい。

- 制約

$1 ≤ N ≤ 2000$
$1000 ≤ Y ≤ 2∗10^7$
$N$ は整数
$Y$ は $1000$ の倍数

- 考え方

第４問目と同じように３重ループで解答してしまうと最大の計算量は $2000 * 2000 * 2000 = 8000000000$ となり、タイムアウトエラーしてしまいます。なので愚直に３重ループで解答するのではなく、一工夫が必要になります。

今回の場合、合計枚数が２０枚で10000円札が10枚、5000円札が8枚だったとしたら1000円札は $20-(10+8)=2$ 枚となります。したがって合計枚数、10000円札の枚数、5000円札の枚数が決まれば1000円札の枚数が決まるので、2重ループで十分であり最大の計算量は $2000 * 2000 = 4000000$ となり時間内に解答できる計算量となります。

- 解答

package main

import "fmt"

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

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

第 9 問: ABC 049 C - Daydream (300 点)

- 問題概要

英小文字からなる文字列 $S$ が与えられます。
$T$ が空文字列である状態から始めて、以下の操作を好きな回数繰り返すことで $S=T$ とすることができるか判定してください。

$T$ の末尾に "dream", "dreamer", "erase", "eraser" のいずれかを追加する。

- 制約

$1≤|S|≤10^5$
$S$ は英小文字からなる

- 考え方

空文字列の末尾に "dream", "dreamer", "erase", "eraser" のいずれかを追加することを繰り返して最終的に $S$ になるかを調べるよりも、 $S$ から "dream", "dreamer", "erase", "eraser" のいずれかを空文字列に置換することを繰り返して最終的に空文字列になるかを調べた方が楽です。

難しい点としては例えば $S$ が "dreamerase" だった場合に "dream" を空文字列に置換して、残った "erase" を空文字列に置換すれば $S$ が空文字列とできるのに対して、 "dreamer" を空文字列に置換してしまうと "ase" が残ってしまうため $S$ を空文字列に置換できない点にあります。したがって単純に貪欲法を採用してしまうと各手順だけでは局所最適解を求めることが出来ません。

この問題のアルゴリズムは２つあると思いますので、どちらも紹介したいと思います。

$S$ の末尾から置換を繰り返す
- "dream", "dreamer", "erase", "eraser"の末尾3文字に注目すると "eam", "mer", "ase", "ser" となり、いずれも重複していないことがわかります。したがって末尾から置換していけば重複を意識することなく貪欲法が採用できます。
- 先ほどの例でいうと "dreamerase" の末尾を置換できるのは "erase" だけであり、残った "dream" を置換できるのは "dream" だけになります。
段階的に置換を繰り返す
- "dream" と "dreamer" および "erase" と "eraser" のどちらを空文字列に置換すればいいのかが、その手順においては分からないというのが難しいので一気に空文字列に置換するのではなく適当な文字（英小文字以外）に置換して段階を踏めば正しく置換することが出来ます。その手順を以下に示します。
  - まず "dream" を "A" に、 "erase" を "B" に置換します
  - 次に "Aer" および "Br" を空文字列に置換します
  - 最後に "A" および "B" を空文字列に置換します
- 先ほどの例でいうと "dreamerase" を "AB" に置換して、 "AB" を空文字列に置換します

今回は2の方針で実装しています。

※あくまで個人的な主観ですが精選10問の中でこの問題が一番難しいように感じます。

- 解答

package main

import (
    "fmt"
    "strings"
)

func main() {
    var str string
    fmt.Scan(&str)
    str = strings.Replace(str, "dream", "A", -1)
    str = strings.Replace(str, "erase", "B", -1)
    str = strings.Replace(str, "Aer", "", -1)
    str = strings.Replace(str, "Br", "", -1)
    str = strings.Replace(str, "A", "", -1)
    str = strings.Replace(str, "B", "", -1)
    if str == "" {
        fmt.Println("YES")
    } else {
        fmt.Println("NO")
    }
}

第 10 問: ABC 086 C - Traveling (300 点)

- 問題概要

シカの AtCoDeer くんは二次元平面上で旅行をしようとしています。AtCoDeer くんの旅行プランでは、時刻 $0$ に点 $(0,0)$ を出発し、$1$ 以上 $N$ 以下の各 $i$ に対し、時刻 $t_i$ に点 $(x_i,y_i)$ を訪れる予定です。

AtCoDeer くんが時刻 $t$ に点 $(x,y)$ にいる時、時刻 $t+1$ には点 $(x+1,y),(x−1,y),(x,y+1),(x,y−1)$ のうちいずれかに存在することができます。その場にとどまることは出来ないことに注意してください。AtCoDeer くんの旅行プランが実行可能かどうか判定してください。

- 制約

$1 ≤ N ≤ 10^5$
$0 ≤ x_i,y_i ≤ 10^5$
$1 ≤ t_i ≤ t_{i+1} ≤ 10^5$
入力はすべて整数

- 考え方

問題を読んですぐに思いつくアルゴリズムは深さ優先探索ではないかと思います。ただし各手順において取れる行動は $４$ 通りあり、かつ手順は最大で $10^5$ あるので最大計算量は $4^{10^5}$ で Google先生で値を求めようとしたところInfinityとなったため、タイムアウトエラーしてしまうでしょう。

この問題で着目すべき点は２点あります。

$(x_i, y_i)$ に最短で向かった場合に $t_i$ までに到達できるかどうか
- 例えば $t_1$ が 1 で、 $x_1$ = 100, $y_1$ = 100 である場合に、 $t_1$ に到達できるのは $(0, 1), (1, 0)$ のいずれかであるため到底 $(100, 100)$ に到達することはできません
$(x_i, y_i)$ に最短で向かった場合に到達した時刻と $t_i$ の差分が偶数かどうか
- 例えば $t_1$ が 10 で、 $x_1$ = 2, $y_1$ = 4 である場合に、 $(2, 4)$ に最短で到達できる時刻は 6 になります（これを仮に $t_j$ とします）。余った時刻は $(2, 4)$ と $(2, 5)$ を往復した場合に $t_i$ に $(x_i, y_i)$ に到達できるのは $t_i$ と $t_j$ の差分が偶数の場合のみです

したがって条件としては全ての $x_i, y_i, t_i$ に関して以下を満たすことになります

$|x_i - x_{i-1}| + |y_i - y_{i-1}| <= t_i - t_{t-1}$
$mod(|x_i - x_{i-1}| + |y_i - y_{i-1}|, 2) = mod(t_i - t_{t-1}, 2)$

- 解答

package main

import (
    "fmt"
    "math"
)

func main() {

    var n int
    fmt.Scan(&n)

    t := map[int]int{0: 0}
    x := map[int]int{0: 0}
    y := map[int]int{0: 0}
    for i := 1; i <= n; i++ {
        var xi, yi, ti int
        fmt.Scan(&ti, &xi, &yi)
        t[i] = ti
        x[i] = xi
        y[i] = yi
    }

    res := true
    for i := 1; i <= n; i++ {
        dx := int(math.Abs(float64(x[i] - x[i-1])))
        dy := int(math.Abs(float64(y[i] - y[i-1])))
        dt := int(math.Abs(float64(t[i] - t[i-1])))
        if dx+dy > dt || (dx+dy)%2 != dt%2 {
            res = false
        }
    }

    if res {
        fmt.Println("Yes")
    } else {
        fmt.Println("No")
    }
}

【まとめ】

これであなたもGolang入門卒業！！

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

AtCoder過去問精選10問でGolangと触れ合ってみませんか？

【概要】

【対象者】

【本題】

第 1 問: ABC 086 A - Product (100 点)

- 問題概要

- 制約

- 考え方

- 解答

第 2 問: ABC 081 A - Placing Marbles (100 点)

- 問題概要

- 考え方

- 解答

第 3 問: ABC 081 B - Shift Only (200 点)

- 問題概要

- 考え方

- 制約

- 解答

第 4 問: ABC 087 B - Coins (200 点)

- 問題概要

- 制約

- 考え方

- 解答

第 5 問: ABC 083 B - Some Sums (200 点)

- 問題概要

- 制約

- 考え方

- 解答

第 ６ 問: ABC 088 B - Card Game for Two (200 点)

- 問題概要

- 制約

- 考え方

- 解答

第 ７ 問: ABC 085 B - Kagami Mochi (200 点)

- 問題概要

- 制約

- 考え方

- 解答

第 ８ 問: ABC 085 C - Otoshidama (300 点)

- 問題概要

- 制約

- 考え方

- 解答

第 9 問: ABC 049 C - Daydream (300 点)

- 問題概要

- 制約

- 考え方

- 解答

第 10 問: ABC 086 C - Traveling (300 点)

- 問題概要

- 制約

- 考え方

- 解答

【まとめ】

第６問: ABC 088 B - Card Game for Two (200 点)

第７問: ABC 085 B - Kagami Mochi (200 点)

第８問: ABC 085 C - Otoshidama (300 点)