[PYTHON] AtCoder Beginner Contest 179 Review
This time's results
Impressions of this time
This time was also a disappointing result. I didn't have time to solve the F problem because I had been bugging the D problem all the time. If the F problem has BIT (or Seg tree), it is not so difficult, so I think I could solve it in about 15 minutes.
Problem A
I wrote the judgment conditions in reverse and spent some time.
A.py
s=input()
if s[-1]!="s":
print(s+"s")
else:
print(s+"es")
B problem
You just have to obediently judge whether they are equal or not. Be careful only with out-of-array references.
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")
C problem
$ A \ times B + C = N $, but if you decide $ A, B $ while satisfying $ A \ times B <N $, ** $ C $ will be uniquely determined **. Here, as $ 1 \ leqq A \ leqq N-1 $, the number ** for $ B $ corresponding to ** $ A $ is calculated, but when $ N % A = 0 $, $ A \ $ B $ that satisfies times B <N $ is $ B = 1,2,…, [\ frac {N} {A}]-1 $ $ [\ frac {N} {A}]-1 $ So, when $ N % A \ neq 0 $, $ A \ times B <N $ is satisfied $ B $ is $ B = 1,2,…, [\ frac {N} {A}] $ $ [\ frac {N} {A}] $ will be the street. Therefore, a full search is performed and the total is output.
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)
D problem
I feel like I used BIT in the AtCoder production contest for the first time. Also, since this BIT can add intervals and I did not implement it, I borrowed kami's BIT. Did. I put modint on it, I didn't know how to use it, and it was 1-indexed, so I made it a bug forever. ** It's pretty dangerous to use a library you've never used ** ...
First, since it is the number of movement methods, consider the DP ** that regards movement as a transition ($ dp [i]: = $ (number of movement methods when in the mass $ i $). )). However, this time there are ** $ k $ intervals **, so if you process each transition one by one, it will be $ O (N ^ 2) $ and it will not be in time. Here, since $ k $ is 10 at the maximum, consider ** handling the transition for each interval well **. At this time, if the interval is $ [l, r] $ and is in the mass $ i $, then $ dp [i + l] + = dp [i], dp [i + l + 1] + = dp [i] ],…, dp [i + r] + = dp [i] $. Therefore, ** the interval addition should be performed efficiently, and the interval addition BIT should be used **.
Therefore, you can look at $ i $ in ascending order and add to each of the $ k $ intervals in order, and the amount of calculation will be $ O (Nk \ log {N}) $. Also, since we want to find the remainder of 998244353, we need to put mod int in BIT instead of long long or int.
In addition, there seems to be a method of solving with $ O (NK) $ by the imos method, a method of reducing to a formal power series, and a method of solving with $ O (N \ log {N}) $ using a formal power series ( → maspy's article) But I'm not sure, so I'll skip this time.
D.cc
//Debugging options:-fsanitize=undefined,address
//Compiler optimization
#pragma GCC optimize("Ofast")
//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//macro
//for loop
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
//FORA is a range for statement(If it's hard to use, erase it)
#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 is a container such as 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:Congruence law
#define MAXR 100000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
/* BIT:RAQ compatible BIT
The initial value is a_1 = a_2 = ... = a_n = 0
・ Add(l,r,x): [l,r)Add x to
・ Sum(i): a_1 + a_2 + ... + a_Calculate i
All calculations are O(logn)
*/
template <typename T>
struct BIT {
int n; //Element count
vector<T> bit[2]; //Data storage location
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)Add to
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;
//constructor
modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
//Copy constructor
modint(const modint &r){val=r.val;}
//Arithmetic operator
modint operator -(){return modint(-val);} //unary
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;}
//Assignment operator
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;
}
//Equivalence comparison operator
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>;
//I / O stream
istream &operator >>(istream &is,mint& x){//Do not add const to x
ll t;is >> t;
x=t;
return (is);
}
ostream &operator <<(ostream &os,const mint& x){
return os<<x.val;
}
signed main(){
//Code for speeding up input
//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 problem
I feel that there was a backward compatibility issue the other day.
$ A_ {i + 1} = A_ {i} ^ 2 \ mod \ m $ and $ A \ 1 = x $, and find $ \ sum {i = 1} ^ nA_i $. At this time, $ n $ is $ 10 ^ 9 $ at the maximum, so you cannot find all the streets.
Here, since each term is the remainder of $ m $, there are only $ m $ streets at most **, and when $ (A \ _ i = A \ _j) \ mod \ m $ holds, $ (A \ Since _ {i + 1} = A \ _ {j + 1}) \ mod \ m $ holds, a loop with a maximum length of $ m $ appears in the ** sequence $ A $.
Therefore, if you can find this loop, you can calculate at high speed by considering how many times the loop appears from ** $ A \ _1 $ to $ A \ _n $ **. I think that if you know how to find a loop, you can implement it at high speed, so I will show you how to find a loop below.
① ** Find $ A \ _i $ where the remainder appears twice **
v… Array to store in the order in which the remainder appears
s… set to save the remainder that came out
Look at $ A \ _1, A \ _2,… $ in that order and store them in v and s. At this time, if $ A \ _i $ with the same value as stored in s appears, exit ① with that value saved.
② ** Separate the loop and the front of the loop **
The value saved in ① is not included in the loop before $ A \ _i $, which appears for the first time. Therefore, it is separated into this part (before the loop) and the part after $ A \ _i $ (loop).
If $ A \ _n $ is before the loop, the operation ends at this point and output is performed. If $ A \ _n $ is included in the loop, calculate before the loop, update $ n $ to the remaining number of terms, update v to be loop only, after doing three things Move on to ③.
③ ** Calculate the loop **
You can request the following information after ②.
l… Loop length
n… The length of the remaining sequence
$ [\ frac {n} {l}] t… Sum of the parts that do not go around the loop
Calculate the loop separated in (2). The above information is easy to find, so the answer is $ [\ 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)
#The beginning of the loop
#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
#Number of loops
tim=n//len(cand)
ama=n%len(cand)
ans+=tim*sum(cand)
ans+=sum(cand[:ama])
print(ans)
#print(p)
#print(cand)
F problem
It can be solved by using the interval addition BIT after C. In the following, I tried to explain in words as much as possible, but there are some parts that I haven't been able to convey, so I think that you will deepen your understanding by ** drawing a diagram and experimenting **.
When I first saw it, I misread it and overlooked the information ** closest **. Here, if we consider the problem using a diagram, it will be as follows.
Assuming that the operations are performed in the order of the circled numbers, the part indicated by the arrow can be painted in white. At this time, paying attention to (1), for example, the number of squares that can be painted when each line is selected is small. Similarly, if you pay attention to ②, you can reduce the number of squares that can be painted when each column is selected. As for (4), it is not possible to reduce the number of squares by (2), so any black square in that column can be made white. In other words, when you select a row (or column), you can see that there are operations that change the number of cells that can change the color of a column (or row) and operations that do not.
Here, after further experimentation, I will summarize it by saving the leftmost column ($ r
(✳︎)… If you think in the figure, if you selected $ (d, 1) $ in ①, any element of $ row $ will be replaced from $ n $ to $ d $. That is, just add $ d-n $ to any element. The same can be said for any operation.
F.cc
//Debugging options:-fsanitize=undefined,address
//Compiler optimization
#pragma GCC optimize("Ofast")
//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//macro
//for loop
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
//FORA is a range for statement(If it's hard to use, erase it)
#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 is a container such as 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:Congruence law
#define MAXR 100000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
/* BIT:RAQ compatible BIT
The initial value is a_1 = a_2 = ... = a_n = 0
・ Add(l,r,x): [l,r)Add x to
・ Sum(i): a_1 + a_2 + ... + a_Calculate i
All calculations are O(logn)
*/
template <typename T>
struct BIT {
int n; //Element count
vector<T> bit[2]; //Data storage location
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)Add to
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 for speeding up input
//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