** Streben Sie einen hellblauen Codierer an! !! !! !! !! !! ** **.

Damit [Richtlinien zur Verbesserung von AtCoder, einem von Red Coder gelehrten Wettbewerbsprofi [Zwischenausgabe: Ziel für hellblauen 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 hat 100 gute pädagogische Fragen gesammelt, die für braune und grüne Codierer geeignet sind, um mit einer kleinen Anzahl von Fragen einen hellblauen Codierer oder eine Bewertung von 1200 zu erzielen.

"100 frühere Fragen, die Anfänger und Fortgeschrittene lösen sollten" in diesem Artikel Wird mit ** Python ** gelöst! Vielen Dank an @ e869120! !! !! !! !! !!

Link zum letzten Artikel

** Alle durchsuchen: Alle auflisten ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Teil 1/22] ** Vollständige Suche: Alle Aufzählungen zur Reduzierung der Anzahl der Straßen durch Ausarbeitung ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part2 / 22] ** Vollständige Suche: Bit vollständige Suche ** [[Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Teil3 / 22]] (https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f) ** Vollständige Suche: Vollständige Suche weiterleiten ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part4 / 22] ** Halbierungssuche ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part5 / 22] ** Suche nach Tiefenpriorität ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part6 / 22] ** Suche nach Breitenpriorität ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part7 / 22]

** (Hinzugefügt am 2020/05/07) **

Ergänzung Geben Sie aus dem Artikel (** Teil 6 **) in dieser Serie mit 100 Fragen ein input()→sys.stdin.readline().rstrip() Ich wechsle zu! [Python] Competitive Pro-Vorlage [At Coder] Ich habe auch einen Artikel für die Vorlage erstellt. Bitte verwenden Sie ihn, wenn Sie ~ mögen

"Teil 3" ~ Bit vollständige Suche ~

Wir werden die folgenden 5 Fragen lösen!

Vollständige Suche: Bit vollständige Suche

10 ALDS_5_A - Ein Round-Robin-Grundproblem. 11　AtCoder Beginner Contest 128 C - Switches 12 AtCoder Anfängerwettbewerb 002 D - Fraktion 13 JOI 2008 Qualifying 5-Osenbei Es ist ein wenig schwierig für den braunen Codierer, aber es wird empfohlen, es zu lösen. 14 Square869120Contest # 4 B - Gebäude sind bunt! Es ist ein schwieriges Problem, das nicht einfach zu lösen ist, aber wenn Sie es lösen, werden Sie definitiv an Stärke gewinnen.

10 ALDS_5_A - Runde

** Wir haben unabhängig die stärkste Vorlage für die vollständige Suche entwickelt! bit = [i>>j&1 for j in range(N)]** Mit dieser Vorlage Egal, was für eine vollständige Suche kommt ** Ich habe vor nichts mehr Angst **

`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)] #Stärkste Vorlage
    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')

** (Hinzugefügt am 2020/05/04) **
Eine andere Lösung
Sie können es auch mit ** DFS ** lösen! Es ist, als würde man bis zum Ende suchen, um die nächste Ziffer hinzuzufügen oder nicht! ** Index und Summe setzen **, der Punkt ist, im Stapel zu speichern! !! !!

** ◆ Rekursive 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()
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 = [] #Index und Summe setzen
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')

Übrigens ist die Ausführungszeit mit ** DFS ** ~ auch schneller Testfall für "n, q = (20.200)" Messergebnis mit dem obigen Code!

** Bit vollständige Suche **: 6,81 Sekunden
** DFS (Retrospective Ver) **: 0,54 Sekunden
** DFS (Stack Ver) **: 1,03 Sekunden

11　AtCoder Beginner Contest 128 C - Switches Difficulty:807 ** Die stärkste Vorlage für die Vollbit-Suche ist ein großer Erfolg! ** **. Die Problemstellung ist etwas kompliziert, aber ich werde mein Bestes tun, um sie zu verstehen, während ich mir die Eingabe- / Ausgabebeispiele ansehe. Da es maximal 10 Schalter gibt, können Sie anscheinend alle Bits durchsuchen (in Bezug auf die Berechnung)! Wenn Sie eine Richtlinie erstellen können, können Sie dieses Problem lösen! !! !! ** Ich habe vor nichts mehr Angst **

`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-Anfängerwettbewerb 002 D - Fraktion

** Schwierigkeit: 1405! !! !! Endlich das Problem der hellblauen Ebene! !! !! ** **. ** Ich konnte es auf den ersten Blick nicht lösen! ** **. Zusätzlich zur Vollbit-Suche ist es möglicherweise einfacher zu lösen, wenn Sie Kenntnisse über ** Diagramme haben. ** **. Die Idee von Graphen hängt auch mit DFS und BFS zusammen, also möchte ich sie beherrschen! !! !!

Kenchons Artikel DFS (Depth Priority Search) Super Einführung! ~ Einstieg in die Welt der Graphalgorithmen ~ [Teil 1]

Denken Sie wie folgt!

Stellen Sie menschliche Beziehungen mit einem ungerichteten Graphen dar.
Befindet sich jedes Mitglied des Landtages in einer Fraktion in einer etwas vollständigen Suche? Denken Sie über alle Möglichkeiten nach, die nicht enthalten sind. Für jeden von 3.2 Kandidaten für Antworten, wenn jeder eine menschliche Beziehung zueinander hat!

