[PYTHON] AtCoder Beginner Contest 107 Revue des questions précédentes

Temps requis

Impressions

Le problème était difficile et j'ai lutté quelques jours après Bachacon. J'avais besoin de beaucoup de capacité de réflexion et de connaissance du BIT (Binary Indexed Tree), alors j'aimerais le résumer. J'ai expliqué le BIT dans Un autre article d'une manière facile à comprendre, alors veuillez vous y référer.

Problème A

Notez que ce que vous devez afficher est «n-i + 1».

answerA.py

n,i=map(int,input().split())
print(n-i+1)

Problème B

Je veux utiliser numpy pour ce genre de problème de grille. J'espère pouvoir apprendre à utiliser numpy dans un proche avenir. L'implémentation est facile à comprendre si les opérations excluant les lignes et les colonnes sont effectuées séparément.

answerB.py

h,w=map(int,input().split())
a=[]
#Exclut les lignes constituées uniquement de carrés blancs
for i in range(h):
    k=input()
    if k!="."*w:
        a.append(k)
l=len(a)

ans=[[] for i in range(l)]
#Exclut les colonnes constituées uniquement de carrés blancs
for i in range(w):
    for j in range(l):
        if a[j][i]=="#":
            for k in range(l):
                ans[k].append(a[k][i])
            break
for i in range(l):
    print("".join(ans[i]))

Problème C

Il est préférable d'allumer ** k bougies consécutives **, et il y a n-k + 1 candidats possibles. De plus, puisque nous sommes au point de coordonnée 0 au début, il y a deux modèles pour chaque candidat, l'un qui va de la coordonnée 0 → extrémité gauche → extrémité droite et l'autre qui va de la coordonnée 0 → extrémité droite → extrémité gauche, donc ceci $ 2 \ times (n) -k + 1) Trouvez le temps minimum (= distance parcourue) dans la rue $.

answerC.py

n,k=map(int,input().split())
x=list(map(int,input().split()))
mi=10**10
for i in range(n-k+1):
    mi=min(mi,x[k-1+i]-x[i]+min(abs(x[i]),abs(x[k-1+i])))
print(mi)

Problème D

J'ai essayé de bien trouver la médiane, mais ** mal lu ** que la séquence de nombres donnée a été triée en premier lieu. De plus, j'ai lu et compris la bonne réponse, mais j'ai senti que c'était assez difficile et que mes capacités étaient insuffisantes. Cependant, c'était un problème très instructif, je voudrais donc l'expliquer en détail. De plus, comme mentionné dans l'impression précédente, le BIT sera expliqué comme connu, veuillez donc vous référer à cet article pour le BIT. ..

Premièrement, nous devons ** faire abstraction de la condition médiane pour la rendre plus facile à trouver ** (ce sens de l'abstraction est susceptible d'augmenter à mesure que nous résolvons plus de problèmes).

En supposant que la valeur médiane de la séquence de nombres b de longueur M est x, il y a plus de $ [\ frac {M} {2}] $ et plus d'éléments dans ①: b, et ②: ① est satisfait. Deux conditions sont requises: x est le maximum. … (✳︎)

Ce que vous pouvez voir, c'est que c'est ** monotone . On voit donc que la valeur médiane peut être trouvée par la dichotomie ( médiane → la dichotomie semble se produire fréquemment **).

Puisque j'ai trouvé que je peux le trouver par dichotomie, je vais considérer "des conditions où la valeur médiane de la séquence de numéros de sujet $ m $ est ** x ou plus **" ... (1).

À partir de (✳︎), (1) définit la valeur médiane de $ (a_l, a_ {l + 1},…, a_ {r}) $ à $ m_ {l, r} (1 \ leqq l \ leqq r \ leqq N) Il y a $ [\ frac {_ {n + 1} C 2} {2}] $ ou plus $ m {l, r} $ qui est x ou plus quand c'est $ ... (2) Je peux le faire.

De plus, si (✳︎) est utilisé de la même manière, $ (a_l, a_ {l + 1},…, a_ {r}) $ a un élément de x ou plus dans $ pour $ m_ {l, r} $ pour être x ou plus. Vous pouvez également voir que [\ frac {r-l + 1} {2}] $ ou plus est suffisant. … (3)

Par conséquent, seules les informations de ** x ou plus ou moins de x sont requises **, donc si le premier est remplacé par 1 et le second est ** remplacé par -1, (3) est $ (a_l, a_ {l +). 1},…, a_ {r}) La somme cumulée de $ elements $ S_ {l, r} $ est égale ou supérieure à 0… (4).

