[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]

** 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 5" -Dichotomie-

Nous allons résoudre les 6 questions suivantes!

Recherche de bisection

18 ALDS_4_B --Dichotomie C'est un problème de base. Vous pouvez également le résoudre avec une carte, mais essayez de le résoudre avec une dichotomie. 19 JOI 2009 Finale 2 - Pizza 20 Concours AtCoder Débutant 077 C - Festival Snuke Intéressant. 21 Concours pour débutants AtCoder 023 D - Le roi du tir est bon sur le plan éducatif. 22 AtCoder Regular Contest 054 B - La loi de Moore Elle peut être résolue en différenciant et en dichotomisant. Puisque l'histoire est liée à la recherche de trois minutes, je pense qu'il est bon de vérifier cela également. 23 JOI 2008 Final 3 - Fléchettes C'est un problème que vous pouvez concevoir et rechercher en deux.

Connaissance préalable de la dichotomie

・ J'écrirai un article basé sur les deux points suivants! ** ① À propos de la dichotomie ** Tout d'abord, l'article de Kencho Généralisation de l'algorithme de dichotomie-Recommandation de la méthode de dichotomie- Lisez à propos de la dichotomie ** Comprenez l'atmosphère! ** **

** ② Après cela, comment implémenter la dichotomie Python ** Comme Le site suivant était facile à comprendre, donc ce site AtCoder Incontournable pour les personnes grises, brunes et vertes! Comment écrire une dichotomie sans la rendre boguée ** Soigneusement ** Lisez à propos de la dichotomie ** Comprenez bien! ** **

18 ALDS_4_B --Dichotomie

Si vous prenez le «len» de l'ensemble de produits de chaque «ensemble» (ensemble), ce sera un coup, Je ferai de mon mieux pour mettre en œuvre cela en dichotomisant. C'était la première fois que je mettais en place une dichotomie, Quand je l'ai implémenté selon le site ci-dessus ** C'était étonnamment facile à mettre en œuvre! ** **

test.py

def I(): return int(input())
def LI(): return list(map(int,input().split()))
n = I()
S = LI()
q = I()
T = LI()
ans = 0
def birarysearch(x):
    ok,ng = -1,n
    def is_ok(i):
        return S[i]<=x
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return S[max(ok,0)]==x
for x in T:
    if birarysearch(x):
        ans += 1
print(ans)

Le plus grand indice de ʻokest la réponse! Cependant, soyez prudent lorsque l'indice devient négatif, et réglez-le surmax (ok, 0)`!

Une autre solution
Si vous pouvez utiliser la bibliothèque bisect, utilisons-la! ** Incroyablement facile à mettre en œuvre! !! !! ** **

** Avec l'index ʻokdans le code ci-dessus, L'index debisect.bisect (S, x) -1` dans le code ci-dessous est le même! ** **

test.py

import bisect
def I(): return int(input())
def LI(): return list(map(int,input().split()))
n = I()
S = LI()
q = I()
T = LI()
ans = 0
for x in T:
    ok = bisect.bisect(S,x)-1
    if S[max(ok,0)]==x:
        ans += 1
print(ans)

• Bisect.bisect_right et bisect.bisect sont exactement les mêmes! !!
• Il y a aussi bisect.bisect_left, mais l'image de base est que seul bisect.bisect est utilisé!

Quoi qu'il en soit

• ** ʻok` (version sans bibliothèque) **
• ** bisect.bisect (A, x) -1 (version avec bibliothèque) **

** Ces deux index sont des plaques de fer dans la dichotomie! !! !! ** **

19 Finales JOI 2009 2-Pizza

C'était aussi ** étonnamment facile à mettre en œuvre! ** ** Vous pouvez livrer la pizza à partir de l'index de «ok» ou de l'index à sa droite, selon celui qui est le plus proche.

test.py

