Résolvez "AtCoder version! Arimoto (Débutant)" avec Python!

Version AtCoder! Arimoto (Débutant) sera résolu en détail avec Python.

1 Toutes les bases "Recherche complète"

Recherche complète 1-1 bit

ABC 045 C-Many formules

image.png

【répondre】

S = list(input())

ans = 0
for i in range(2**(len(S)-1)):
    plus = [""]*(len(S))
    fomula = ""
    for j in range(len(S)-1):
        if(i>>j & 1):
            plus[j] = "+"
    
    for i in range(len(S)):
        fomula += S[i] + plus[i]
    ans += eval(fomula)
    
print(ans)

ABC 104 C - All Green image.png image.png

__ [Explication] __ Recherchez tous les bits pour ne pas prendre de bonus. Prenez un bonus et choisissez les points manquants restants parmi celui avec le score le plus élevé.

【répondre】

D,G = map(int,input().split())
l = list(list(map(int, input().split())) for _ in range(D))

#Trier par ordre décroissant de score
l = l[::-1]

ans = float("inf")
for i in range(2**D):
    total = 0
    cnt = 0
    for j in range(D):
        if (i>>j)&1:
            total += 100*(D-j)*l[j][0] + l[j][1]
            cnt += l[j][0]
    if total >= G:
        ans = min(ans,cnt)
        continue
    for j in range(D):
        if (i>>j)&1 == False:
            for k in range(l[j][0]):
                total += 100*(D-j)
                cnt+=1
                if total >= G:
                    ans = min(ans,cnt)
                    break
            break

print(ans)

1-2 DFS (recherche de priorité de profondeur)

Recherche prioritaire ATC 001 A en profondeur

__ [Explication] __ DFS (Depth-First Search) est une image qui recherche tout le chemin vers l'arrière, et lorsqu'il n'y a rien à rechercher, retourne à l'endroit où vous n'avez pas cherché et recherche à nouveau. Implémentez en utilisant Stack qui est LIFO (Last-In First-Out). image.png

【répondre】

from collections import deque

