[PYTHON] AtCoder Grand Contest 048 Critique

Les résultats de cette fois

Impressions de cette époque

C'est une lie qui ne peut être résolue rapidement que dans le cadre qui va de soi ... Je pensais au problème C depuis longtemps, mais je ne pouvais pas du tout le résoudre.

J'étais sur Twitter simplement parce que je ne pouvais pas le résoudre. Je sens que je ne peux pas le faire à l'avenir sans la force physique pour y réfléchir un peu plus ...

Problème A

J'aurais pu éviter WA si je me calmais, ce qui est décevant. Je pense que cela a été résolu relativement rapidement (en termes de temps) comme si vous pouviez le voir dans Kodofo.

Premièrement, si vous n'avez que $ a $, c'est évidemment -1. De même, si la chaîne donnée est déjà plus grande que la chaîne "atcoder", elle vaut évidemment 0.

De plus, s'il y a un caractère autre que $ a $, vous pouvez toujours l'agrandir dans l'ordre lexical en amenant ce caractère en premier. Ici, si $ x $ est l'index qui a un caractère qui n'est pas $ a $ pour la première fois en partant du front, le nombre minimum de swaps requis pour amener ce caractère en premier est $ x $. Je voudrais répondre à ceci, mais si le caractère existant dans ** $ x $ est plus grand que "t", il peut être agrandi dans l'ordre lexical en l'amenant au deuxième caractère **, donc une fois Vous pouvez trier moins souvent par dictionnaire. Au contraire, s'il est différent de ces deux motifs, ce sera la chaîne de caractères "aa ..." et ne sera pas plus grand que "atcoder" dans l'ordre lexical.

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

Problème B

J'ai accéléré diverses choses et j'ai obtenu le code le plus rapide → Soumettre (J'ai juste renoncé à accélérer mon code et j'ai accéléré le code de yosupo Je suis désolé yosupo.).

J'avais une idée court-circuitée que c'était comme DP mais impossible, et je pensais toujours au problème C. Penser calmement, DP est impossible, alors je cherche juste une autre méthode. Puisqu'il semble difficile de décider par DP ou honnêtement, je pense qu'il y a une sorte de règle ** et je la considère. De plus, la solution typique pour les parenthèses est de gérer la somme cumulée, mais cela semble impossible car il y a trop de modèles.

Quoi qu'il en soit, ** expérimentez ** pour les problèmes qui ne s'appliquent pas à une solution aussi typique. De plus, comme les parenthèses ne sont valables que s'il y a à la fois une ouverture et une fermeture, il est bon de ** considérer la régularité ** (je ne considère pas cette zone pendant le concours, je regarderai TL plus tard J'ai remarqué ...).

De plus, il convient de noter que (et) et [et] peuvent être librement sélectionnés lors de la sélection d'un index qui devient $ A, B $. Par conséquent, la relation de position des index est considérée comme importante. Ensuite, si l'index qui devient $ A $ et l'index qui devient $ B $ ** ont le même nombre d'index pairs et d'index impairs, **, () et [] doivent être bien arrangés. Vous pouvez créer une chaîne de parenthèses satisfaisant (la preuve est [l'article maspy](https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6] % 83% B3-2020-10-19agc048 # toc3)).

De plus, comme ce qui précède est assez vague en logique (✳︎1), je pense qu'il vaut mieux se référer à la solution de éditorial pour être exact. Puisqu'il sera copié tel quel, il sera omis ici.

De plus, la méthode de sélection de l'ensemble d'index $ x \ _1, x \ _2,…, x \ _k $ où [] est placé dans l'éditeur et considérant les conditions ** est très abstraite. Je pense que c'est une idée générale. Pendant le concours, cette ** considération dans l'ensemble d'indices ** a été complètement omise, donc je le regrette (✳︎2).

(✳︎1)… ** La considération par expérience ou la considération par abstraction ** est souvent omise, je voudrais donc la rendre compatible.

(✳︎2)… Si vous êtes en forme, vous pouvez faire une telle abstraction, alors j'ai senti qu'il fallait stabiliser la considération. Tout d'abord, c'est vraiment un mystère que je n'ai pas pu trouver l'idée de ** faire l'hypothèse d'un ensemble d'index ** dans ce problème.

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)

Problème C

Comme vous pouvez le voir dans les commentaires d'autres personnes, il semble que vous puissiez le faire avec la méthode de l'échelle, mais je ne pouvais pas penser à une bonne implémentation. Je reviendrai pour le résoudre un jour.

Problème après C

Je vais sauter cette fois.