def I(): return int(input())
d = I()
n = I()
m = I()
dn = [0]+sorted([I() for _ in range(n-1)])+[d]
mn = sorted([I() for _ in range(m)])
ans = 0
def binarysearch(x):
    ok,ng = -1,len(dn)
    def is_ok(i):
        return dn[i]<=x
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return min(x-dn[ok],dn[ok+1]-x)
for x in mn:
    ans += binarysearch(x)
print(ans)

• Au fait Au moment de la saisie, «dn» incluait également les informations du siège social »[0]« et »[d]«! !! !! J'avais l'habitude de le faire sans le savoir, Comment ajouter [0] ou [d] ← ** Il semble qu'il ait un nom appelé "Banheiho **" ~ Il est sorti quand j'ai cherché quelque chose sur Google. Comme pour la ** méthode gourmande **, il peut y avoir d'autres façons de penser aux programmes que vous apprenez sans le savoir sans connaître votre nom!

Une autre solution
Si vous pouvez utiliser la bibliothèque bisect, utilisons-la aussi! ** Facile à mettre en œuvre! !! !! ** **

test.py

import bisect
def I(): return int(input())
d = I()
n = I()
m = I()
dn = [0]+sorted([I() for _ in range(n-1)])+[d]
mn = sorted([I() for _ in range(m)])
ans = 0
for x in mn:
    ok = bisect.bisect(dn,x)-1
    ans += min(x-dn[ok],dn[ok+1]-x)
print(ans)

20　AtCoder Beginner Contest 077 C - Snuke Festival Difficulty:1096 ** Je n'ai pas pu le résoudre à première vue! !! !! ** **

bisect.bisect_left apparaît ... Il n'y avait aucune idée ** basée sur ** B, pas A ou C ... Comme vous pouvez le voir dans l'explication, le problème est devenu ...! **J'ai beaucoup appris! !! !! ** **

test.py

import bisect
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
A = sorted(LI())
B = sorted(LI())
C = sorted(LI())
ans = 0
for b in B:
    ok_a = bisect.bisect_left(A,b)
    ok_c = bisect.bisect_right(C,b)
    ans += ok_a*(N-ok_c)
print(ans)

21 AtCoder Beginner Contest 023 D --Sooting King

** Difficulté: 1804! !! !! Problème bleu! !! !! Je n'ai pas pu résoudre ça à première vue! !! !! ** **

Regardez le code de ceux qui peuvent commenter, je vois! Mais pouvez-vous le résoudre lorsqu'un problème similaire se reproduit? Si vous dites cela, je ne connais toujours pas l'image qui peut être résolue ... ** Pratique insuffisante pour des problèmes extrêmement difficiles! !! !! ** **

test.py

import numpy as np
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
HS = np.array([LI() for _ in range(N)])
H = HS[:,0]
S = HS[:,1]
rangeN = np.arange(N)
ok,ng = 10**9+10**9*10**9+1,0
def is_ok(i):
    T = (i-H)//S
    T.sort()
    return (T>=rangeN).all()
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid
print(ok)

• Une des faiblesses de la bibliothèque bisect est qu'elle ne peut être utilisée que si elle est un tableau. h = [i for i in range(10**9+10**9*10**9+1)] Si vous écrivez quelque chose comme ça, ce sera 200 millions de% TLE, donc vous ne pouvez pas utiliser la bibliothèque bisect à de tels moments! Par conséquent, il y a certains modèles que la bibliothèque bisect ne peut pas être utilisée, donc ** Vous devez être capable de mettre en œuvre vous-même la dichotomie! ** **

22 Concours régulier AtCoder 054 B - Loi de Moore

Difficulty:1268 ** Je n'ai pas pu résoudre cela à première vue! !! !! ** **

Ce n'est pas une «dichotomie» ** «Il semble que cela puisse être résolu par la trisection» **! Ce n'est pas une augmentation monotone ou une diminution monotone, il semble donc que vous ne pouvez pas faire de dichotomie! Je l'ai implémenté en googlé de différentes manières, mais je ne peux que saisir l'atmosphère

