AtCoder Beginner Contest 176 参戦記
ABC176A - Takoyaki
2分で突破. 書くだけ.
N, X, T = map(int, input().split())
print((N + X - 1) // X * T)
ABC176B - Multiple of 9
1分半で突破. 書くだけ.
N = input()
if sum(int(c) for c in N) % 9 == 0:
print('Yes')
else:
print('No')
Python では以下でも良かったらしい. なんだかなあ.
N = int(input())
if N % 9 == 0:
print('Yes')
else:
print('No')
ABC176C - Step
3分くらいで突破. 前の人のほうが高ければ、前の人と同じ高さまで台で足すを繰り返すだけ.
N, *A = map(int, open(0).read().split())
result = 0
p = A[0]
for i in range(1, N):
if p >= A[i]:
result += p - A[i]
else:
p = A[i]
print(result)
ABC176D - Wizard in Maze
81分で突破、TLE×2. 下手に実装すると1回のワープで行けるところに2回で行ってしまいそうで気を使った. キューが一つだとワープの処理で O(HW) のスキャンが必要になってしまうので、キューを2つにして、BFS で訪れたマスからだけワープを試みるようにしたら、AC できる計算量になった.
package main
import (
"bufio"
"fmt"
"math"
"os"
"strconv"
)
func min(x, y int) int {
if x < y {
return x
}
return y
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
func main() {
defer flush()
H := readInt()
W := readInt()
Ch := readInt() - 1
Cw := readInt() - 1
Dh := readInt() - 1
Dw := readInt() - 1
S := make([]string, H)
for i := 0; i < H; i++ {
S[i] = readString()
}
t := make([][]int, H)
for i := 0; i < H; i++ {
t[i] = make([]int, W)
for j := 0; j < W; j++ {
if S[i][j] == '#' {
t[i][j] = -1
} else {
t[i][j] = math.MaxInt64
}
}
}
warpCount := 0
t[Ch][Cw] = warpCount
q := make([][2]int, 0, 1024)
q = append(q, [2]int{Ch, Cw})
warpq := make([][2]int, 0, 1024)
for len(q) != 0 {
for len(q) != 0 {
warpq = append(warpq, q[0])
h, w := q[0][0], q[0][1]
q = q[1:]
if h-1 >= 0 && t[h-1][w] > warpCount {
q = append(q, [2]int{h - 1, w})
t[h-1][w] = t[h][w]
}
if h+1 < H && t[h+1][w] > warpCount {
q = append(q, [2]int{h + 1, w})
t[h+1][w] = t[h][w]
}
if w-1 >= 0 && t[h][w-1] > warpCount {
q = append(q, [2]int{h, w - 1})
t[h][w-1] = t[h][w]
}
if w+1 < W && t[h][w+1] > warpCount {
q = append(q, [2]int{h, w + 1})
t[h][w+1] = t[h][w]
}
}
if t[Dh][Dw] != math.MaxInt64 {
break
}
warpCount++
for i := 0; i < len(warpq); i++ {
h, w := warpq[i][0], warpq[i][1]
for i := max(0, h-2); i <= min(H-1, h+2); i++ {
for j := max(0, w-2); j <= min(W-1, w+2); j++ {
if t[i][j] <= warpCount {
continue
}
t[i][j] = warpCount
q = append(q, [2]int{i, j})
}
}
}
warpq = warpq[:0]
}
if t[Dh][Dw] == math.MaxInt64 {
println(-1)
} else {
println(t[Dh][Dw])
}
}
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
}
var stdoutWriter = bufio.NewWriter(os.Stdout)
func flush() {
stdoutWriter.Flush()
}
func println(args ...interface{}) (int, error) {
return fmt.Fprintln(stdoutWriter, args...)
}
カリカリにチューンする羽目になったが、Python でもなんとか通せた.
from collections import deque
def main():
from sys import stdin
readline = stdin.readline
from builtins import max, min, range
INF = 10 ** 6
H, W = map(int, readline().split())
Ch, Cw = map(lambda x: int(x) - 1, readline().split())
Dh, Dw = map(lambda x: int(x) - 1, readline().split())
S = [readline()[:-1] for _ in range(H)]
t = [[INF] * W for _ in range(H)]
for h in range(H):
th = t[h]
Sh = S[h]
for w in range(W):
if Sh[w] == '#':
th[w] = -1
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])
warp_count = 0
warpq = []
while q:
while q:
warpq.append(q[0])
h, w = q.popleft()
if h - 1 >= 0 and t[h - 1][w] > warp_count:
q.append((h - 1, w))
t[h - 1][w] = warp_count
if h + 1 < H and t[h + 1][w] > warp_count:
q.append((h + 1, w))
t[h + 1][w] = warp_count
if w - 1 >= 0 and t[h][w - 1] > warp_count:
q.append((h, w - 1))
t[h][w - 1] = warp_count
if w + 1 < W and t[h][w + 1] > warp_count:
q.append((h, w + 1))
t[h][w + 1] = warp_count
if t[Dh][Dw] != INF:
break
warp_count += 1
for h, w in warpq:
for i in range(max(0, h - 2), min(H, h + 3)):
ti = t[i]
for j in range(max(0, w - 2), min(W, w + 3)):
if ti[j] > warp_count:
ti[j] = warp_count
q.append((i, j))
warpq.clear()
if t[Dh][Dw] == INF:
print(-1)
else:
print(t[Dh][Dw])
main()
ABC176E - Bomber
突破できず. あと10分早くD問題が解けていたら……. というか、Dを飛ばしてこっちに手を付けていたら…….
追記: D問題より明らかにこっちのほうが簡単. 一番爆破対象の多い縦と横をそれぞれ選ぶ(複数候補がある可能性があることに注意). 爆弾設置位置に爆破対象がある場合はダブルカウントになるので1引く必要がある. 爆弾設置位置に爆破対象があるかを単純な二次元配列で覚えようとすると 6×1010 ビット= 7.5GB の記憶容量が必要になるので、位置のタプルの set で記憶する.
H, W, M = map(int, input().split())
rows = [0] * H
cols = [0] * W
s = set()
for _ in range(M):
h, w = map(lambda x: int(x) - 1,input().split())
rows[h] += 1
cols[w] += 1
s.add((h, w))
max_rows = max(rows)
max_cols = max(cols)
max_rows_indexes = [i for i in range(H) if rows[i] == max_rows]
max_cols_indexes = [i for i in range(W) if cols[i] == max_cols]
duplicate = True
if M >= len(max_rows_indexes) * len(max_cols_indexes):
for h in max_rows_indexes:
for w in max_cols_indexes:
if (h, w) not in s:
duplicate = False
break
if not duplicate:
break
else:
duplicate = False
if duplicate:
print(max_rows + max_cols - 1)
else:
print(max_rows + max_cols)