[PYTHON] concours yukicoder 263 avis

résultat

スクリーンショット 2020-08-29 12.03.11.png

Impressions

Je suis mort comme la dernière fois. C'est un problème qui devrait toujours être résolu quand je meurs, et j'ai l'impression d'avoir oublié le cas du coin ou de l'avoir mis sur bug dans l'implémentation **. ** Quand sera-t-il possible d'analyser calmement la cause pendant le concours?

Problème A

A^2 -B^2 =N \leftrightarrow (A-B)(A+B)=N

Puisque la formule peut être transformée comme ci-dessus et que la régularité de ** $ AB $ et $ A + B $ correspond , $ (AB, A + B) = $ (pair, pair), (impair, impair) Ça devrait être. En outre, à ce stade, le premier doit être un multiple de 4 et le second doit être un nombre impair. Aussi, puisque $ A-B <A + B $, si $ N = 4,1 $ ne tient pas ( case du coin! **), ce sera comme suit.

A.py


n=int(input())
if n%2==1:
    if n==1:
        print(-1)
    else:
        print(1)
elif n%4==0:
    if n==4:
        print(-1)
    else:
        print(1)
else:
    print(-1)

Problème B

J'ai résolu beaucoup de problèmes de DP ces derniers jours, donc j'ai pu les résoudre assez rapidement. Cependant, c'est le reflet que j'ai fait une erreur dans l'indice ** et que je suis devenu WA **.

Pour ce problème, vous pouvez voir que vous devriez regarder les bonbons ** dans l'ordre **. Cependant, ** ne peut pas être effectué par la méthode gourmande **, donc le DP suivant est défini.

$ dp [i] [j]: = $ (Bonheur maximum lors de la sélection d'un nombre impair (ou pair) de bonbons lors de la prise jusqu'au $ i $ e bonbon)

Cependant, lorsque $ j = 0 $, le nombre est impair, et lorsque $ j = 1 $, le nombre est impair.

À ce stade, la transition n'est pas difficile et se déroule comme suit.

(1) Mettre à jour $ dp [i + 1] [0] $

Si vous ne choisissez pas $ a [i + 1] $, $ dp [i] [0] $ Lors du choix de $ a [i + 1] $, $ dp [i] [1] + a [i + 1] $

(2) Mettre à jour $ dp [i + 1] [0] $

Si vous ne choisissez pas $ a [i + 1] $, $ dp [i] [1] $ Lors du choix de $ a [i + 1] $, $ dp [i] [0] -a [i + 1] $

B.py


n,m=map(int,input().split())
a=[sum(list(map(int,input().split()))) for i in range(n)]
dp=[[0,0] for i in range(n)]
dp[0][0]=a[0]
for i in range(n-1):
    #Manger ou pas
    dp[i+1][0]=max(dp[i][0],dp[i][1]+a[i+1])
    dp[i+1][1]=max(dp[i][1],dp[i][0]-a[i+1])
print(max(dp[n-1]))

Problème C

J'ai fait l'erreur de penser à une seule des équations qui sont apparues en premier, puis j'ai fait la bonne politique, mais j'ai senti que ** la mise en œuvre était gênante **, et par conséquent j'ai fait ** une mise en œuvre désordonnée **, donc la dernière Je n'ai pas pu avoir un seul cas de WA.

J'étais tellement impatient au début que je ne pouvais pas mettre en place une politique, alors je veux être ** calme ** là-bas. Ces jours-ci, ma mentalité est si terrible que je ne peux pas du tout le faire ...

Premièrement, si vous mettez le problème dans une formule, ce sera $ A \ fois B = X-C, A \ fois C = Y-B $. Lorsque cela est transformé, $ (A-1) (B-C) = X-Y, (A + 1) (B + C) = X + Y $. Aussi, pour rendre l'implémentation plus facile, supposons que $ X \ geqq Y $ tient, et si ce n'est pas le cas, échangez.

En se concentrant sur $ (A-1) (BC) = XY $, $ A-1 $ est une fraction de $ XY $, donc ** $ O (\ sqrt {X}) $ est $ A $. Les candidats peuvent être énumérés **. De plus, quand $ A $ est fixe, $ B-C = \ frac {X-Y} {A-1}, B + C = \ frac {X + Y} {A + 1} $ tient. Par conséquent, si vous définissez $ v = \ frac {XY} {A-1}, w = \ frac {X + Y} {A + 1} $, alors $ B = \ frac {v + w} {2}, C = \ frac {wv} {2} $ tient. À ce stade, $ B, C $ peut ne pas être un entier, mais le transtyper en un type entier et trouver $ B, C $. Pour ce $ B, C $, vérifiez si $ (A-1) (BC) = XY, (A + 1) (B + C) = X + Y $ tient, et comptez le nombre. ..

