[PYTHON] Yukicoder-Wettbewerb 259 Bewertung

Ergebnis

Impressionen

A Ich fand das Problem schwierig und rannte weg. Es ist nicht schwierig, wenn Sie den Grundlagen folgen, also bereue ich es. Beim B-Problem habe ich einen Fehler in der konstanten und verlorenen Zeit gemacht. Es tut mir Leid ... Das C-Problem war eine Art Problem, das ich nicht viel getan hatte, aber ich löste es. Ich bin froh, dass ich klebrig war.

Problem A

① Der Bereich von $ t $ hängt von $ D $ ab, und $ D $ ist ** extrem groß **. Es ist erforderlich, den ** Mindestwert ** $ T $ für $ t $ ② $ t <T $ zu ermitteln Da es ** Monotonie ** gibt, die für $ t> T $ gilt, kann $ T $ aufgrund dieser beiden Bedingungen durch Dichotomie erhalten werden. Wenn die von jedem Schleim in einem bestimmten $ t $ zurückgelegte Gesamtstrecke mit $ O (N) $ berechnet wird, beträgt der Berechnungsbetrag $ O (N \ log {D}) $. Wenn Sie also rechtzeitig ein Programm schreiben können Ich dachte.

Betrachten Sie nun die Gesamtfahrstrecke aller Schleime in $ t $, aber wenn zwei Schleime (Geschwindigkeiten sind $ v_1 $, $ v_2 $) zu einem Schleim kombiniert werden, die Geschwindigkeit der verbleibenden Schleime Das Ergebnis ist $ v_1 + v_2 $. Wenn Sie also * auf die insgesamt zurückgelegte Strecke achten **, ändert sich dies nicht, selbst wenn nicht jeder Schleim verschmilzt. Wenn Sie also berücksichtigen, wie weit sich alle Schleime bis zu $ t $ bewegen (wenn sie nicht verschmelzen), $ O. Sie kann mit (N) $ berechnet werden.

Weitere Informationen zur Dichotomie finden Sie in diesem Artikel. Außerdem kann dieses Problem mit $ O (N) $ anstelle von $ O (N \ log {D}) $ (Hauptlösung gelöst werden. Leitartikel)).

A.py

n,d=map(int,input().split())
x=list(map(int,input().split()))
v=list(map(int,input().split()))
s=sum(v)

def f(k):
    return s*k

#Ich bin falsch,r ist wahr
l,r=0,1000000000000
while l+1<r:
    k=l+(r-l)//2
    if f(k)>=d:
        r=k
    else:
        l=k
print(r)

B-Problem

Überprüfen Sie zunächst alle Primzahlen, die vom Eratostenes-Sieb ** bestimmt werden können, da die Abfrage zur Bestimmung der Primzahl verwendet wird (dies führt zur Bestimmung der Primzahl der Abfrage $ O (1) $). Wenn festgestellt wird, dass $ p $ keine Primzahl ist, sollte $ -1 $ ausgegeben werden. Wir gehen also davon aus, dass $ p $ eine Primzahl ist, und fahren mit der folgenden Diskussion fort.

Wenn Sie also einfach nach $ A ^ {P!} \ (Mod \ P) $ als $ ((A ^ 1) ^ 2) ^ 3… $ fragen, wird dies selbst unter der Bedingung von $ mod \ P $ nicht rechtzeitig sein. Hmm. Woran man sich hier erinnern sollte, ist der Satz von ** Fermat **. Ich denke, Sie sollten bedenken, dass es allgemein bekannt ist, wenn Probleme im Zusammenhang mit der Macht des Überschusses auftreten. In diesem Theorem gilt ** $ A ^ {p-1} = 1 \ (mod \ p) $ ** für $ A $, was kein Vielfaches von $ p $ für die Primzahl $ p $ ist. Hier gilt $ A ^ {p!} = (A ^ {p-1}) ^ x \ (x = 1,2,…, p-2, p) , also ( \ weil \ p $ ist $ 2 $ oder mehr als eine Primzahl), $ A ^ {p!} = 0 \ (mod \ P) $, wenn $ A $ ein Vielfaches von $ p $ ist, $ A ^ {p!} = 1 \ andernfalls Es wird (mod \ P) $.

Zusammenfassend lässt sich sagen, dass $ -1 $, wenn $ p $ keine Primzahl ist, $ 0 $, wenn $ p $ eine Primzahl ist und $ A % p = 0 $, und $ A % p , wenn $ p $ eine Primzahl ist. Wenn neq 0 $ ist, sollte $ 1 $ ausgegeben werden.