Ici, si la somme cumulée $ S_k $ de $ (a_1, a_2,…, a_ {k}) $ est obtenue et sauvegardée d'abord par la somme cumulée, $ S_ {l, r} = S_r-S_ {l -1} $, et (4) est $ S_r-S_ {l-1} \ geqq 0 \ leftrightarrow S_ {l-1} \ leqq Il peut être reformulé comme S_r $… (5).

De plus, (5) est $ S_ {l-1} \ leqq Puisqu'il s'agit de S_r (1 \ leqq l \ leqq r \ leqq N) $, c'est la même valeur même si elle est reformulée comme $ S_l \ leqq S_r (0 \ leqq l <r \ leqq N) $… (6).

D'après les considérations ci-dessus, la condition de (1) est que $ 0 \ leqq l <r \ leqq N $ est satisfait et $ S_l \ leqq S_r $ est $ [\ frac {_ {n + 1 } C _2} {2}] Il peut être reformulé qu'il y a $ ou plus, et nous envisagerons de le demander.

De plus, si vous considérez $ l et r $ à ce moment, le montant du calcul sera $ O (n ^ 2) $, mais avec ** r fixed (r \ *) **, $ S_l \ $ l $ qui satisfait leqq S_ {r ^ \ *} $ et $ 0 \ leqq l <r ^ \ * $ est en fait obtenu par $ O (\ log {n}) $ en utilisant ** BIT, donc $ O (n \ log {n}) $ peut être utilisé pour déterminer la paire de $ l, r $.

Lors de l'utilisation de BIT plus tôt, le $ i $ ème élément (indexé 1) du tableau $ B $ géré par BIT est mis à ** Somme cumulée $ S_r (0 \ leqq r \ leqq r ^ \ * - 1) Satisfaire $ S_l \ leqq S_ {r ^ \ *} $ et $ 0 \ leqq l <r ^ \ * $ en définissant le nombre de fois où $ i $ apparaît dans $ **. $ l $ peut être calculé par $ B_1 + B_2 +… + B_ {S_ {r ^ \ *}} $.

Aussi, pour ** combien de fois la somme cumulée $ S_r (0 \ leqq r \ leqq r ^ \ * -1) $ qui devient $ i $ apparaît **, $ B_ {S_ pour chaque r Ajoutez simplement {r}} $.

De plus, la somme cumulée $ S_r (0 \ leqq r \ leqq n) $ peut être inférieure ou égale à 0, donc $ 1-S_min $ est ajouté à toutes les sommes cumulées de sorte que la valeur minimale soit 1.

Si tout ce qui précède est mis en œuvre, ce sera comme suit.

✳︎… Même après l'établissement de la politique de mise en œuvre, j'ai fait une erreur dans l'index et la sortie du segfo ou fait une erreur dans ce qui devrait être produit, donc je voudrais être prudent.

answerD.cc

//Comprendre(Ordre alphabétique,bits/stdc++.Une faction qui n'utilise pas h)
#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

    //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-1 + 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;
    }
};

ll solve(vector<ll>& a,ll x,ll n){
    vector<ll> b(n,-1);
    REP(i,n)if(a[i]>=x)b[i]=1;
    vector<ll> s(n+1,0);
    
    //C'était différent ici ...
    FOR(i,1,n)s[i]=s[i-1]+b[i-1];

    ll base=1-MIN(s);REP(i,n+1)s[i]+=base;
    BIT T(MAX(s));
    ll ret=0;
    REP(i,n+1){
        ret+=T.sum(s[i]);
        T.add(s[i],1);
    }
    return ret;
}

signed main(){
    ll n;cin >> n;
    vector<ll> a(n,0);vector<ll> c(n,0);
    REP(i,n){cin >> a[i];c[i]=a[i];}
    sort(ALL(c));c.erase(unique(ALL(c)),c.end());
    //Trouvez la réponse par dichotomie
    ll check=((n+1)*n/2)/2;
    ll l,r;l=0;r=SIZE(c)-1;
    while(r>l+1){
        ll h=(l+r)/2;
        if(solve(a,c[h],n)>=check){
            l=h;
        }else{
            r=h;
        }
    }
    #if 0
    //Code de débogage
    REP(i,SIZE(c)){
        cout << c[i] << " " << solve(a,c[i],n) << endl;
    }
    #endif

    //Encore une fois, l'erreur d'inverser l et r ...
    if(solve(a,c[r],n)>=check){
        cout << c[r] << endl;
    }else{
        cout << c[l] << endl;
    }
}