[PYTHON] AtCoder Anfängerwettbewerb 174 Bewertung

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Ich habe den Fehler gemacht, dass ich das C-Problem nicht lösen konnte. Das Thema konnte nicht genau gelesen werden. ** Wenn Sie ein Problem haben, überprüfen Sie die Bewegung mit einer Probe **.

Es scheint, dass viele Menschen das F-Problem untersucht und gelöst haben. Ich denke, es ist ein interessantes Problem, aber ich wusste, wie man es löst, also werde ich versuchen, es zu lösen, wenn ich es vergesse. Es gibt einige Probleme, die es leicht machen, eines in diesem Abschnitt zu finden, aber es ist leicht zu vergessen, deshalb möchte ich sicherstellen, dass ich es beim nächsten Mal lösen kann.

Problem A

Sie müssen nur überprüfen, ob es über 30 Grad ist.

A.py

print("Yes" if int(input())>=30 else "No")

B-Problem

Finde einfach die Entfernung. Auch diesmal mache ich mir Sorgen, dass die Route ein Bruchteil sein wird, also habe ich sie quadriert (es scheint in Ordnung zu sein, die Route so zu berechnen, wie sie in diesem Problem ist).

B.py

n,d=map(int,input().split())
ans=0
for i in range(n):
    x,y=map(int,input().split())
    ans+=(x**2+y**2<=d**2)
print(ans)

C-Problem

Ein Vielfaches von ** $ K $ kann als 0 ** umformuliert werden, wobei der Rest durch $ K $ geteilt wird. Wenn das $ i $ th von $ 7,77,777,… $ $ a_i $ ist, dann ist $ a_ {i + 1} = 10 \ mal a_i + 7 $. Wenn daher die Reste von $ a_j und a_l $ gleich sind, sind auch die Reste von $ a_ {j + 1} und a_ {l + 1} $ gleich. Daher gibt es etwas, das unter dem Rest geteilt durch ** $ K $ bis zu $ a_ {K + 1} $ ** leidet. Wenn Sie also nach $ a_1 $ ~ $ a_k $ suchen, wird der Rest geteilt durch $ K $ sein Sie können nach Nullen suchen. Wenn andererseits 0 bis zu diesem Punkt nicht herauskommt, gibt es nichts, was der Rest nach dem Teilen durch $ K $ zu 0 wird.

In diesem Problem können Sie das Problem lösen, indem Sie auf den Rest von ** $ K $ achten, wenn Sie feststellen, dass der Rest von ** $ K $ geteilt durch $ K $ 0 ** ist. Da es in den Grundlagen des ** Simulationsversuchs bei der Lösung eines Problems ** enthalten ist, wurde mir erneut klar, wie wichtig es ist, die Grundlagen gründlich umzusetzen.

C.py

k=int(input())
now=7%k
if now==0:
    print(1)
    exit()
for i in range(1,k):
    now=10*now+7
    now%=k
    if now==0:
        print(i+1)
        break
else:
    print(-1)

D Problem

Es ist leicht zu erkennen, dass die endgültige Sequenz "rot-rot ... rot-rot / weiß-weiß ... weiß-weiß" ist. Um die angegebene Steinreihe ** gierig zu ändern **, ändern wir sie zunächst von links nach rot.

Zu diesem Zeitpunkt ist es nicht erforderlich, Akaishi zu ändern. Berücksichtigen Sie daher ** nur für Shiraishi **. Zu diesem Zeitpunkt denke ich darüber nach, den weißen Stein in einen roten Stein umzuwandeln. Wenn Sie ihn jedoch durch den roten Stein auf der rechten Seite des Steins ersetzen, anstatt den Stein neu zu färben, können Sie die Farbe von zwei Steinen gleichzeitig ändern **, sodass dies effizient ist. ist. Außerdem können Sie sehen, dass ** durch den am weitesten rechts stehenden roten Stein ersetzen ** geeignet ist, durch roten Stein zu ersetzen, damit die Anzahl der Ersetzungen verringert wird (← Zum Beispiel ** Extremfall ** (neben). Ich denke, es ist leicht zu verstehen, wenn man bedenkt, dass es ineffizient ist (wenn es durch Akaishi ersetzt wird). Wenn Sie eine Situation erstellen können, in der sich auf der rechten Seite kein roter Stein befindet, während Sie dies wiederholen, ist die Anzahl der Operationen zu diesem Zeitpunkt die Mindestanzahl der Operationen.

D.py

from collections import deque
n=int(input())
c=input()
r=deque()
lr=0
for i in range(n):
    if c[i]=="R":
        lr+=1
        r.append(i)
ans=0
for i in range(n):
    if lr==0:
        break
    if c[i]=="W":
        if i<r[-1]:
            ans+=1
            r.pop()
            lr-=1
        else:
            break

print(ans)

E Problem

Wenn Sie die Häufigkeit kombinieren, mit der Sie ein Protokoll schneiden (die Anzahl der Male), das Minimum (der Zahlenbereich ist groß) und ** je länger das Protokoll ist, desto weniger oft schneiden Sie ** (Monotonie), können Sie sich eine Dichotomie vorstellen.

Hier ** in der Dichotomie ist es notwendig, die Bedingung zu berücksichtigen, die immer für das Minimum (oder Maximum) oder mehr gilt **, aber hier "zumindest notwendig, um die längste Länge (Aufrundung) kleiner als $ x $ zu machen". Die Bedingung ist, dass die Häufigkeit, mit der ein Protokoll geschnitten wird, $ K $ oder weniger beträgt und die Summe der für jedes Protokoll berechneten "Ceil (a [i] / x) -1" $ K $ oder weniger beträgt. Falls es gut ist.

Beachten Sie auch, dass für l, r ** $ l $ immer auf einen Wert gesetzt ist, der nicht immer gilt **, ** $ r $ wird auf einen Wert gesetzt, der nicht immer gilt **.

Wenn Sie diese beachten, können Sie die richtige Antwort erhalten, indem Sie sie gemäß [diesem Artikel] implementieren (https://qiita.com/DaikiSuyama/items/84df26daad11cf7da453).

E.py

n,k=map(int,input().split())
a=list(map(int,input().split()))
def f(x):
    global a,n,k
    if x==0:
        return 10**10
    ret=0
    for i in range(n):
        ret+=(-((-a[i])//x)-1)
    return ret

l,r=0,10**10
while l+1<r:
    x=l+(r-l)//2
    if f(x)<=k:
        r=x
    else:
        l=x

print(r)

F Problem

Ich werde diesmal nicht lösen.