[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) **

• Supplément Entrez à partir de l'article (** Partie 6 **) dans cette série de 100 questions input()→sys.stdin.readline().rstrip() Je change pour! [Python] Competitive Pro Template [At Coder] J'ai également fait un article pour le modèle, alors veuillez l'utiliser si vous le souhaitez ~

"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')

• Au fait, le temps d'exécution est également plus rapide avec ** DFS ** ~ Cas de test pour n, q = (20,200) Résultat de la mesure avec le code ci-dessus!

• ** Recherche complète de bits **: 6,81 secondes
• ** DFS (Retrospective Ver) **: 0,54 seconde
• ** DFS (Stack Ver) **: 1,03 seconde

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! !! !!

• Article de Kenchon DFS (Depth Priority Search) Super Introduction! ~ Entrée dans le monde des algorithmes graphiques ~ [Partie 1]

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 «^»). ** **

• Numpy Lorsqu'il s'agit de données de tableaux 2D ou plus, le code n'est pas compliqué, donc la logique est facile à comprendre --XOR (opérateur: ^) Ce qui peut être représenté par " 0 ou 1 "semble être compatible lors de l'exécution de l'opération" 0 ⇄ 1" (0 ^ 1 → 1, 1 ^ 1 → 0)

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!

• np.array([[i>>j&1 for j in range(R)]]).T
• np.matrix([i>>j&1 for j in range(R)]).T
• np.array([i>>j&1 for j in range(R)]).reshape(R,-1)
• np.array([[i>>j&1] for j in range(R)])

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 ~ En termes d'image, les deux suivants sont les mêmes!

• 2 - [2 0 1 0 2] = [0 2 1 2 0]
• [2 2 2 2 2] - [2 0 1 0 2] = [0 2 1 2 0]

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)