** Ich habe vergessen, den Bereich von "MAXRR" im Code zu ändern und habe WA ausgegeben **. Es war schmerzhaft. Das hat viel Zeit gekostet.

B.cc

//Compileroptimierung
#pragma GCC optimize("Ofast")
//Einschließen usw.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//Makro
//für Schleife
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Enden)、のどちらOder
//Schleifenvariablen ohne D werden um 1 erhöht, und Schleifenvariablen mit D werden um 1 dekrementiert.
//FORA ist ein Bereich für Aussagen(Wenn es schwer zu bedienen ist, löschen Sie es)
#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 ist ein Container wie ein Vektor
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//Konstante
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 6000000 //10^5:Maximale Reichweite des Arrays
//Abkürzung
#define PB push_back //Einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares

#define PN true //Primzahl
#define NPN false //Keine Primzahl
//Nicht wesentlich
#define MAXRR 3000 //√ Stellen Sie eine Zahl größer oder gleich MAXR ein

//Angenommen, ganze Zahlen bis MAXR sind Primzahlen(Von hier aus rasieren)
vector<bool> PN_chk(MAXR+1,PN);//0index entspricht der i-ten ganzen Zahl i(0~MAXR)
//Bereiten Sie ein Array zum Speichern von Primzahlen vor
vector<ll> PNs;

void se(){
    //0 und 1 sind keine Primzahlen
    PN_chk[0]=NPN;PN_chk[1]=NPN;

    FOR(i,2,MAXRR){
        //Eine Primzahl, wenn bei Ihrer Ankunft davon ausgegangen wird, dass es sich um eine Primzahl handelt
        if(PN_chk[i]) FOR(j,i,ll(MAXR/i)){PN_chk[j*i]=NPN;}
    }
    FOR(i,2,MAXR){
        if(PN_chk[i]) PNs.PB(i);
    }
}

ll modpow(ll a,ll n,ll p){
    if(n==0)return 1;
    ll t=modpow(a,n/2,p);
    t=t*t%p;
    if(n&1)t=t*a%p;
    return t;
}

signed main(){
    //Code zur Beschleunigung der Eingabe
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    se();
    ll t;cin>>t;
    REP(_,t){
        ll a,p;cin>>a>>p;
        if(!PN_chk[p]){
            cout<<-1<<endl;
            continue;
        }
        if(a%p==0){
            cout<<0<<endl;
            continue;
        }
        cout<<1<<endl;
    }
}

C-Problem

Wenn ich das ähnliche Thema kennen würde, könnte ich mein Bestes geben, um es umzusetzen, also fühlte ich die Kraft der Hingabe.

Wenn Sie $ r_i und c_i $ wie unten gezeigt eingeben, können Sie sie zunächst in die vier in der folgenden Abbildung gezeigten Teile unterteilen.

Auf dieser Grundlage können wir sehen, dass die zu erhaltende Antwort darin besteht, das Produkt der Produkte der Zahlen zu erhalten, die in jedem der Rechtecke ①, ②, ③ und ④ enthalten sind. Für den Teil, der in einem solchen Rechteck enthalten ist, kann die Abfrageverarbeitung mit $ O (1) $ durchgeführt werden, indem mit ** zweidimensionaler Akkumulation ** vorberechnet wird.

Bei der Erstellung einer Tabelle durch Vorberechnung ist ** im Fall einer zweidimensionalen kumulativen Summe ** wie folgt. Außerdem ist jedes Quadrat $ a [x] [y] $, und die folgenden sind alle 0-indiziert.

$ s [x] [y]: = [0, x) × [0, y) Die Summe der rechteckigen Abschnitte von $ s[x+1][y+1] = s[x][y+1] + s[x+1][y] - s[x][y] + a[x][y]

Im Fall von ** zweidimensionalem kumulativem Produkt ** ist es daher wie folgt, wenn es auf die gleiche Weise durchgeführt wird.

$ s [x] [y]: = [0, x) × [0, y) $ Produkt aus rechteckigen Abschnitten s[x+1][y+1] = s[x][y+1] \times s[x+1][y] \div s[x][y] \times a[x][y]

Daher kann dieses ** zweidimensionale kumulative Produkt in vier Richtungen ** definiert werden, und die verbleibenden drei rechteckigen Abschnitte sind wie folgt. Der Ausdruck des Intervalls unterscheidet sich von der Definition der Mathematik, aber ich hoffe, Sie können die Atmosphäre verstehen. (Ich habe versucht, dies in einer Atmosphäre zu tun, ohne Folgendes zu beschreiben. ** Ich werde die Richtlinie gründlich beschreiben **.)

