Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What are the problem?

AtCoder Beginner Contest 209 ~Goの練習~

感想

今回もリアタイで参加することはできなかった。

E問題とF問題が知識がないとできないようだったのできつかった。

ただ、そもそも集中して解こうとしていなかったので、そもそも解く姿勢に問題がありそう。

A問題

考察

$a$以上$b$以下の整数の個数を出力する。

$b<a$の場合は個数が0であることに注意する。

文法

特になし。

package main

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

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

    var a, b int
    fmt.Fscan(scin, &a, &b)
    if b < a {
        fmt.Fprintln(prout, 0)
    } else {
        fmt.Fprintln(prout, b-a+1)
    }
}

B問題

考察

$x$から与えられた順番に$a[i]$を引いて、偶数番目の時のみインクリメントを行えば良い。

最後に、$x<0$の時はNo、それ以外の時はYesを出力する。

文法

特になし。

package main

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

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

    var n, x int
    fmt.Fscan(scin, &n, &x)
    for i := 0; i < n; i++ {
        var a int
        fmt.Fscan(scin, &a)
        if i%2 == 0 {
            x -= a
        } else {
            x -= a
            x++
        }
    }
    if x < 0 {
        fmt.Fprintln(prout, "No")
    } else {
        fmt.Fprintln(prout, "Yes")
    }
}

C問題

考察

何らかの順番で整数列に含まれる数字を順に選び、余った数の中から選ぶことを繰り返すことで、任意の数が異なるように選ぶことができる、と考えた。

この時、数が大きいほど選べる数の選択肢が増えることに注目した。つまり、数の小さいものから選ぶことで、残った数の中から任意のものを選べることに注目した。

また、場合の数は$c_i$の並び順によらないので、$c_i$の昇順に並べ直す。この時、数の小さいものから選ぶことで、$i$番目の整数には$c_i-i$通りの選び方がある。つまり、これを任意の$i$で繰り返して掛け合わせれば良いのだが、$c_i \leqq i$となる$i$が一つでも存在する場合は0通りとなるので注意が必要である。

文法

特になし。

package main

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

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

    var n int
    fmt.Fscan(scin, &n)
    mod := int(math.Pow10(9)) + 7
    var c []int = make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Fscan(scin, &c[i])
    }
    sort.Slice(c, func(i, j int) bool { return c[i] < c[j] })
    ans := 1
    flag := false
    for i := 0; i < n; i++ {
        if c[i] < i+1 {
            flag = true
            break
        } else {
            ans *= c[i] - i
            ans %= mod
        }
    }
    if flag {
        fmt.Fprintln(prout, 0)
    } else {
        fmt.Fprintln(prout, ans)
    }
}

D問題

考察

問題をよく読んでなくてLCAを使うのかと思っていた。問題はよく読もう。

まず、道の途中で出会うか街で出会うかの判定はその距離が奇数であるか偶数であるかの判定と同様である。また、木上の距離の偶奇を扱う問題は木が二部グラフとなる性質を用いて解けば良い。したがって、与えられた木をDFSやBFSなどで走査して二色に彩色すれば良い。彩色した際、同じ色同士の場合は距離が偶数であり、異なる色同士の場合は距離が奇数となるので、クエリではその処理を行えば良い。

文法

二次元配列を用いるのにまだ少し慣れない。

(多分)今回はbfsを行ったので、スライスを用いてqueueのような操作をした。十分高速に動くので、queueを使っていたタイミングでもスライスを使うようにする。

(C++の)dequeとvectorのいいとこ取りがスライスであると認識して当面の間は使おうと思う。時間のある時に実装を調べたい。

package main

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

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

    var n, q int
    fmt.Fscan(scin, &n, &q)
    var tree [][]int = make([][]int, n)
    for i := 0; i < n-1; i++ {
        var a, b int
        fmt.Fscan(scin, &a, &b)
        tree[a-1] = append(tree[a-1], b-1)
        tree[b-1] = append(tree[b-1], a-1)
    }
    var check []int = make([]int, n)
    check[0] = 1
    var now []int = make([]int, 0)
    now = append(now, 0)
    for len(now) > 0 {
        x := now[0]
        now = now[1:]
        for _, nex := range tree[x] {
            if check[nex] == 0 {
                check[nex] = -check[x]
                now = append(now, nex)
            }
        }
    }
    for i := 0; i < q; i++ {
        var c, d int
        fmt.Fscan(scin, &c, &d)
        if check[c-1]+check[d-1] == 0 {
            fmt.Fprintln(prout, "Road")
        } else {
            fmt.Fprintln(prout, "Town")
        }
    }
}
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
0
Help us understand the problem. What are the problem?