def dfs(maze, sh, sw):
    #Initialiser la liste atteinte
    visited = [[0]*W for _ in range(H)]

    stack = deque([[sh,sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.pop()
        if maze[h][w] == "g":
            return("Yes")
        for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
            new_h, new_w = h+i, w+j
            if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                continue
            elif maze[new_h][new_w] != "#" and visited[new_h][new_w] == 0:
                visited[new_h][new_w] = 1
                stack.append([new_h, new_w])
    return("No")

H,W = map(int,input().split())
maze = [input() for _ in range(H)]

#Trouvez la position de départ
for i in range(H):
    if maze[i].find("s") != -1:
        sh = i
        sw = maze[i].find("s")
        
print(dfs(maze, sh, sw))

1-3 BFS (recherche de priorité de largeur)

Recherche de priorité de largeur ABC 007 C

__ [Explication] __ BFS (recherche en largeur en premier) est une image de recherche de peu profonde à superficielle. Implémentez en utilisant Queue qui est FIFO (First-In First-Out). image.png

【répondre】

from collections import deque

def dfs(maze, sh, sw, gh ,gw):
    #Initialiser la liste atteinte
    visited = [[-1]*W for _ in range(H)]

    stack = deque([[sh,sw]])
    visited[sh][sw] = 0
    while stack:
        h, w = stack.popleft()
        if h == gh and w == gw :
            return(visited[h][w])
        for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
            new_h, new_w = h+i, w+j
            if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                continue
            elif maze[new_h][new_w] != "#" and visited[new_h][new_w] == -1:
                visited[new_h][new_w] = visited[h][w] + 1
                stack.append([new_h, new_w])
    return("No")

H,W = map(int,input().split())
sh,sw = map(int, input().split())
gh,gw = map(int, input().split())
maze = [input() for _ in range(H)]

print(dfs(maze, sh-1, sw-1, gh-1, gw-1))

1-4 Liste des conditions spéciales

ABC 054 C One-stroke Path

__ [Explication] __ Utilisez des permutations pour énumérer toutes les façons de connecter des graphiques. Jugez s'ils sont correctement connectés et comptez-les.

【répondre】

from itertools import permutations

N,M = map(int, input().split())
l = [list(map(int,input().split())) for _ in range(M)]

graph = [[False]*(N+1) for _ in range(N+1)]
for i in l:
    graph[i[0]][i[1]] = True
    graph[i[1]][i[0]] = True

cnt = 0

for i in permutations(range(1,N+1)):
    #Considérez le point de départ à partir de 1
    if i[0] != 1:
        continue
    isJoin = True
    for j in range(1,N):
        if not graph[i[j-1]][i[j]]:
            isJoin = False
            break
    if isJoin:
        cnt += 1

print(cnt)

Arrangement de carte J de qualification JOI 2009

__ [Explication] __ Utilisez des permutations pour énumérer la disposition des entiers. Créez des entiers triés à l'aide de map et join, ajoutez-les à dic et répondez enfin au nombre d'entiers dans dic.

【répondre】

from itertools import permutations

N = int(input())
S = int(input())
l = [int(input()) for _ in range(N)]
dic = {}
for i in permutations(l,S):
    i = map(str,i)
    dic[("".join(i))] = 1

print(len(dic))

2 Ruée vers la folie! "Méthode gourmande"

__ Qu'est-ce que la méthode de la cupidité __

  1. Divisez le problème en plusieurs sous-problèmes
  2. Évaluer la solution pour chaque sous-problème (il existe plusieurs modèles de solution possibles pour chaque sous-problème)
  3. Évaluer la solution du sous-problème suivant (également possible de plusieurs manières), avec celle avec la meilleure évaluation comme solution de ce sous-problème (= solution optimale locale)

Citation: j'ai essayé de résoudre une méthode simple de cupidité

2-1 Problème des pièces

JOI 2007 Qualifying A Change

__ [Explication] __ Comptez le nombre de pièces de la plus grosse pièce.

【répondre】

N = int(input())

N = 1000 - N
cnt = 0

l = [500,100,50,10,5,1]

for i in l:
    cnt += N // i
    N = N - i*(N//i)

print(cnt)

2-2 Problème de planification de section

Concours de programmation Keyence 2020 B - Robot Arms

__ [Explication] __ Tout d'abord, triez par la position de l'extrémité droite du bras du robot. Regardez la position la plus à droite dans l'ordre de gauche, et si elles se chevauchent, excluez-les. S'ils ne se chevauchent pas, mettez à jour la position la plus à droite.

【répondre】

N = int(input())
l = [list(map(int,input().split())) for _ in range(N)]

ans = N
for i in l:
    x = 0 if i[0]-i[1] < 0 else i[0]-i[1]
    i[1] = i[0]+i[1]
    i[0] = x
    
l.sort(key=lambda x:x[1])

right = 0
for i in range(N):
    if right > l[i][0]:
        ans-=1
    else:
        right = l[i][1]

print(ans)

2-3 Gourmand cherchant le plus petit dans l'ordre lexical

ABC 076 C Dubious Document 2

__ [Explication] __ Tout d'abord, quelle est la chaîne de caractères de T et le nombre de caractères restants comme indiqué ci-dessous? Préparez la liste SS remplie.

coder??
?coder?
??coder

Comparez la liste de caractères créée SS avec le caractère donné par caractère.

    1. Si la lettre S'correspond à "?" Ou SS → Tel quel
  1. Quand la lettre S n'est pas "?" Et la lettre SS est "?" → Convertir SS "?" En S'character
    1. Autrement → Chaînes de caractères qui ne peuvent pas être créées

Après cela, remplissez le "?" Restant dans le SS avec "a" pour qu'il soit le plus petit dans l'ordre du dictionnaire. 【répondre】

S = input()
T = input()

n = len(S)-len(T)+1
ans = []
for i in range(n):
    SS = list("?"*(i) + T + "?"*(n-i-1))
    flag = True
    for i in range(len(S)):
        if S[i]=="?" or S[i]==SS[i]:
            pass
        elif S[i]!="?" and SS[i]=="?":
            SS[i] = S[i]
        else:
            flag = False
    if flag:
        ans.append("".join(SS).replace("?","a"))

if ans:
    ans.sort()
    print(ans[0])
else:
    print("UNRESTORABLE")

2-4 Greedy prend une place plus stricte

ABC 083 C Multiple Gift

__ [Explication] __ Le plus petit qui est plus grand que le nombre précédent et est un multiple est doublé. Par conséquent, doublez-le et vérifiez jusqu'à ce qu'il dépasse Y.

【répondre】

X,Y = map(int,input().split())

cnt=0
while X<=Y:
    cnt+=1
    X = X*2

print(cnt)

Empilement ARC 006 C

__ [Explication] __ Regardez le poids de la boîte en haut de l'avant, et si vous pouvez la mettre, mettez-la. Si vous ne pouvez pas le mettre, répétez la comparaison avec la boîte au sommet de la montagne suivante.

【répondre】

N = int(input())
W = [int(input()) for _ in range(N)]

l=[float("inf")]
for w in W:
    flag=True
    for i in range(len(l)):
        if l[i]>=w:
            l[i] = w
            flag=False
            break
    if flag:
        l.append(w)
        
print(len(l))

3 Souvenez-vous et réutilisez la «planification dynamique»

3-1 01 Problème de sac à dos

AOJ Course 0-1 Knapsack Problem

__ [Explication] __ dp [i] [j] ・ ・ ・ Cela signifie la solution optimale jusqu'au poids j en utilisant les bagages jusqu'au i-ème. ・ Lorsque w [i]> j Ce bagage ne peut pas être mis, alors mettez à jour avec la solution optimale pour le bagage précédent.

・ Lorsque w [i] ≤ j Pensez à quand mettre le i-ème bagage. Puisque le poids w [i] augmentera, la valeur v [i] sera ajoutée à la solution optimale du poids de j-w [i] jusqu'au i-1er. Après cela, prenez le maximum lorsque le i-ème bagage n'est pas déposé.

Citation: Mémorandum de Tsubasa Méthode de planification dynamique (sur le problème du sac à dos) Il y a un chiffre et c'est très facile à comprendre.

【répondre】

N,W = map(int,input().split())

v = [0] * N
w = [0] * N
for i in range(N):
    v[i],w[i] = map(int,input().split())

dp = [[0] * (W+1) for _ in range(N)]

for i in range(N):
    for j in range(1, W+1):
        if w[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],v[i]+dp[i-1][j-w[i]])

print(max(dp[N-1]))

Concours TDPC A

__ [Explication] __ Problème de somme partielle.

Lors de la vérification si l'entrée peut être de 3 à 5 Si 2 en 5-3 est True, vous pouvez le définir sur 5! Je vais chercher avec le sentiment.

Flux de données dp au moment de la liste d'entrée [2,3]. dp[1][2] = dp[0][2-2] = dp[0][0] = True dp[2][3] = dp[1][3-3] = dp[1][0] = True dp[2][5] = dp[1][5-3] = dp[1][2] = True [0,2,3,5] devient Vrai.

【répondre】

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

_sum = sum(l)
dp = [[False]*(_sum+1) for _ in range(N+1)]
dp[0][0] = True

for i in range(1,N+1):
    for j in range(_sum+1):
        if l[i-1]>j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j] or dp[i-1][j-l[i-1]]

print(sum(dp[N]))

Recommended Posts

Résolvez "AtCoder version! Arimoto (Débutant)" avec Python!
Résolvez AtCoder 167 avec python
Résolvez AtCoder ABC166 avec python
Recommandation de résolution des problèmes d'AtCoder avec python (20200517-0523)
Livre de fourmis avec python (Chapter3 édition intermédiaire ~)
[AtCoder] Résoudre ABC1 ~ 100 Un problème avec Python
Résoudre AtCoder ABC168 avec python (A ~ D)
J'ai essayé de résoudre l'édition du débutant du livre des fourmis avec python
[AtCoder] Résoudre un problème de ABC101 ~ 169 avec Python
Résoudre des maths avec Python
Résolvez AtCoder Débutant Contest 170 D - Non divisible (ABC170D) avec python (tamis Eratostenes)
Résolvez POJ 2386 avec python
Vérifier la version avec python
Essayez de résoudre le livre des défis de programmation avec python3
[Python] Résoudre des équations avec sympy
Bleu clair avec AtCoder @Python
Spécifiez la version python avec virtualenv
Web scraping débutant avec python
Concours Atcoder Débutant 152 Kiroku (python)
Résolvez AtCoder Beginner Contest159 D --Banned K (ABC159D) avec python (le compte est trop lent!)
Résolution avec Ruby et Python AtCoder ABC133 D Somme cumulée
Résolvez le livre en spirale (algorithme et structure de données) avec python!
solveur> Lien> Résoudre le solveur Excel avec python
Résoudre ABC163 A ~ C avec Python
Résoudre ABC166 A ~ D avec Python
Résoudre Atcoder ABC169 A-D avec Python
Jouons avec Excel avec Python [Débutant]
Résoudre ABC168 A ~ C avec Python
[Débutant] Extraire des chaînes de caractères avec Python
Résolu AtCoder ABC 114 C-755 avec Python3
Résoudre ABC162 A ~ C avec Python
Résoudre ABC167 A ~ C avec Python
Gérez chaque version de Python avec Homebrew
Résoudre ABC158 A ~ C avec Python
Livre Ali en python: Graphique Sec.2 à 5
AtCoder Beginner Contest 174 C Problème (Python)
AtCoder ARC104 B Somme cumulative résolue en Ruby, Python et Java
Livre Ali en python: page 42 numéros
Livre en spirale en Python! Python avec un livre en spirale! (Chapitre 14 ~)
Livre Ali en python: Auto-implémentation de la file d'attente prioritaire
Livre Ali en python: Sec.2-4, structure de données
Livre Ali en python: méthode Dyxtra Sec.2-5
atCoder 173 Python
Je voulais résoudre ABC160 avec Python
Mémo Atcoder débutant Python @ Keyence 2020, problème ABC
Livre Ali en python: page 43 Planification des sections
order_by ('-created_at') ← Qu'est-ce que "ー"? ?? ?? [Le débutant apprend le python avec un livre de référence]
Livre Ali en python: Sec.2 à 5 Graph (préparation)
[Python] Résolvez 10 problèmes d'élite passés d'Atcoder
Résolution avec Ruby, Perl, Java et Python AtCoder ABC 047 C Expression régulière
Solve Lake Counting (POJ n ° 2386) avec Python3
Livre de fourmis en python: page 49 Réparation de clôture
Résoudre avec Ruby et Python AtCoder ABC084 D Somme cumulative des nombres premiers
Jeu à la main en Python (commençons avec AtCoder?)
Livre Ali en python: Sec.2-3, Dynamic Planning (DP)
Résolvons des équations linéaires simultanées avec Python sympy!
Je voulais résoudre NOMURA Contest 2020 avec Python