AtCoder Grand Contest 041 参戦記

AGC041A - Table Tennis Training

28分半で突破. WA5. 何だ簡単じゃんと思って提出したらやっぱり簡単ではなかったw

以下のうち一番早いものが解答

1. まっすぐ近寄る(ただし距離が偶数でないとすれ違うので偶数の場合のみ)
2. 1 で待ち合わせをする.
3. N で待ち合わせをする.
4. 2人で1に向かい、先に着くAにいた選手が1ターン1に留まり(これで距離が偶数になる)、折り返してBを迎えに行く
5. 2人でNに向かい、先に着くBにいた選手が1ターンNに留まり(これで距離が偶数になる)、折り返してAを迎えに行く

N, A, B = map(int, input().split())

t = float('inf')
if abs(A - B) % 2 == 0:
    t = min(abs(A - B) // 2, t)
t = min(B - 1, t)
t = min(N - A, t)
t = min((A - 1 + 1) + (B - A - 1) // 2, t)
t = min((N - B + 1) + (N - (A + (N - B + 1))) // 2, t)
print(t)

追記: 改めて考えてみると、2と3は要らないし、偶数の場合は端に行くパターンを考える必要はなかった.

N, A, B = map(int, input().split())

if (B - A) % 2 == 0:
    print((B - A) // 2)
else:
    print(min(A, N - B + 1) + (B - A - 1) // 2)

AGC041B - Voting Judges

113分で突破. WA5. Python で TLE 食らって、PyPy にしても TLE 食らって、Go で書き直しても TLE 食らって、一箇所無駄なスライスのコピーを消したら AC と、一つだけ重たいテストケースが入っててボコボコにされた.

とはいえ、1900番台でレーティングフルボッコになりそうで涙目だった状態から、華麗な900番台への転生で歓喜の舞.

一つの問題が受け取れる投票はM個がマックスなので、現在スコア+MがP番目のスコア以上になれば基本的には候補になる.
が、投票数が多すぎる場合はP番目のスコアにも投票をまぶさざるえなく、その処理がとても大変だった.
というか、適当に書いたのによく通ったなあというのが正直なところ.
厳密にはどっかに穴がありそう…….

package main

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

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

func main() {
    N := readInt()
    M := readInt()
    V := readInt()
    P := readInt()

    A := make([]int, N)
    for i := 0; i < N; i++ {
        A[i] = readInt()
    }
    sort.Sort(sort.Reverse(sort.IntSlice(A)))
    p := A[P-1]
    V -= P - 1
    b := A[P-1:]
    for {
        mv := M * V
        for i := 0; i < len(b); i++ {
            t := min(p-b[i], M)
            mv -= t
        }
        if mv > 0 {
            p += (mv + len(b) - 1) / len(b)
        } else {
            break
        }
    }

    result := 0
    for i := 0; i < N; i++ {
        if A[i]+M >= p {
            result++
        }
    }
    fmt.Println(result)
}

const (
    ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
    result := bufio.NewScanner(os.Stdin)
    result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
    result.Split(bufio.ScanWords)
    return result
}()

func readString() string {
    stdinScanner.Scan()
    return stdinScanner.Text()
}

func readInt() int {
    result, err := strconv.Atoi(readString())
    if err != nil {
        panic(err)
    }
    return result
}