[PYTHON] AtCoder Grand Contest 048 Bewertung

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Es ist ein Bodensatz, der nur im selbstverständlichen Rahmen schnell gelöst werden kann ... Ich habe lange über das C-Problem nachgedacht, konnte es aber überhaupt nicht lösen.

Ich war auf Twitter, nur weil ich es nicht lösen konnte. Ich habe das Gefühl, dass ich es in Zukunft nicht mehr tun kann, ohne die körperliche Kraft, es ein bisschen mehr in Betracht zu ziehen ...

Problem A

Ich hätte WA vermeiden können, wenn ich mich beruhigt hätte, was enttäuschend ist. Ich denke, es wurde relativ schnell (in Bezug auf die Zeit) gelöst, als ob es in Kodofo gesehen würde.

Erstens, wenn Sie nur $ a $ haben, ist es offensichtlich -1. Wenn die angegebene Zeichenfolge bereits größer als die Zeichenfolge "atcoder" ist, ist sie offensichtlich 0.

Wenn es ein anderes Zeichen als $ a $ gibt, können Sie es jederzeit in lexikalischer Reihenfolge vergrößern, indem Sie dieses Zeichen zuerst einfügen. Wenn $ x $ der Index ist, der ein Zeichen enthält, das zum ersten Mal nicht $ a $ ist und von vorne zählt, beträgt die Mindestanzahl von Swaps, die erforderlich sind, um dieses Zeichen zuerst zu bringen, $ x $. Ich möchte dies beantworten, aber wenn das in ** $ x $ vorhandene Zeichen größer als "t" ist, kann es in lexikalischer Reihenfolge vergrößert werden, indem es auf das zweite Zeichen ** gebracht wird, also einmal Sie können seltener nach Wörterbuch sortieren. Im Gegenteil, wenn es sich nicht um diese beiden Muster handelt, ist es die Zeichenfolge "aa ..." und nicht größer als "atcoder" in lexikalischer Reihenfolge.

A.py

for _ in range(int(input())):
    s=input()
    if all(i=="a" for i in s):
        print(-1)
    else:
        n=len(s)
        if "atcoder"<s:
            print(0)
            continue
        for i in range(n):
            if s[i]!="a":
                if s[i]>"t":
                    print(i-1)
                else:
                    print(i)
                break

B-Problem

Ich habe verschiedene Dinge beschleunigt und den schnellsten Code erhalten → Senden (Ich habe es einfach aufgegeben, meinen Code zu beschleunigen und den Code von yosupo zu beschleunigen Es tut mir leid, yosupo.).

Ich hatte eine kurzgeschlossene Idee, dass es DP-ähnlich, aber unmöglich war, und ich dachte immer über das C-Problem nach. Wenn ich ruhig denke, ist DP unmöglich, also suche ich einfach nach einer anderen Methode. Da es schwierig zu sein scheint, sich bei DP oder ehrlich zu entscheiden, denke ich, dass es eine Art Regel ** gibt, und denke darüber nach. Die typische Lösung für Klammern besteht darin, die kumulative Summe zu verarbeiten. Dies scheint jedoch unmöglich zu sein, da zu viele Muster vorhanden sind.

Wie auch immer, ** Experiment ** wird für das Problem durchgeführt, dass die typische Lösung nicht gilt. Da Klammern nur gültig sind, wenn sowohl geöffnet als auch geschlossen wird, ist es auch gut, ** Gleichmäßigkeit zu berücksichtigen ** (ich berücksichtige diesen Bereich während des Wettbewerbs nicht, ich werde später auf TL eingehen Mir ist aufgefallen ...).

Darüber hinaus sollte beachtet werden, dass (und) und [und] frei ausgewählt werden können, wenn ein Index ausgewählt wird, der zu $ A, B $ wird. Daher wird die Positionsbeziehung der Indizes als wichtig angesehen. Wenn dann sowohl der Index, der zu $ A $ wird, als auch der Index, der zu $ B $ ** wird, die gleiche Anzahl von geraden und ungeraden Indizes haben, sollten **, () und [] gut angeordnet sein. Sie können eine Klammerzeichenfolge erstellen, die erfüllt (Beweis ist [maspys Artikel]) (https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6 % 83% B3-2020-10-19agc048 # toc3)).

Da das oben Gesagte in der Logik ziemlich vage ist (✳︎1), ist es meiner Meinung nach besser, auf die Lösung von editorial zu verweisen, um genau zu sein. Da es so kopiert wird, wie es ist, wird es hier weggelassen.

Auch die Methode zur Auswahl des ** Indexsatzes $ x \ _1, x \ _2,…, x \ _k $, wobei [] im Editor platziert wird und die Bedingungen ** berücksichtigt, ist sehr abstrakt. Ich denke, es ist eine allgemeine Idee. Während des Wettbewerbs wurde diese ** Überlegung im Indexsatz ** komplett weggelassen, daher bedauere ich es (✳︎2).

(✳︎1)… ** Überlegungen durch Experimente oder Überlegungen durch Abstraktionen ** werden oft weggelassen, daher möchte ich sie kompatibel machen.

(✳︎2)… Wenn Sie in guter Verfassung sind, können Sie eine solche Abstraktion vornehmen, daher hielt ich es für notwendig, die Überlegung zu stabilisieren. Zunächst einmal ist es wirklich ein Rätsel, dass ich bei diesem Problem nicht auf die ** Annahme einer Reihe von Indizes ** kommen konnte.

B.py

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
s=sum(a)
e,o=[b[i]-a[i] for i in range(n) if i%2==0],[b[i]-a[i] for i in range(n) if i%2==1]
e.sort(reverse=True)
o.sort(reverse=True)
for i in range(n//2):
    if e[i]+o[i]>0:
        s+=e[i]+o[i]
    else:
        break
print(s)

C-Problem

Wie Sie dem Kommentar anderer Leute entnehmen können, scheint es, dass Sie dies mit der Skalierungsmethode tun können, aber ich konnte mir keine gute Implementierung vorstellen. Ich werde eines Tages zurückkommen, um es zu lösen.

Nach C Problem

Ich werde diesmal überspringen.