`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)

Eine detaillierte Ergänzung zum 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)

Vorheriger Artikel zur Verwendung von "itertools.product" und "for / else" [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part2 / 22] Da es in kurz erklärt wird, beziehen Sie sich bitte auch darauf ...

Auch das Bild der if-Anweisung ist ein früherer Artikel [Python] ABC133B (Problem mit dem oberen rechten Dreieck) [At Coder] Ein Bild der Berechnung aller "oberen rechten Dreiecke" und "unteren linken Dreiecke" in der Tabelle, die in diesem Artikel erscheint! !! !! Wenn Sie ein Bild dieser Tabelle haben, können Sie es wahrscheinlich sogar codieren!

13 JOI 2008 Qualifying 5-Osenbei

** Ich konnte es auf den ersten Blick nicht lösen! !! Es kann einfacher zu lösen sein, wenn Sie Kenntnisse über Numpy und XOR (exklusive logische Summe^) haben. ** **.

Numpy Beim Umgang mit Daten von 2D-Arrays oder mehr ist der Code nicht kompliziert, sodass die Logik leicht zu verstehen ist --XOR (Operator: ^) Was durch "0 oder 1" dargestellt werden kann, scheint kompatibel zu sein, wenn die Operation "0 ⇄ 1" ("0 ^ 1 → 1, 1 ^ 1 → 0") ausgeführt wird.

Ich dachte, als ich den AC-Code von erstaunlichen Menschen sah.

Denken Sie wie folgt!

Untersuchen Sie alle Muster zum Umdrehen / Nicht umdrehen aller Zeilen 2.1 Zählen Sie die Anzahl von "1" in jeder Spalte für jedes Muster "(= schwarz)" In 3.2 können wir "0" -Nummer =>, dh "R-Schwarz", versenden. Da kann die Leitung aber auch umgedreht werden Das größere von "R-Schwarz" und "Schwarz"! Der Antwortkandidat ist die Summe aller Ergebnisse in jeder Spalte!

Die Anzahl der "1" in jeder Spalte kann durch Hinzufügen jeder Spalte beantwortet werden. (Das Hinzufügen jeder Spalte ist der 18. von "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)

Es war ein unerwartet kurzer Code!

Eine detaillierte Ergänzung zum Code

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

T ist eine Translokation, [Diese Seite] (https://deepage.net/features/numpy-transpose.html) Daher ist es nur dann wirksam, wenn das Ziel der Translokation zwei oder mehr Dimensionen sind! Das Ziel der Translokation ist eindimensional np.array([i>>j&1 for j in range(R)]).T Dann nein.

Verwenden Sie einen der folgenden Schreibstile. Jedem geht es gut!

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 ^ bit sieht so aus ~ スクリーンショット 2020-05-01 14.10.15.png Wenn Sie "XOR (operator: ^)" mit "1" verwenden, wird es umgedreht! !! !! !! !! Im obigen Beispiel wird nur die oberste Zeile umgedreht! Das Endergebnis bleibt das gleiche! ** Beeindruckend! !! !! !! !! !! ** **.

Addieren Sie jede Spalte, um die Anzahl von "1" in jeder Spalte zu zählen. Das Hinzufügen jeder Spalte kann mit axis = 0 hinzugefügt werden! Für "Achse", Dieser Artikel War leicht zu verstehen!

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

R-black sieht so aus ~ スクリーンショット 2020-05-01 14.41.21.png In Bezug auf das Bild sind die folgenden zwei gleich!

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]

Für np.fmax, [Diese Seite] (https://note.nkmk.me/python-numpy-maximum-mimimun-fmax-fmin/) War leicht zu verstehen!

** Fazit! Numpy und XOR sind unglaublich! !! !! !! !! !! ** **.

14　Square869120Contest #4 B - Buildings are Colorful! ** Es schien auf den ersten Blick gelöst zu sein, aber ich konnte es nicht lösen! !! !! Es tut mir Leid! ** **. Selbst als "Bit" 0 war, bemerkte ich nicht das Muster, dass die Höhe des Gebäudes "Kijun" zunahm ...

Aber wenn Sie alle Probleme der Bit-Full-Suche bisher verstehen können, ist die Idee selbst nicht so schwierig!

`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)

Nächstes Mal werde ich die folgenden 3 Fragen lösen!

Vollständige Suche: Vollständige Suche weiterleiten

15　AtCoder Beginner Contest 145 C - Average Length 16　AtCoder Beginner Contest 150 C - Count Order 17 ALDS_13_A-8 Queen Problem ist interessant.

Part3/22 Ende!

Weiter (Teil 4/22)

[Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Teil 3/22].

Link zum letzten Artikel

"Teil 3" ~ Bit vollständige Suche ~

Vollständige Suche: Bit vollständige Suche

10 ALDS_5_A - Runde

test.py

test.py

test.py

test.py

12 AtCoder-Anfängerwettbewerb 002 D - Fraktion

test.py

13 JOI 2008 Qualifying 5-Osenbei

test.py

test.py

Vollständige Suche: Vollständige Suche weiterleiten

`test.py`

`test.py`

`test.py`

`test.py`

`test.py`

`test.py`

`test.py`