【ABC190】A~D問題

• AtCoder
• ABC
• golang

AtCoder Beginner Contest 190

A - Very Very Primitive Game

https://atcoder.jp/contests/abc190/tasks/abc190_a

考えたこと

• $A == B$ の時 後攻が勝つ
• $A > B$ の時 Takahashi が勝つ
• $A < B$ の時 Aoki が勝つ

Note

入力例

2 2 1

出力例

Takahashi

AC

func main() {
    A, B, C := nextInt(), nextInt(), nextInt()
    fmt.Println(solve(A, B, C))
}

func solve(a, b, c int) string {
    if a == b {
        if c == 0 {
            return "Aoki"
        }
        return "Takahashi"
    }
    if a > b {
        return "Takahashi"
    }
    return "Aoki"
}

After Contest

• $B = B - C$ で常に Takahashi 先手と同義

B - Magic 3

https://atcoder.jp/contests/abc190/tasks/abc190_b

考えたこと

• そのまま実装

Note

入力例

7 100 100
10 11
12 67
192 79
154 197
142 158
20 25
17 108

出力例

Yes

AC

func main() {
    N, S, D := nextInt(), nextInt(), nextInt()

    var cnt int
    for i := 0; i < N; i++ {
        x, y := nextInt(), nextInt()
        if x < S && y > D {
            cnt++
        }
    }
    if cnt > 0 {
        fmt.Println("Yes")
    } else {
        fmt.Println("No")
    }
}

C - Bowls and Dishes

https://atcoder.jp/contests/abc190/tasks/abc190_c

考えたこと

• $K \leq 16$
• ボールを置く全てのパターンを全探索($O(2^K)$)

Note

入力例

6 12
2 3
4 6
1 2
4 5
2 6
1 5
4 5
1 3
1 2
2 6
2 3
2 5
5
3 5
1 4
2 6
4 6
5 6

出力例

9

AC

func main() {
    N, M := nextInt(), nextInt()
    AB := nextInts(2 * M)
    K := nextInt()
    CD := nextInts(2 * K)

    arr := [][]bool{make([]bool, N)}

    for i := 0; i < K; i++ {
        c, d := CD[i*2]-1, CD[i*2+1]-1
        narr := [][]bool{}
        for j := range arr {
            narr = append(narr, sara(c, d, arr[j])...)
        }
        arr = narr
    }

    var ans int
    for _, s := range arr {
        var cnt int
        for i := 0; i < M; i++ {
            a, b := AB[i*2]-1, AB[i*2+1]-1

            if s[a] && s[b] {
                cnt++
            }
        }
        ans = maxOf(ans, cnt)
    }

    fmt.Println(ans)
}

func sara(c, d int, a []bool) [][]bool {
    ca := make([]bool, len(a))
    copy(ca, a)
    a[c] = true
    ca[d] = true
    return [][]bool{a, ca}
}

After Contest

• コンテスト中は再帰で全探索したが、bit全探索でも

func main() {
    N, M := nextInt(), nextInt()
    AB := nextInts(2 * M)
    K := nextInt()
    CD := nextInts(2 * K)

    var ans int
    for bit := 0; bit < 1<<K; bit++ {
        dish := make([]bool, N)

        for i := 0; i < K; i++ {
            c, d := CD[i*2]-1, CD[i*2+1]-1

            if bit>>i&1 != 0 {
                dish[c] = true
            } else {
                dish[d] = true
            }
        }

        var cnt int
        for i := 0; i < M; i++ {
            a, b := AB[i*2]-1, AB[i*2+1]-1

            if dish[a] && dish[b] {
                cnt++
            }
        }
        ans = maxOf(ans, cnt)
    }

    fmt.Println(ans)
}

D - Staircase Sequences

https://atcoder.jp/contests/abc190/tasks/abc190_d

考えたこと

• $N \leq 10^{12}$ より $\sqrt{N}$ 解法を予想
• 等比数列の和
  • $\frac{1}{2}(2\cdot begin + length-1)\cdot length=N$
  • $begin = \frac{N}{length}-\frac{length-1}{2}$
• $begin$ が 1以上の条件を満たす等差数列が存在する時, 対応する　1未満の要素を含む等差数列が丁度1つ存在する。
  • $[-begin+1, begin+length)$, $[begin, begin+length)$
• $length$ は $N$ の 約数であり, 自然数
• 少しガバガバだけど書いてみる

Note

入力例

963761198400

出力例

1920

AC

func main() {
    N := nextInt()

    var ans int
    for _, div := range divisors(N) {
        a := float64(N)/float64(div) - float64(div-1)/2
        if a == float64(int(a)) {
            ans += 2
        }

    }
    fmt.Println(ans)
}

func divisors(n int) []int {
    ret, a := []int{}, []int{}
    for i := 1; i*i <= n; i++ {
        if n%i != 0 {
            continue
        }
        ret = append(ret, i)
        if i*i != n {
            a = append([]int{n / i}, a...)
        }
    }
    return append(ret, a...)
}