AtCoder Grand Contest 048 Critique

Les résultats de cette fois

スクリーンショット 2020-10-22 10.07.12.png

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.

Recommended Posts

AtCoder Grand Contest 041 Critique
AtCoder Grand Contest 048 Critique
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
AtCoder Grand Contest 046 Critique
Critique du concours AtCoder Beginner Contest 152
Revue du concours régulier AtCoder 105
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
Critique du concours AtCoder Débutant 181
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
Critique du concours AtCoder Débutant 180
Critique du concours AtCoder pour débutant 177
AtCoder Débutant Contest 168 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
AtCoder Regular Contest 106 Évaluation
Critique du concours AtCoder
AtCoder Débutant Contest 175 Critique
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique
AtCoder Débutant Contest 170 Critique
Revue du concours régulier AtCoder 104
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
AtCoder Grand Contest 040 Rapport de participation
AtCoder Grand Contest 047 Rapport de participation
AtCoder Grand Contest Past Question Challenge 2
AtCoder Grand Contest Défi des questions passées 1
AtCoder Beginner Contest 066 Revoir les questions précédentes
Concours AtCoder Débutant 177
concours yukicoder 259 avis
concours yukicoder 264 avis
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
concours yukicoder 261 avis
Concours AtCoder Débutant 173
concours yukicoder 266 avis
Concours Atcoder Débutant 153
concours yukicoder 263 avis
yukicoder contest 268 avis
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes