[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part3 / 22]

** Visez un codeur bleu clair! !! !! !! !! !! ** **

Alors [Directives pour améliorer AtCoder, un pro de la compétition enseigné par Red Coder [Édition intermédiaire: Visez Light Blue Coder! ]]( https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7 % B4% 9A% E8% 80% 85% E3% 81% 8C% E8% A7% A3% E3% 81% 8F% E3% 81% B9% E3% 81% 8D% E9% 81% 8E% E5% 8E % BB% E5% 95% 8F% E7% B2% BE% E9% 81% B8-100-% E5% 95% 8F) (@ e869120)

AtCoder a rassemblé 100 bonnes questions éducatives qui conviennent aux codeurs marron et vert afin d'obtenir un codeur bleu clair, ou une note de 1200, avec un petit nombre de questions.

100 questions passées que les débutants et les intermédiaires devraient résoudre dans cet article` Sera résolu avec ** Python **! Merci à @ e869120! !! !! !! !! !!

Lien vers l'article précédent

** Rechercher tout: Tout lister ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part1 / 22] ** Recherche complète: toute énumération pour réduire le nombre de rues en concevant ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part2 / 22] ** Recherche complète: recherche complète de bits ** [[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part3 / 22]] (https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f) ** Recherche complète: avant la recherche complète ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part4 / 22] ** Recherche par section ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part5 / 22] ** Recherche de priorité de profondeur ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part6 / 22] ** Recherche de priorité de largeur ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part7 / 22]

** (Ajouté le 07/05/2020) **

"Partie 3" ~ Recherche complète de bits ~

Nous allons résoudre les 5 questions suivantes!

Recherche complète: recherche complète de bits

10 ALDS_5_A --Un problème de base à tour de rôle. 11 AtCoder Beginner Contest 128 C - Switches 12 Concours AtCoder Débutant 002 D --Faction 13 JOI 2008 Qualifying 5-Osenbei C'est un peu difficile pour le codeur brun, mais il est recommandé de le résoudre. 14 Square869120Concours # 4 B - Les bâtiments sont colorés! C'est un problème difficile qui ne peut pas être résolu facilement, mais si vous le résolvez, vous gagnerez certainement en force.

10 ALDS_5_A - Aller-retour

** Nous avons développé indépendamment le modèle le plus puissant pour une recherche peu complète! bit = [i>>j&1 for j in range(N)]** Avec ce modèle Peu importe ce que la recherche complète vient ** Je n'ai plus peur de rien **

test.py


def I(): return int(input())
def LI(): return list(map(int,input().split()))
n = I()
A = LI()
q = I()
m = LI()
ans = 0
partial_sum = set()
for i in range(2**n):
    bit = [i>>j&1 for j in range(n)] #Modèle le plus fort
    partial_sum.add(sum([A[k]*bit[k] for k in range(n)]))
for x in m:
    print('yes' if x in partial_sum else 'no')

** (Ajouté le 04/05/2020) **
Une autre solution
Vous pouvez également le résoudre avec ** DFS **! C'est comme chercher jusqu'à la fin pour ajouter ou ne pas ajouter le chiffre suivant! ** Définir l'index et la somme **, le but est de stocker dans la pile! !! !!

** ◆ Ver récursif **

test.py


def I(): return int(input())
def LI(): return list(map(int,input().split()))
n = I()
A = LI()
q = I()
m = LI()
partial_sum = set()
def dfs(i,_sum):
    if i==n:
        partial_sum.add(_sum)
        return
    dfs(i+1,_sum)
    dfs(i+1,_sum+A[i])
dfs(0,0)
for x in m:
    print('yes' if x in partial_sum else 'no')

** ◆ Stack Ver **

test.py


def I(): return int(input())
def LI(): return list(map(int,input().split()))
n = I()
A = LI()
q = I()
m = LI()
partial_sum = set()
stack = [] #Mettre l'index et la somme
def dfs():
    stack.append([0,0])
    stack.append([0,A[0]])
    partial_sum.add(A[0])
    while stack:
        i,s = stack.pop()
        i += 1
        if i==n:
            partial_sum.add(s)
            continue
        stack.append([i,s])
        stack.append([i,s+A[i]])
dfs()
for x in m:
    print('yes' if x in partial_sum else 'no')

11 AtCoder Beginner Contest 128 C - Switches Difficulty:807 ** Le modèle le plus puissant pour la recherche de bits complets est un grand succès! ** ** L'énoncé du problème est un peu compliqué, mais je ferai de mon mieux pour le comprendre tout en regardant les exemples d'entrée / sortie. Puisqu'il y a un maximum de 10 commutateurs, il semble que vous puissiez rechercher tous les bits (en termes de calcul)! Si vous pouvez établir une politique, vous pouvez résoudre ce problème! !! !! ** Je n'ai plus peur de rien **

test.py


def LI(): return list(map(int,input().split()))
N,M = LI()
ks = [LI() for _ in range(M)]
p = LI()
ans = 0
for i in range(2**N):
    bit = [i>>j&1 for j in range(N)]
    for k,x in enumerate(ks):
        _,*s = x
        if p[k] != sum([bit[y-1] for y in s])%2:
            break
    else:
        ans += 1
print(ans)

12 AtCoder Beginner Contest 002 D --Faction

** Difficulté: 1405! !! !! Enfin le problème du niveau bleu clair! !! !! ** ** ** Je n'ai pas pu le résoudre à première vue! ** ** En plus de la recherche de bits complète, elle peut être plus facile à résoudre si vous connaissez les ** graphes. ** ** L'idée des graphes est également liée à DFS et BFS, donc je veux la maîtriser! !! !!

Pensez comme suit!

  1. Représentez les relations humaines avec un graphe non orienté.
  2. Chaque membre de la Diète fait-il partie d'une faction en recherche un peu complète? Pensez à toutes les façons dont il n'est pas inclus. Pour chacun des 3.2, des candidats aux réponses si tout le monde a une relation humaine entre eux!

test.py


import itertools
def LI(): return list(map(int,input().split()))
N,M = LI()
xy = [LI() for _ in range(M)]
ans = 1
graph = {i:[] for i in range(1,N+1)} #1_indexed
for a in xy:
    x,y = a
    graph[x].append(y)
    graph[y].append(x)
for i in range(2**N):
    bit = [i>>j&1 for j in range(N)]
    giinsuu = sum(bit)
    if giinsuu<=1:
        continue
    giinNO_bit1 = [k+1 for k in range(N) if bit[k]==1]
    for b,c in itertools.product(giinNO_bit1,repeat=2):
        if b==c:
            continue
        if not b in graph[c]:
            break
        if not c in graph[b]:
            break
    else:
        ans = max(ans,giinsuu)
print(ans)

Un complément détaillé au code

for b,c in itertools.product(giinNO_bit1,repeat=2):
    if b==c:
        continue
    if not b in graph[c]:
        break
    if not c in graph[b]:
        break
else:
    ans = max(ans,giinsuu)

ʻL'article précédent expliquant comment utiliser itertools.product et pour / else` [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part2 / 22] Puisqu'il est expliqué brièvement dans, veuillez vous y référer également ...