Je suis tombé sur ce problème lors de la formulation de la première formule ... ** Cela devrait probablement être possible avec beaucoup de pratique sur des problèmes difficiles! !! !! ** ** Si vous y réfléchissez concrètement, 0 ans, 1 an, 2 ans ..., vous pouvez faire une formule!

• x+P*2**(-x/1.5)

test.py

def F(): return float(input())
P = F()
high,low = P,0
def f(x):
    return x+P*2**(-x/1.5)
def is_high(i,j):
    return f(i)>=f(j)
while high-low>1*(10**-12):
    mid_right = (high*2+low)/3
    mid_left = (high+low*2)/3
    if is_high(mid_right,mid_left):
        high = mid_right
    else:
        low = mid_left
print(f(high))

Une autre solution
Je me sens un peu méchant, mais pas de w La réponse peut être obtenue en remplaçant la valeur de x par une différenciation unique = 0 en «x + P * 2 ** (-x / 1,5)». La valeur de x du 1er différentiel = 0 est [Ce site] (https://ja.wolframalpha.com/input/?i=%28x%2BP*%282**%28-x%2F1.5%29%29%29%27%3D+0) Utilisons!

Par conséquent, x≈-2.16404 log(2.16404/P) Parce qu'il sort Après cela, il suffit de mettre x dans x + P * 2 ** (-x / 1.5)!

test.py

import math
def F(): return float(input())
P = F()
x = -2.16404*math.log(2.16404/P)
def f(x):
    return x+P*(2**(-x/1.5))
print(f(x) if x>0 else f(0))

** J'ai fait AC! ** ** Au fait Comme prémisse, x> = 0 (je ne peux pas retourner dans le passé!) Vous remarquerez la nécessité de classer les cas lors du débogage de l'exemple d'entrée / sortie 2!

23 JOI 2008 Final 3 - Fléchettes

** Bien sûr, je n'ai pas pu le résoudre à première vue! !! !! ** ** Ou plutôt, je ne sais pas où utiliser la dichotomie. Bien sûr, il est impossible de faire un quadruple pour une phrase ou une recherche de bits complète, alors pensez-y en deux ou deux! Si N <= 1000, la quantité de calcul 10 ^ 6 peut être augmentée à double pour instruction, donc je me demande si ce nombre 1000 était un indice ...

Cet article Version AtCoder! Arimoto (Débutant) Résolution de fléchettes avec python J'ai pu l'implémenter en toute sécurité en référence à **! ** **

test.py

import bisect,itertools
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N,M = LI()
P = [I() for _ in range(N)]
ans = 0
set_two_darts = set()
for x,y in itertools.product(P+[0],repeat=2):
    set_two_darts.add(x+y)
list_two_darts = sorted(set_two_darts)
ok_two_darts = bisect.bisect(list_two_darts,M)-1
if list_two_darts[ok_two_darts]<=M:
    ans = max(ans,list_two_darts[ok_two_darts])
for z in list_two_darts:
    remaining_point = M-z
    if remaining_point<=0:
        continue
    ok = bisect.bisect(list_two_darts,remaining_point)-1
    ans = max(ans,z+list_two_darts[ok])
print(ans)

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

Recherche de priorité de profondeur

24 ALDS_11_B --Recherche de priorité en profondeur Il s'agit d'un problème de base. 25 AOJ 1160-Combien d'îles y a-t-il? Le nombre de composants connectés dans le graphique peut être calculé par recherche de priorité de profondeur. 26 Concours AtCoder Débutant 138 D --Ki De nombreux problèmes d'arborescence utilisent la recherche de priorité en profondeur. 27 JOI 2009 Qualification 4-Traversée de glace mince La recherche de priorité de profondeur est un problème qui nous dit qu'il ne s'agit pas simplement d'une structure arborescente. Il peut être résolu à l'aide d'une fonction récursive.

Part5/22 fin!

Suivant (Partie 6/22)