[PYTHON] Critique du concours AtCoder
Les résultats de cette fois
Impressions de cette époque
Cette fois, ce fut également un résultat décevant. Je n'ai pas eu le temps de résoudre le problème F parce que j'avais tout le temps mis sur écoute le problème D. Si le problème F a un BIT (ou un arbre Seg), ce n'est pas si difficile, donc je pense que je l'ai résolu en environ 15 minutes.
Problème A
J'ai écrit les conditions de jugement à l'envers et j'ai passé du temps.
A.py
s=input()
if s[-1]!="s":
print(s+"s")
else:
print(s+"es")
Problème B
Vous devez simplement juger docilement s'ils sont égaux ou non. Faites attention uniquement aux références hors séquence.
B.py
n=int(input())
x,y=[],[]
for i in range(n):
x_,y_=map(int,input().split())
x.append(x_)
y.append(y_)
for i in range(n-2):
if x[i]==y[i] and x[i+1]==y[i+1] and x[i+2]==y[i+2]:
print("Yes")
break
else:
print("No")
Problème C
$ A \ times B + C = N $, mais si vous décidez $ A, B $ tout en satisfaisant $ A \ times B <N $, ** $ C $ sera déterminé de manière unique **. Ici, comme $ 1 \ leqq A \ leqq N-1 $, le nombre ** pour $ B $ correspondant à ** $ A $ est calculé, mais lorsque $ N % A = 0 $, $ A \ $ B $ qui satisfait les temps B <N $ est $ B = 1,2,…, [\ frac {N} {A}] - 1 $ $ [\ frac {N} {A}] - 1 $ Donc, quand $ N % A \ neq 0 $, $ A \ times B <N $ est satisfait, $ B $ est $ B = 1,2,…, [\ frac {N} {A}] $ $ [\ frac {N} {A}] $ sera la rue. Par conséquent, il recherche tout et affiche le total.
C.py
n=int(input())
ans=0
for a in range(1,n):
if n%a==0:
ans+=(n//a-1)
else:
ans+=(n//a)
print(ans)
Problème D
J'ai l'impression d'avoir utilisé BIT dans le concours de production d'AtCoder pour la première fois. De plus, comme ce BIT peut ajouter des intervalles et que je ne l'ai pas implémenté, j'ai emprunté le BIT de kami. Fait. J'ai mis un modint dessus, je ne savais pas comment l'utiliser, et il était indexé en 1, donc je l'ai fait bogue pour toujours. ** Il est assez dangereux d'utiliser une bibliothèque que vous n'avez jamais utilisée ** ...
Tout d'abord, puisqu'il s'agit du nombre de méthodes de mouvement, considérons DP ** qui considère le mouvement comme une transition ($ dp [i]: = $ (nombre de méthodes de mouvement dans la masse $ i $) )). Cependant, cette fois, il y a des ** $ k $ sections **, donc si vous traitez chaque transition une par une, ce sera $ O (N ^ 2) $ et ce ne sera pas à temps. Ici, puisque $ k $ est de 10 au maximum, considérez ** bien gérer la transition pour chaque intervalle **. À ce stade, si l'intervalle est $ [l, r] $ et est dans la masse $ i $, alors $ dp [i + l] + = dp [i], dp [i + l + 1] + = dp [i] ],…, Dp [i + r] + = dp [i] $. Par conséquent, ** l'ajout de section doit être effectué de manière efficace et le BIT d'ajout de section doit être utilisé **.
Par conséquent, vous pouvez regarder $ i $ dans l'ordre croissant et ajouter à chacune des sections $ k $ dans l'ordre, et le montant du calcul sera $ O (Nk \ log {N}) $. De plus, puisque nous voulons trouver le reste de 998244353, nous devons mettre mod int dans BIT au lieu de long long ou int.
De plus, il semble y avoir une méthode de résolution avec $ O (NK) $ par la méthode imos, une méthode de réduction à un numéro de classe formel, et une méthode de résolution avec $ O (N \ log {N}) $ en utilisant un numéro de classe formel ( → article maspy) Mais je ne suis pas sûr, alors je vais sauter cette fois.
D.cc
//Options de débogage:-fsanitize=undefined,address
//Optimisation du compilateur
#pragma GCC optimize("Ofast")
//Inclure etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//macro
//pour 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.
//FORA est une gamme de déclaration(Si c'est difficile à utiliser, effacez-le)
#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--)
#define FORA(i,I) for(const auto& i:I)
//x est un conteneur tel que vector
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 998244353 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie
//Abréviation
#define PB push_back //Insérer
#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
/* BIT:BIT compatible RAQ
La valeur initiale est un_1 = a_2 = ... = a_n = 0
· Ajouter(l,r,x): [l,r)Ajouter x à
· Somme(i): a_1 + a_2 + ... + a_Calculer i
Tous les calculs sont O(logn)
*/
template <typename T>
struct BIT {
int n; //Nombre d'éléments
vector<T> bit[2]; //Emplacement de stockage des données
BIT(int n_) { init(n_); }
void init(int n_) {
n = n_ + 1;
for (int p = 0; p < 2; p++) bit[p].assign(n, 0);
}
void add_sub(int p, int i, T x) {
for (int idx = i; idx < n; idx += (idx & -idx)) {
bit[p][idx] += x;
}
}
void add(int l, int r, T x) { // [l,r)Ajouter à
add_sub(0, l, -x * (l - 1));
add_sub(0, r, x * (r - 1));
add_sub(1, l, x);
add_sub(1, r, -x);
}
T sum_sub(int p, int i) {
T s(0);
for (int idx = i; idx > 0; idx -= (idx & -idx)) {
s += bit[p][idx];
}
return s;
}
T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i ; }
};
template<ll mod> class modint{
public:
ll val=0;
//constructeur
modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
//Copier le constructeur
modint(const modint &r){val=r.val;}
//Opérateur arithmétique
modint operator -(){return modint(-val);} //unaire
modint operator +(const modint &r){return modint(*this)+=r;}
modint operator -(const modint &r){return modint(*this)-=r;}
modint operator *(const modint &r){return modint(*this)*=r;}
modint operator /(const modint &r){return modint(*this)/=r;}
//Opérateur d'assignation
modint &operator +=(const modint &r){
val+=r.val;
if(val>=mod)val-=mod;
return *this;
}
modint &operator -=(const modint &r){
if(val<r.val)val+=mod;
val-=r.val;
return *this;
}
modint &operator *=(const modint &r){
val=val*r.val%mod;
return *this;
}
modint &operator /=(const modint &r){
ll a=r.val,b=mod,u=1,v=0;
while(b){
ll t=a/b;
a-=t*b;swap(a,b);
u-=t*v;swap(u,v);
}
val=val*u%mod;
if(val<0)val+=mod;
return *this;
}
//Opérateur de comparaison d'équivalence
bool operator ==(const modint& r){return this->val==r.val;}
bool operator <(const modint& r){return this->val<r.val;}
bool operator !=(const modint& r){return this->val!=r.val;}
};
using mint = modint<MOD>;
//Flux d'E / S
istream &operator >>(istream &is,mint& x){//N'ajoutez pas de const à x
ll t;is >> t;
x=t;
return (is);
}
ostream &operator <<(ostream &os,const mint& x){
return os<<x.val;
}
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n,k;cin>>n>>k;
BIT<mint> dp(n);
vector<pair<ll,ll>> sec(k);
REP(i,k){
ll l,r;cin>>l>>r;
sec[i]=MP(l,r);
}
dp.add(1,2,1);
REP(i,n){
//cout<<i+1<<endl;
REP(j,k){
if(i+sec[j].F<=n){
dp.add(i+sec[j].F+1,min(i+sec[j].S+2,n+1),dp.sum(i+1)-dp.sum(i));
//cout<<i+1+sec[j].F<<" "<<min(i+1+sec[j].S+1,n+2)<<endl;
}
}
}
//cout<<1<<endl;
cout<<dp.sum(n)-dp.sum(n-1)<<endl;
}
E problème
Je pense qu'il y avait un problème de compatibilité descendante l'autre jour.
$ A_ {i + 1} = A_ {i} ^ 2 \ mod \ m $ et $ A \ 1 = x $, et trouvez $ \ sum {i = 1} ^ nA_i $. Pour le moment, $ n $ vaut 10 $ ^ 9 $ au maximum, il n'est donc pas possible de trouver toutes les rues.
Ici, puisque chaque terme est le reste de $ m $, il n'y a que $ m $ rues au plus **, et quand $ (A \ _i = A \ _j) \ mod \ m $ tient, $ (A ) Puisque _ {i + 1} = A \ _ {j + 1}) \ mod \ m $ tient, une boucle d'une longueur maximale de $ m $ apparaît dans la ** séquence $ A $.
Par conséquent, si vous pouvez trouver cette boucle, vous pouvez effectuer le calcul à grande vitesse en considérant combien de fois la boucle apparaît de ** $ A \ _1 $ à $ A \ _n $ **. Je pense que si vous savez comment trouver une boucle, vous pouvez l'implémenter à grande vitesse, donc je vais vous montrer comment trouver une boucle ci-dessous.
① ** Trouvez $ A \ _i $ où le reste apparaît deux fois **
v ... Un tableau qui stocke dans l'ordre dans lequel le reste apparaît
s ... réglé pour enregistrer le reste qui est sorti
Regardez $ A \ _1, A \ _2,… $ dans cet ordre et stockez-les dans v et s. À ce moment, si $ A \ _i $ avec la même valeur que stockée dans s apparaît, quittez ① avec cette valeur enregistrée.
② ** Séparez la boucle et l'avant de la boucle **
La valeur sauvegardée dans ① n'est pas incluse dans la boucle avant $ A \ _i $, qui apparaît pour la première fois. Par conséquent, il est séparé en cette partie (avant la boucle) et la partie après $ A \ _i $ (boucle).
Si $ A \ _n $ est avant la boucle, l'opération se termine à ce point et la sortie est effectuée. Si $ A \ _n $ est inclus dans la boucle, calculez avant la boucle, mettez à jour $ n $ avec le nombre de termes restant, mettez à jour v pour être une boucle uniquement, après avoir fait trois choses Passez à ③.
③ ** Calculez la boucle **
Vous pouvez demander les informations suivantes après ②.
l… longueur de la boucle
n… La longueur de la séquence restante
$ [\ frac {n} {l}] t… La somme des parties qui ne font pas le tour de la boucle
Calculez la boucle séparée en (2). Les informations ci-dessus sont faciles à trouver, donc la réponse est $ [\ frac {n} {l}] \ times s + t $.
E.py
n,x,m=map(int,input().split())
cand=[x]
cands=set()
cands.add(x)
for i in range(m):
c=(cand[-1]**2)%m
if c in cands:
break
else:
cand.append(c)
cands.add(c)
#Le début de la boucle
#print(cand)
p=cand.index(c)
if x<p:
print(sum(cand[:x]))
exit()
ans=sum(cand[:p])
cand=cand[p:]
#print(ans)
n-=p
#Nombre de boucles
tim=n//len(cand)
ama=n%len(cand)
ans+=tim*sum(cand)
ans+=sum(cand[:ama])
print(ans)
#print(p)
#print(cand)
Problème F
Il peut être résolu en utilisant l'addition d'intervalle BIT après C. Dans ce qui suit, j'ai essayé d'expliquer avec des mots autant que possible, mais il y a des parties que je n'ai pas été en mesure de transmettre, donc je pense que vous approfondirez votre compréhension en ** dessinant un diagramme et en expérimentant **.
Quand je l'ai vu pour la première fois, je l'ai mal lu et j'ai oublié les informations ** les plus proches **. Ici, si nous considérons le problème à l'aide d'un diagramme, ce sera comme suit.
En supposant que les opérations sont effectuées dans l'ordre des nombres encerclés, la partie indiquée par la flèche peut être peinte en blanc. À ce stade, en faisant attention à (1), par exemple, le nombre de cellules qui peuvent être peintes lorsque chaque ligne est sélectionnée est petit. De même, si vous faites attention à ②, vous pouvez réduire le nombre de carrés pouvant être peints lorsque chaque colonne est sélectionnée. De plus, en ce qui concerne (4), puisqu'il n'est pas possible de réduire le nombre de cellules de (2), toute cellule noire de cette colonne peut être rendue blanche. En d'autres termes, lorsque vous sélectionnez une ligne (ou une colonne), vous pouvez voir qu'il existe des opérations qui modifient le nombre de cellules qui peuvent changer la couleur d'une colonne (ou ligne) et des opérations qui ne changent pas **.
Maintenant, après plus d'expérimentation, je vais enregistrer la colonne la plus à gauche ($ r
(✳︎)… Si vous pensez dans la figure, si vous avez sélectionné $ (d, 1) $ dans ①, tout élément de $ row $ sera remplacé de $ n $ à $ d $. Autrement dit, ajoutez simplement $ d-n $ à n'importe quel élément. La même chose peut être dite pour toute opération.
F.cc
//Options de débogage:-fsanitize=undefined,address
//Optimisation du compilateur
#pragma GCC optimize("Ofast")
//Inclure etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//macro
//pour 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.
//FORA est une gamme de déclaration(Si c'est difficile à utiliser, effacez-le)
#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--)
#define FORA(i,I) for(const auto& i:I)
//x est un conteneur tel que vector
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie
//Abréviation
#define PB push_back //Insérer
#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
/* BIT:BIT compatible RAQ
La valeur initiale est un_1 = a_2 = ... = a_n = 0
· Ajouter(l,r,x): [l,r)Ajouter x à
· Somme(i): a_1 + a_2 + ... + a_Calculer i
Tous les calculs sont O(logn)
*/
template <typename T>
struct BIT {
int n; //Nombre d'éléments
vector<T> bit[2]; //Emplacement de stockage des données
BIT(int n_) { init(n_); }
void init(int n_) {
n = n_ + 1;
for (int p = 0; p < 2; p++) bit[p].assign(n, 0);
}
void add_sub(int p, int i, T x) {
for (int idx = i; idx < n; idx += (idx & -idx)) {
bit[p][idx] += x;
}
}
void add(int l, int r, T x) { // [l,r)Ajouter à
add_sub(0, l, -x * (l - 1));
add_sub(0, r, x * (r - 1));
add_sub(1, l, x);
add_sub(1, r, -x);
}
T sum_sub(int p, int i) {
T s(0);
for (int idx = i; idx > 0; idx -= (idx & -idx)) {
s += bit[p][idx];
}
return s;
}
T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i ; }
};
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n,q;cin>>n>>q;
BIT<ll> row(n);
row.add(1,n+1,n);
BIT<ll> column(n);
column.add(1,n+1,n);
ll d,r;d=n;r=n;
ll ans=0;
REP(_,q){
ll x,y;cin>>x>>y;
if(x==1){
ans+=column.sum(y)-column.sum(y-1)-2;
//cout<<column.sum(y)-column.sum(y-1)-1<<endl;
if(y<r){
row.add(1,d,(y-row.sum(1)));
r=y;
}
}else{
ans+=row.sum(y)-row.sum(y-1)-2;
//cout<<row.sum(y)-row.sum(y-1)-1<<endl;
if(y<d){
column.add(1,r,(y-column.sum(1)));
d=y;
}
}
}
cout<<(n-2)*(n-2)-ans<<endl;
}
Recommended Posts