En outre, l'image de l'instruction if est un article antérieur [Python] ABC133B (problème du triangle supérieur droit) [At Coder] Une image du calcul de tout le «triangle droit supérieur» et «triangle inférieur gauche» dans le tableau qui apparaît dans cet article! !! !! Si vous avez une image de ce tableau, je pense que vous pouvez même le coder!

13 JOI 2008 Qualifying 5-Osenbei

** Je n'ai pas pu le résoudre à première vue! !! Cela peut être plus facile à résoudre si vous connaissez «Numpy» et «XOR» (somme logique exclusive «^»). ** **

J'ai pensé quand j'ai vu le code AC de personnes extraordinaires.

Pensez comme suit!

  1. Examiner tous les modèles de retournement / non retournement de toutes les lignes 2.1 Comptez le nombre de «1» dans chaque colonne pour chaque motif »(= noir)» Dans la version 3.2, nous pouvons envoyer le nombre «0» => c'est-à-dire «R-noir». Cependant, puisque la ligne peut également être retournée Le plus grand de «R-noir» et «noir»! La réponse est la somme de tous les résultats dans chaque colonne!

Le nombre de «1» dans chaque colonne peut être compté en ajoutant chaque colonne. (L'ajout de chaque colonne est le 18e de «Numpy»!)

test.py


import numpy as np
def LI(): return list(map(int,input().split()))
R,C = LI()
a = np.array([LI() for _ in range(R)])
ans = 0
for i in range(2**R):
    bit = np.array([[i>>j&1 for j in range(R)]]).T
    black = (a^bit).sum(axis=0)
    ans = max(ans,np.fmax(R-black,black).sum())
print(ans)

C'était un code étonnamment court!

Un complément détaillé au code

bit = np.array([[i>>j&1 for j in range(R)]]).T

«T» est une translocation, [Ce site] (https://deepage.net/features/numpy-transpose.html) Par conséquent, il ne sera efficace que si l'objectif de la translocation est de deux dimensions ou plus! La cible de la translocation est unidimensionnelle np.array([i>>j&1 for j in range(R)]).T Alors non.

Utilisez l'un des styles d'écriture suivants. Tout le monde va bien!

black = (a^bit).sum(axis=0)

ʻA ^ bitressemble à ceci ~ <img width="257" alt="スクリーンショット 2020-05-01 14.10.15.png " src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183481/cd40dd9d-5b1b-898f-6413-4bec36a8506b.png "> Si vous utilisezXOR (opérateur: ^)avec1`, il retournera! !! !! !! !! Dans l'exemple ci-dessus, seule la ligne du haut est retournée! La ligne du bas reste la même! ** Sensationnel! !! !! !! !! !! ** **

Pour compter le nombre de «1» dans chaque colonne, additionnez chaque colonne. L'ajout de chaque colonne peut être ajouté avec ʻaxis = 0`! Pour «axe», Cet article C'était facile à comprendre!

ans = max(ans,np.fmax(R-black,black).sum())

«R-black» ressemble à ceci ~ スクリーンショット 2020-05-01 14.41.21.png En termes d'image, les deux suivants sont les mêmes!

Pour np.fmax, [Ce site] (https://note.nkmk.me/python-numpy-maximum-mimimun-fmax-fmin/) C'était facile à comprendre!

** Conclusion! «Numpy» et «XOR» sont incroyables! !! !! !! !! !! ** **

14 Square869120Contest #4 B - Buildings are Colorful! ** Cela semblait résolu à première vue, mais je ne pouvais pas le résoudre! !! !! Je suis désolé! ** ** Même lorsque bit était égal à 0, je n'ai pas remarqué le motif que la hauteur du bâtiment kijun augmentait ...

Mais si vous pouvez comprendre tous les problèmes de la recherche peu complète jusqu'à présent, l'idée en elle-même n'est pas si difficile!

test.py


def LI(): return list(map(int,input().split()))
N,K = LI()
a = LI()
ans = float('INF')
for i in range(2**(N-1)):
    bit = [i>>j&1 for j in range(N-1)]
    if K-1!=sum(bit):
        continue
    cost,kijun = 0,a[0]
    for k in range(N-1):
        if bit[k]==0:
            kijun = max(kijun,a[k+1])
            continue
        if a[k+1]>=kijun+1:
            kijun = a[k+1]
            continue
        cost += (kijun+1)-a[k+1]
        kijun += 1
    ans = min(ans,cost)
print(ans)

La prochaine fois, je résoudrai les 3 questions suivantes!

Recherche complète: avant la recherche complète

15 AtCoder Beginner Contest 145 C - Average Length 16 AtCoder Beginner Contest 150 C - Count Order 17 ALDS_13_A-8 Le problème de la reine est intéressant.

Part3/22 fin!

Suivant (Partie 4/22)

Recommended Posts

[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Partie 5/22]
[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Partie 7/22]
[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Partie 4/22]
[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part3 / 22]
[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Partie 1/22]
[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Partie 6/22]
Résoudre avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (028 --033 recherche de priorité de largeur)
Résolution avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (053 --055 Méthode de planification dynamique: Autres)
Résoudre avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (024 --027 Recherche de priorité en profondeur)
Résoudre avec Python [100 anciennes questions sélectionnées que les débutants et les intermédiaires devraient résoudre] (015 --017 Recherche complète: Recherche complète en avant)
Résoudre avec Python [100 questions passées sélectionnées que les débutants et les intermédiaires devraient résoudre] (010 --014 Recherche complète: Recherche complète de bits)
Résoudre avec Python [100 questions passées sélectionnées que les débutants et les intermédiaires devraient résoudre] (001 --004 Toutes les recherches: Toutes les énumérations)
Résoudre avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (056 --059 Problème de l'itinéraire le plus court: méthode Dyxtra)
Résoudre avec Python [100 questions que les débutants et les intermédiaires devraient résoudre] (034-038 Méthode de planification dynamique: Knapsack DP basic)
Résolvez avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (039 --045 Méthode de planification dynamique: variante Knapsack DP)
Résoudre avec Python [100 questions passées sélectionnées que les débutants et les intermédiaires devraient résoudre] (005 --- 009 Toutes les recherches: Toutes les énumérations pour réduire le nombre de rues en concevant)
[Pour les professionnels de la compétition débutants] J'ai essayé de résoudre 40 questions AOJ "ITP I" avec python
J'ai essayé de résoudre l'édition du débutant du livre des fourmis avec python
Python que je voudrais recommander aux débutants en programmation
J'ai essayé de résoudre Soma Cube avec python
J'ai essayé de résoudre le problème avec Python Vol.1
J'ai essayé de résoudre la théorie des nombres entiers d'AOJ avec Python
J'ai essayé d'énumérer les différences entre java et python
J'ai essayé de créer une interface graphique à trois yeux côte à côte avec Python et Tkinter
Django super introduction par les débutants Python! Partie 6 J'ai essayé d'implémenter la fonction de connexion
J'ai essayé de résumer les langues que les débutants devraient désormais apprendre par but
Examen mathématique précoce de l'Université Tohoku 2020 (sciences) J'ai essayé de résoudre les grandes questions 1 à 3 avec Python
Django super introduction par les débutants Python! Partie 1 J'ai essayé d'afficher une page HTML qui ne dit que "Hello World"
J'ai essayé de toucher Python (installation)
les débutants en python ont essayé de le découvrir
Je veux résoudre APG4b avec Python (seulement 4.01 et 4.04 au chapitre 4)
[Python] Un mémo que j'ai essayé de démarrer avec asyncio
[Pandas] J'ai essayé d'analyser les données de ventes avec Python [Pour les débutants]
J'ai essayé de faire un processus d'exécution périodique avec Selenium et Python
J'ai essayé de détecter facilement les points de repère du visage avec python et dlib
[Python] J'ai essayé d'expliquer des mots difficiles à comprendre pour les débutants d'une manière facile à comprendre.
J'ai essayé de résumer la gestion des exceptions Python
J'ai essayé d'implémenter PLSA en Python
J'ai essayé d'implémenter la permutation en Python
Django super introduction par les débutants Python! Partie 3 J'ai essayé d'utiliser la fonction d'héritage de fichier de modèle
Comment écrire hors ligne en temps réel J'ai essayé de résoudre E11 avec python
J'ai essayé d'implémenter PLSA dans Python 2
Je voulais résoudre ABC160 avec Python
J'ai essayé d'utiliser PyEZ et JSNAPy. Partie 2: J'ai essayé d'utiliser PyEZ
J'ai essayé d'implémenter ADALINE en Python
J'ai essayé de laisser optuna résoudre le nombre
J'ai essayé de développer un formateur qui génère des journaux Python en JSON
Django super introduction par les débutants Python! Partie 2 J'ai essayé d'utiliser les fonctions pratiques du modèle
J'ai essayé de faire la reconnaissance de caractères manuscrits de Kana Partie 2/3 Création et apprentissage de données
Je voulais résoudre ABC159 avec Python
J'ai essayé d'implémenter PPO en Python
10 erreurs Python communes aux débutants
J'ai essayé de vérifier et d'analyser l'accélération de Python par Cython
J'ai essayé de résoudre la recherche de priorité de profondeur (DFS) d'AtCoder en Python (résultat: TLE ...)
J'ai essayé de résoudre TSP avec QAOA
[Python] J'ai essayé de calculer TF-IDF régulièrement
[Chaîne de Markov] J'ai essayé de lire des citations et des émotions négatives en Python.
J'ai essayé de toucher Python (syntaxe de base)
J'ai créé un exemple pour accéder à Salesforce en utilisant Python et Bottle
Je voulais résoudre ABC172 avec Python