AtCoder ABC 176 Python (A ~ E)

Résumé

A, B, C résolus. Je pense que D et E peuvent être résolus dans un peu plus de temps, mais je n'ai pas pu les résoudre au moment du concours, et c'est devenu AC à une date ultérieure.

problème

https://atcoder.jp/contests/abc176

A. Takoyaki

Répondre

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

if N % X == 0:
    ans = (N // X) * T
else:
    ans = (N // X) * T + T

print(ans)

Les cas ont été divisés selon que le nombre N de takoyaki à fabriquer est ou non un multiple de X, qui est la capacité maximale de la machine à takoyaki.

B. Multiple of 9

Répondre

N = list(str(input()))

total = 0
for i in range(len(N)):
    total += int(N[i])

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

Vers l'énoncé du problème

"L'entier N est un multiple de 9, et la somme des nombres de chaque chiffre lorsque N est exprimé en décimal est un multiple de 9."

Puisqu'il a écrit un indice, je vais le déposer dans le code tel quel. N'avez-vous pas besoin de cet indice? J'ai pensé.

C. Step

Répondre

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

total = 0
for i in range(N-1):
    if A[i] > A[i+1]:
        diff = A[i] - A[i+1]
        total += diff
        A[i+1] += diff

print(total)

Comparez le courant A [i] avec le prochain A [i + 1], et si A [i + 1] est plus grand, ajoutez la différence.

C'était facile pour le problème C, donc je craignais qu'il y ait des pièges avant de soumettre, et j'ai pensé qu'il pourrait y avoir quelque chose parce que la valeur maximale de A, qui est une contrainte, est aussi grande que 10 ** 9. J'ai essayé de l'éteindre pour le moment et c'est passé.

D. Wizard in Maze

Réponse (je la transmettrai avec AC pypy à une date ultérieure. Python est TLE)

#---------------------------------[importer]---------------------------------#
from collections import deque
#---------------------------------[Réception d'entrée / réglage initial]---------------------------------#
H, W = map(int, input().split())
C = tuple(map(int, input().split())) #Position magique
D = tuple(map(int, input().split())) #objectif
D_y = D[0] -1 #0 début
D_x = D[1] -1 #0 début
S = [list(input()) for _ in range(H)]
visited = [[-1] * W for _ in range(H)]
visited[C[0]-1][C[1]-1] = 0 #valeur initiale
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] #Mouvement ordinaire
main_q = deque()
magic_q = deque() #Cue pour la magie
main_q.append((C[0]-1, C[1]-1))
#---------------------------------[BFS]---------------------------------#
while main_q:
    y, x = main_q.popleft()
    magic_q.append((y, x))
    for move in moves:
        dy, dx = move
        moved_y = y + dy
        moved_x = x + dx

        if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
            continue
        if S[moved_y][moved_x] == '#':
            continue
        if S[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
            main_q.append((moved_y, moved_x))
            visited[moved_y][moved_x] = visited[y][x]
    #---------------------------------[BFS pour la magie]---------------------------------#
    if not main_q: # main_Si q devient vide, utilisez la magie de la recherche
        while magic_q:
            y, x = magic_q.popleft()
            for dy in range(-2, 3):
                for dx in range(-2, 3):
                    moved_y = y + dy
                    moved_x = x + dx

                    if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
                        continue
                    if S[moved_y][moved_x] == '#':
                        continue
                    if S[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
                        main_q.append((moved_y, moved_x))
                        visited[moved_y][moved_x] = visited[y][x] + 1
#---------------------------------[Affichage des réponses]---------------------------------#
answer = visited[D_y][D_x]
print(answer)

Au moment où j'ai lu le problème, j'ai pensé que je ne pouvais pas le résoudre avec BFS, mais je ne pouvais pas le résoudre au moment du concours car je ne pouvais pas le mettre en œuvre correctement en utilisant la magie.

La politique est

1. Premièrement, déplacez-vous normalement avec le mouvement A (ici, implémentez le premier BFS)
2. Après avoir effectué tout le mouvement A, essayez le mouvement B avec la magie à partir de l'endroit recherché par le mouvement A (stocké dans magic_q```) (Implémentez le deuxième BFS ici)
3. Recommencez à vous déplacer avec le mouvement A à partir de l'emplacement recherché avec le mouvement B (stocké dans main_q```)
4. Répétez les étapes 1 à 3 ci-dessous. Lors du déplacement, enregistrez le nombre de fois où Magic a été utilisé dans visité
5. Le nombre de fois enregistré dans la destination `` visité '' est la réponse Ce sera.

En supposant que vous puissiez écrire un BFS normal, je pense que la clé de ce problème était de savoir si vous pouviez ou non implémenter "enregistrer le nombre de fois où Magic a été utilisé dans visité```.

Avec le code ci-dessus, il devient TLE en python et vous devez le passer avec pypy. Je pense que python fonctionnera si vous le concevez, mais je ne l'ai pas amélioré car le code tel qu'il est est plus facile à comprendre pour moi.

E. Bomber

Réponse (AC à une date ultérieure)

import numpy as np

H, W, M = map(int, input().split())
row = np.zeros(W)
col = np.zeros(H)
memo = []
for _ in range(M):
    h, w = map(int, input().split())
    h -=1
    w -=1
    row[w] += 1
    col[h] += 1
    memo.append((h, w))

col_max = col.max()
row_max = row.max()

max_col_indexes = np.where(col == col_max)[0]
max_row_indexes = np.where(row == row_max)[0]

ans = col_max + row_max -1
memo = set(memo)
for c in max_col_indexes:
    for r in max_row_indexes:
        if (c, r) not in memo:
            ans = col_max + row_max
            print(int(ans))
            exit()

print(int(ans))

La politique a été décidée immédiatement et j'ai appliqué le code, mais je ne pouvais pas réduire la quantité de calcul et je ne pouvais pas AC au moment du concours.

En tant que politique

1. Comptez les bombes qui existent dans chaque ligne et colonne, et obtenez le nombre maximum de bombes (ligne max, colonne max) pour chaque ligne et colonne, et le numéro de ligne et le numéro de colonne qui seront max.
2. Si vous comptez des bombes avec le même numéro de ligne et le même numéro de colonne que max, `` `row max + column max -1 '' est la réponse
3. Si vous ne comptez pas les bombes avec les mêmes numéros de ligne et de colonne que max, `row max + column max `répondra
4. Pour déterminer si les mêmes bombes sont comptées en lignes et en colonnes, vérifiez s'il y a des bombes aux coordonnées maximales du numéro de ligne et du numéro de colonne. est.

Si vous ne mettez pas `` memo = set (memo) '' dans le code, ce sera TLE.