[PYTHON] Code de l'Éducation Forces Round 87
Les résultats de cette fois
Impressions de cette époque
J'ai participé à un concours appelé Edufo, communément appelé Codeforces. J'étais confus car je ne pouvais pas comprendre la différence entre les concours réguliers. Il y avait trois complets jusqu'à A, B, C1. J'ai senti que C2 et D pouvaient être résolus, mais à la fin je n'ai pas pu résoudre non plus.
Quand j'ai vérifié la solution sur Twitter, etc., il semblait que je pouvais le faire en trouvant la méthode que je voulais envisager, alors j'aimerais enquêter sur la cause de la solution.
Problème A
Il était difficile de déchiffrer l'énoncé du problème et il a fallu beaucoup de temps pour le résoudre. Quatre valeurs de $ a, b, c et d $ sont données, mais ce problème peut être résolu correctement en dessinant la figure suivante.
Le temps de sommeil total doit être de $ a $ ou plus, et si vous dormez pendant $ b $ au début, l'alarme retentit, puis l'alarme retentit pendant $ c $, et le $ d $ time va ** essayer de dormir. ** Vous ne pouvez donc dormir que $ cd $ et cela se répétera à l'infini.
Premièrement, lorsque $ b \ geqq a $, cela se produit lorsque $ b $ est passé. Notez que c'est $ b $ au lieu de $ a $.
De plus, lorsque $ c \ leqq d $, vous ne pouvez dormir qu'au premier $ b $, vous devez donc afficher -1 lorsque a> b.
Ce qui précède est mis en œuvre et devient comme suit.
A.py
t=int(input())
for i in range(t):
a,b,c,d=map(int,input().split())
if d>=c:
if b>=a:
print(b)
else:
print(-1)
else:
if b>=a:
print(b)
else:
a-=b
num=-((-a)//(c-d))
print(b+num*c)
Problème B
Renvoie la longueur de la sous-chaîne la plus courte qui contient tous les éléments 1, 2 et 3. Cependant, si une telle sous-chaîne n'existe pas, 0 doit être affiché.
Ce problème peut être résolu en utilisant la ** méthode de mise à l'échelle ** car les sections peuvent être déplacées et comptées ** en continu **, mais l'implémentation est lente après la mise au point de la méthode de mise à l'échelle. J'ai senti que j'étais moi-même amateur.
Dans la mise en œuvre de la méthode de mise à l'échelle, le traitement de la requête doit être effectué dans l'ordre de «** Avancer l'extrémité droite dans l'ordre vers la droite ** → ** Avancer l'extrémité gauche dans l'ordre vers la droite **». Notez également que ** le bord droit ne dépasse pas la plage de la séquence que vous souhaitez examiner ** et ** le bord gauche ne dépasse pas le bord droit **.
B.py
t=int(input())
for i in range(t):
s=input()
le=len(s)
l,r=0,0
d=[0,0,0]
d[int(s[0])-1]=1
ans=0
while True:
#Décision R
while not all(d) and r!=le-1:
r+=1
d[int(s[r])-1]+=1
if r==le-1:
break
#l décision
while l!=le-1:
if all(d):
if ans==0:
ans=r-l+1
else:
ans=min(ans,r-l+1)
d[int(s[l])-1]-=1
l+=1
else:
break
if r==le-1 or l==le-1:
break
print(ans)
Problème C1
Dans le cas d'un nombre pair, vous pouvez encadrer le polygone avec le plus petit carré en organisant les chiffres comme indiqué ci-dessous (je ne peux pas le prouver car je l'ai fait de manière heuristique).
Si vous faites un triangle en reliant le centre du polygone et les sommets du polygone et calculez en utilisant le rapport trigonométrique (sin, cos, tan), $ \ frac {1} {\ tan {\ frac {90} {n}} } $ Vous pouvez demander.
D'ailleurs, en tant qu'idée heuristique, c'est le sommet du polygone qui est le plus éloigné du centre du polygone, et cette forme en est une car il faut considérer ** l'arrangement avec une bonne symétrie **. C'est comme si c'était pratique.
C1.py
import math
t=int(input())
for i in range(t):
n=int(input())
print(1/math.tan(math.radians(90/n)))
Problème C2
Dans le cas d'un nombre impair, j'ai mal compris que le chiffre le plus à gauche était écrit sale et que les côtés supérieur et inférieur touchaient le carré (** dessinez soigneusement le chiffre! **).
Comme précédemment, il n'y a que les trois motifs ci-dessus ** lorsque vous dessinez avec la symétrie à l'esprit, mais les motifs gauche et droit peuvent être considérés comme le même motif ** en tournant le carré. Par conséquent, considérez lequel des motifs les plus à gauche et au milieu a la plus grande surface, qui est clairement le motif du milieu (vous pouvez le déterminer par calcul).
Ce motif du milieu est entre les motifs droit et gauche, et comme il déplace $ \ frac {180} {n} $ de l'extrémité gauche à l'extrémité droite, on pense que $ \ frac {90} {n} $ est déplacé du motif d'extrémité gauche. Par exemple, il est possible d'obtenir $ \ frac {\ cos {\ frac {45} {n}}} {\ sin {\ frac {90} {n}}} $ en effectuant la même considération géométrique que précédemment. Je peux le faire.
C2.py
import math
t=int(input())
for i in range(t):
n=int(input())
print(math.cos(math.radians(45/n))/math.sin(math.radians(90/n)))
Problème D
Je pensais qu'il serait possible de le résoudre en utilisant BIT, mais je n'ai pas pu le résoudre car je ne savais pas qu'il était possible de faire une dichotomie sur BIT. Ce n'est pas difficile si vous pouvez faire une dichotomie.
Tout d'abord, la position à insérer et la position à supprimer sont ** déterminées en fonction du tri **, pensez donc à trier cet ensemble multiple et à opérer tout en conservant ce tri.
Ici, les ** nombres en double ** sont les mêmes même s'ils sont considérés ensemble dans le tri, donc ** un tableau x ** ($ 1 \ leqq $ (élément de x) qui stocke le nombre de chaque nombre) Préparez $ \ leqq n $).
Si vous pensez insérer sous ceci, vous pouvez l'exécuter avec O (1) (car vous n'ajoutez que +1 à l'élément du tableau $ \ parce que $), mais lors de la suppression, décidez que l'élément du tableau est -1 Il est nécessaire d'obtenir le numéro de l'élément, qui est O (n).
Ici, le tableau x ** qui stocke le numéro de chaque numéro est géré par BIT (voir cet article pour BIT). Ensuite, l'insertion sera O ($ \ log {n}
Si vous pouvez abandonner la commande jusqu'à présent, vous pouvez écrire un programme avec O ($ n (\ log {n}) ^ 2
ios::sync_with_stdio(false);
cin.tie(nullptr);
D.cc
//Comprendre(Ordre alphabétique)
#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable
using namespace std;
typedef long long ll;
//macro
//pour la relation de boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//x est un conteneur tel que vector
#define ALL(x) (x).begin(),(x).end() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ((ll)(x).size()) //taille à la taille_Changement de t à ll
#define MAX(x) *max_element(ALL(x)) //Trouvez la valeur maximale
#define MIN(x) *min_element(ALL(x)) //Trouvez la valeur minimale
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie(Utilisé pour l'énumération des nombres premiers, etc.)
//Abréviation
#define PB push_back //Insérer dans le vecteur
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire
//1-indexed
class BIT {
public:
ll n; //Longueur des données
vector<ll> bit; //Emplacement de stockage des données
BIT(ll n):n(n),bit(n+1,0){} //constructeur
//k & -k est LSB
//bit_x à i o(log(n))Ajouter avec
void add(ll i,ll x){
if(i==0) return;
for(ll k=i;k<=n;k+=(k & -k)){
bit[k]+=x;
}
}
//bit_1 + bit_2 + … + bit_n à O(log(n))Une peau
ll sum(ll i){
ll s=0;
if(i==0) return s;
for(ll k=i;k>0;k-=(k & -k)){
s+=bit[k];
}
return s;
}
//a_1 + a_2 + … + a_i >=Trouvez le plus petit i tel que x(a_k >= 0)
//Si x est égal ou inférieur à 0, il n'y a pas d'élément correspondant → 0 est renvoyé
ll lower_bound(ll x){
if(x<=0){
return 0;
}else{
ll i=0;ll r=1;
//Obtenez la longueur de section maximale possible
//Doit être le plus petit carré de n ou moins(La plus grande section d'une colonne numérique gérée par BIT)Cherchant
while(r<n) r=r<<1;
//La longueur de la section est réduite de moitié à chaque fois qu'elle est examinée
for(int len=r;len>0;len=len>>1) {
//Lors de l'adoption de cette section
if(i+len<n && bit[i+len]<x){
x-=bit[i+len];
i+=len;
}
}
return i+1;
}
}
};
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n,q;cin >> n >> q;
BIT a(n);REP(i,n){ll a_sub;cin >> a_sub;a.add(a_sub,1);}
vector<ll> k(q);REP(i,q) cin >> k[i];
REP(i,q){
if(k[i]>0){
a.add(k[i],1);
}else{
//Ce qui est inclus dans la colonne numérique est toujours spécifié
a.add(a.lower_bound(-k[i]),-1);
}
}
vector<ll> answers(n);
REP(i,n){answers[i]=a.sum(i+1);}
if(answers[n-1]<=0){
cout << 0 << endl;return 0;
}
REP(i,n){
if(i>0){
if(answers[i]-answers[i-1]>0){
cout << i+1 << endl;return 0;
}
}else{
if(answers[i]>0){
cout << i+1 << endl;return 0;
}
}
}
}
E problem, F problem, G problem //codeforces.com/contest/1354/problem/G)
Je pense que je manque encore de capacités, alors je vais sauter cette fois.
Recommended Posts