$ s [x] [y]: = [w-1, x) × [0, y) $ Produkt rechteckiger Abschnitte s[x-1][y+1] = s[x][y+1] \times s[x-1][y] \div s[x][y] \times a[x][y]

$ s [x] [y]: = [0, x) × [h-1, y) $ Produkt rechteckiger Abschnitte s[x+1][y-1] = s[x][y-1] \times s[x+1][y] \div s[x][y] \times a[x][y]

$ s [x] [y]: = [w-1, x) × [h-1, y) $ Produkt rechteckiger Abschnitte s[x+1][y+1] = s[x][y+1] \times s[x+1][y] \div s[x][y] \times a[x][y]

Wenn Sie dies implementieren können, können Sie ein Programm schreiben, indem Sie ** feststellen, dass es sich um einen offenen Abschnitt handelt **. Außerdem habe ich meine Modint-Bibliothek verwendet, da ich nur den Rest geteilt durch $ 10 ^ 9 + 7 $ finden muss.

Nachtrag (8/2)

Das Teilen von 0 durch Teilen des gefüllten Teils vom Ganzen ist mühsam, daher ist es besser zu wissen, dass ** das Problem, das Produkt aus mehreren Zahlen zu finden, nur durch das Produkt ** ausgedrückt wird.

C.cc

//Compileroptimierung
#pragma GCC optimize("Ofast")
//Einschließen usw.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//Makro
//für Schleife
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Enden)、のどちらOder
//Schleifenvariablen ohne D werden um 1 erhöht, und Schleifenvariablen mit D werden um 1 dekrementiert.
//FORA ist ein Bereich für Aussagen(Wenn es schwer zu bedienen ist, löschen Sie es)
#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 ist ein Container wie ein Vektor
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//Konstante
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays
//Abkürzung
#define PB push_back //Einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares

template<ll mod> class modint{
public:
    ll val=0;
    //Konstrukteur
    modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
    //Konstruktor kopieren
    modint(const modint &r){val=r.val;}
    //Arithmetischer Operator
    modint operator -(){return modint(-val);} //einstellig
    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;}
    //Aufgabenverwalter
    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;
    }
    //Äquivalenzvergleichsoperator
    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>;

//E / A-Stream
istream &operator >>(istream &is,mint& x){//Fügen Sie x nicht const hinzu
    ll t;is >> t;
    x=t;
    return (is);
}
ostream &operator <<(ostream &os,const mint& x){
    return os<<x.val;
}

//Leistung
mint modpow(const mint &a,ll n){
    if(n==0)return 1;
    mint t=modpow(a,n/2);
    t=t*t;
    if(n&1)t=t*a;
    return t;
}



signed main(){
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll h,w;cin>>h>>w;
    vector<vector<ll>> A(h,vector<ll>(w,0));
    REP(i,h)REP(j,w)cin>>A[i][j];
    vector<vector<vector<mint>>> s(4,vector<vector<mint>>(h+1,vector<mint>(w+1,1)));
    REP(j,h){
        REP(k,w){
            ll x,y;
            x=j;y=k;
            s[0][x+1][y+1]=s[0][x+1][y]*s[0][x][y+1]/s[0][x][y]*A[x][y];
        }
    }
    REP(j,h){
        REP(k,w-1){
            ll x,y;
            x=j;y=w-1-k;
            s[1][x+1][y-1]=s[1][x+1][y]*s[1][x][y-1]/s[1][x][y]*A[x][y];
        }
    }
    REP(j,h-1){
        REP(k,w){
            ll x,y;
            x=h-1-j;y=k;
            s[2][x-1][y+1]=s[2][x-1][y]*s[2][x][y+1]/s[2][x][y]*A[x][y];
        }
    }
    REP(j,h-1){
        REP(k,w-1){
            ll x,y;
            x=h-1-j;y=w-1-k;
            s[3][x-1][y-1]=s[3][x-1][y]*s[3][x][y-1]/s[3][x][y]*A[x][y];
        }
    }
    #if 0
    REP(i,4){
        REP(j,h){
            REP(k,w){
                cout<<s[i][j][k]<<" ";
            }
            cout<<endl;
        }
        cout<<endl;
    }
    #endif
    ll q;cin>>q;
    REP(_,q){
        ll r,c;cin>>r>>c;
        mint ans=1;
        ll x,y;
        x=r-1;y=c-1;
        ans*=s[0][x][y];
        //x=r;y=w-c;
        ans*=s[1][x][y];
        //x=h-r;y=c;
        ans*=s[2][x][y];
        //x=h-r;y=w-c;
        ans*=s[3][x][y];
        cout<<ans<<endl;
    }
}