[PYTHON] AtCoder Débutant Contest 176 Rapport de participation

AtCoder Débutant Contest 176 Rapport de participation

ABC176A - Takoyaki

Percer en 2 minutes. Il suffit d'écrire.

N, X, T = map(int, input().split())

print((N + X - 1) // X * T)

ABC176B - Multiple of 9

Percer en une minute et demie. Il suffit d'écrire.

N = input()

if sum(int(c) for c in N) % 9 == 0:
    print('Yes')
else:
    print('No')

Il semble que ce qui suit était également bon en Python.

N = int(input())

if N % 9 == 0:
    print('Yes')
else:
    print('No')

ABC176C - Step

Percer dans environ 3 minutes. Si la personne précédente est plus haute, répétez simplement l'ajout sur la table à la même hauteur que la personne précédente.

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

Percer en 81 minutes, TLE × 2. Je faisais attention que si je ne l'implémentais pas correctement, j'irais à l'endroit où je pourrais aller avec une chaîne en 2 fois. S'il n'y a qu'une seule file d'attente, * O * (* HW) Puisqu'il serait nécessaire de scanner *), si je faisais deux files d'attente et essayais de déformer uniquement à partir des cellules visitées par BFS, la quantité de calcul qui pourrait être AC était atteinte.

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...)
}

J'ai fini par être net, mais j'ai réussi à le faire avec 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

Je ne pouvais pas percer. Si je pouvais résoudre le problème D 10 minutes plus tôt ... Ou plutôt, si je sautais D et touchais celui-ci ...

Addendum: C'est évidemment plus facile que le problème D. Sélectionnez la verticale et l'horizontale avec le plus de cibles d'explosion (notez qu'il peut y avoir plusieurs candidats). Double compte s'il y a des cibles d'explosion à la position d'installation de la bombe Il est nécessaire de soustraire 1 car cela devient. Si vous essayez de vous rappeler s'il existe une cible d'explosion à l'emplacement d'installation de la bombe avec un simple tableau bidimensionnel, 6 × 10 10 </ sup> bits = 7,5 Go de capacité de stockage sont nécessaires Par conséquent, il est mémorisé par l'ensemble du ruban de la position.

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)

Recommended Posts

AtCoder Beginner Contest 181 Rapport de participation
AtCoder Beginner Contest 161 Rapport de participation
AtCoder Beginner Contest 151 Rapport de participation
AtCoder Débutant Contest 176 Rapport de participation
AtCoder Beginner Contest 154 Rapport de participation
AtCoder Beginner Contest 166 Rapport de participation
AtCoder Beginner Contest 153 Rapport de participation
AtCoder Beginner Contest 145 Rapport de participation
AtCoder Débutant Contest 184 Rapport de participation
AtCoder Beginner Contest 165 Rapport de participation
Rapport de participation au concours AtCoder Débutant 160
AtCoder Beginner Contest 169 Rapport de participation
AtCoder Beginner Contest 178 Rapport de participation
AtCoder Beginner Contest 163 Rapport de participation
AtCoder Beginner Contest 159 Rapport de participation
AtCoder Beginner Contest 164 Rapport de participation
AtCoder Beginner Contest 168 Rapport de participation
Rapport de participation au concours AtCoder Débutant 150
AtCoder Beginner Contest 158 Rapport de participation
Rapport de participation au concours AtCoder Débutant 180
AtCoder Beginner Contest 156 Rapport de participation
AtCoder Beginner Contest 162 Rapport de participation
AtCoder Débutant Contest 157 Rapport de participation
AtCoder Beginner Contest 167 Rapport de participation
AtCoder Débutant Contest 179 Rapport de participation
Concours AtCoder Débutant 182
AtCoder Beginner Contest 146 Rapport de participation
AtCoder Beginner Contest 152 Rapport de participation
AtCoder Débutant Contest 155 Rapport de participation
AtCoder Beginner Contest 174 Rapport de participation
AtCoder Beginner Contest 171 Rapport de participation
AtCoder Beginner Contest 149 Rapport de participation
AtCoder Beginner Contest 148 Rapport de participation
AtCoder Débutant Contest 170 Rapport de participation
AtCoder Débutant Contest 183 Rapport de participation
Note de participation au concours pour débutants AtCoder # 003
AtCoder Grand Contest 041 Rapport de participation
AtCoder Grand Contest 040 Rapport de participation
Rapport de participation au concours régulier AtCoder 105
AtCoder Regular Contest 104 Rapport de participation
Fiche d'inscription au concours ACL pour débutant
Journal de participation Atcoder Beginner Contest 146
AtCoder Chokudai Contest 005 Rapport de participation
AtCoder Grand Contest 047 Rapport de participation
Concours AtCoder Débutant 177
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
Concours AtCoder Débutant 173
Concours Atcoder Débutant 153
Rapport de participation au concours de programmation AtCoder HHKB 2020
Rapport de participation au concours de programmation AtCoder Acing 2020
Rapport de participation au concours de programmation AtCoder Keyence 2020
Rapport de participation au concours de programmation AtCoder Panasonic 2020
Critique du concours AtCoder Beginner Contest 152
Concours AtCoder Débutant 181 Remarque
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178