AtCoder Beginner Contest 144 参戦記

ABC144A - 9x9

2分で突破. 書くだけ.

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

if A < 10 and B < 10:
    print(A * B)
else:
    print(-1)

ABC144B - 81

7分で突破. 書くだけだったんだけど、コードテストが正しく動かなくて(何故か標準出力が戻ってこない)、無駄に時間を使ってしまった.

from sys import exit

N = int(input())

for i in range(1, 10):
    for j in range(1, 10):
        if N == i * j:
            print('Yes')
            exit()
print('No')

ABC144C - Walk on Multiplication Table

5分で突破. できるだけ小さい数の掛け合わせがいいので、sqrt から下ろしていけばいいよなと瞬時に思いついたので、あとは書くだけだったのだが、コードテストが不調でローカルで入出力例を動かす羽目になったので時間が無駄にかかってしまった.

from math import sqrt
from sys import exit

N = int(input())

for i in range(int(sqrt(N)) + 1, -1, -1):
    if N % i == 0:
        print((i - 1) + (N // i - 1))
        exit()

ABC144D - Water Bottle

突破できず. WA, RE が1個づつ残ってしまった. 解説を見たら、半分未満の方の式の atan を asin と取り違えていた. 三角関数なんて嫌いだー. (というか、atan とか初めて使ったぞ)

from math import atan, pi

a, b, x = map(int, input().split())

if x >= a * a * b / 2:
    print(atan((a*a*b-x)/(a*a*a/2))/(2 * pi)*360)
else:
    print(90 - atan(x/(a*b*b/2))/(2 * pi)*360)

ABC144E - Gluttony

突破できず. A を昇順ソートして、F を降順ソートするところまではひと目だったけど、A を1づつ減らしていくのは K≤10¹⁸ だから TLE 必死だしでフリーズして終了.

解説動画を見てゴールの方を二分探索で動かすのかーと感動. 動かすものが違うだけの Educational DP Contest の2つのナップサック問題を思い出して、応用できなかったなあと思ったり. 予習してはあったけど、過去問で必要とする問題にまだ遭遇できてなくて使ったことがなかっためぐる式二分探索を初めて書いて AC.

# PyPy なら通る
def is_ok(x):
    trainings = 0
    for i in range(N):
        t = A[i] - x // F[i]
        if t > 0:
            trainings += t
    return trainings <= K


N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse=True)

ng = -1
ok = A[-1] * F[0]
while ok - ng > 1:
    m = ng + (ok - ng) // 2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

package main

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

func main() {
    N := readInt()
    K := readInt()
    A := readInts(N)
    F := readInts(N)

    sort.Ints(A)
    sort.Sort(sort.Reverse(sort.IntSlice(F)))

    isOk := func(x int) bool {
        trainings := 0
        for i := 0; i < N; i++ {
            t := A[i] - x/F[i]
            if t > 0 {
                trainings += t
            }
        }
        return trainings <= K
    }

    ng := -1
    ok := A[N-1] * F[0]
    for ok-ng > 1 {
        m := ng + (ok-ng)/2
        if isOk(m) {
            ok = m
        } else {
            ng = m
        }
    }
    fmt.Println(ok)
}

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
}

func readInts(n int) []int {
    result := make([]int, n)
    for i := 0; i < n; i++ {
        result[i] = readInt()
    }
    return result
}