De plus, puisque la discussion ci-dessus est basée sur l'hypothèse de $ X \ neq Y $, il est nécessaire de considérer le cas de ** $ X = Y $ séparément **. Lorsque $ X = Y $, à partir de $ (A-1) (B-C) = 0 \ leftrightarrow A = 1 \ ou \ B = C $, vous pouvez diviser les observations comme suit.

(1) Lorsque $ A = 1 $ Depuis $ (A + 1) (B + C) = X + Y \ leftrightarrow B + C = X $, $ (B, C) = (1, X-1), (2, X-2),…, Il y a des rues $ X-1 $ de (X-1,1) $.

(2) Lorsque $ B = C $ De $ (A + 1) (B + C) = X + Y \ leftrightarrow (A + 1) B = X $, $ A + 1 $ est une fraction de $ X $ et peut être utilisé dans la discussion précédente. .. Cependant, lorsque ** $ \ frac {X} {A + 1} $ devient 1 ou 2, il est nécessaire de séparer soigneusement les cas **, mais il a été traité séparément comme un ** cas d'angle **. ..

C.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 int 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


ll check_divisors(ll x,ll y){
    ll ret=0;
    ll n=x-y;
    vector<ll> divisors;//Un tableau qui stocke les fractions
    FOR(i,1,sqrt(n)){
        if(n%i==0){
            divisors.PB(i);
            if(i!=n/i){
                divisors.PB(n/i);
            }
        }
    }
    //a-Candidat pour 1
    FORA(i,divisors){
        ll a,b,c;a=i+1;
        ll v,w;v=n/(a-1);w=(x+y)/(a+1);
        b=(v+w)/2;c=(w-v)/2;
        if(b>0 and c>0 and (a-1)*(b-c)==(x-y) and (a+1)*(b+c)==(x+y)){
            ret++;        
        }
    }
    return ret;
}

ll check_divisors2(ll x,ll y){
    ll ret=x-1;
    FOR(i,3,sqrt(x)){
        if(x%i==0){
            if(i!=ll(x/i)){
                ret+=2;
            }else{
                ret++;
            }
        }
    }
    if(x%2==0){
        if(2!=ll(x/2) and x!=2){
            ret++;
        }
    }
    if(x!=1 and x!=2)ret++;
    return ret;
}

signed main(){
    //Code pour accélérer la saisie
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll s;cin>>s;
    REP(i,s){
        ll x,y;cin>>x>>y;
        if(x<y)swap(x,y);
        if(x==y){
            cout<<check_divisors2(x,y)<<endl;
        }else{
            cout<<check_divisors(x,y)<<endl;
        }
    }
}

Problème après D

Je ne résoudrai pas cette fois.

Recommended Posts

concours yukicoder 259 avis
concours yukicoder 264 avis
concours yukicoder 261 avis
concours yukicoder 267 avis
concours yukicoder 266 avis
concours yukicoder 263 avis
yukicoder contest 268 avis
AtCoder Grand Contest 041 Critique
yukicoder contest 265 Record de participation
Revue du concours régulier AtCoder 105
yukicoder contest 263 Record de participation
concours yukicoder 243 Record de participation
record de 256 entrées
yukicoder contest 273 Record de participation
Examen du concours de programmation Keyence 2020
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
concours yukicoder 252 Record de participation
concours yukicoder 259 Record de participation
Critique du concours AtCoder
concours yukicoder 249 Record de participation
AtCoder Débutant Contest 169 Évaluation
concours yukicoder 271 Record de participation
AtCoder Grand Contest 048 Critique
record de participation au concours 267 de yukicoder
Critique du concours AtCoder Débutant 181
Concours yukicoder 251 Record de participation
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
yukicoder contest 242 Record de participation
Critique du concours AtCoder Débutant 180
concours yukicoder 241 Record de participation
Critique du concours AtCoder pour débutant 177
AtCoder Débutant Contest 168 Critique
AtCoder Grand Contest 045 Critique
Revue du concours de programmation NOMURA 2020
AtCoder Grand Contest 044 Critique
yukicoder contest 245 record d'inscription
yukicoder contest 257 Record de participation
record de participation au concours yukicoder 250
Concours yukicoder 254 Record de participation
Critique du concours AtCoder pour débutant 172
AtCoder Regular Contest 106 Évaluation
yukicoder contest 246 Record de participation
concours yukicoder 275 Record de participation
Concours yukicoder 274 Record de participation
Critique du concours AtCoder
AtCoder Grand Contest 046 Critique
AtCoder Débutant Contest 175 Critique
Examen du concours de programmation HHKB 2020
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
yukicoder contest 261 Record de participation
AtCoder Débutant Contest 170 Critique
Revue du concours régulier AtCoder 104
record du concours 262
Critique du concours AtCoder