[PYTHON] Tokio Marine & Nichido Programming Contest 2020 Review
This time's results
The performance was around 1270.
Impressions of this time
The next day's ABC was too bad and I took everything, but I thought I could fight a little more this time as well. However, as a result, I was able to solve the problems of yellow diff and orange diff in the review, so I think it was good. High difficulty can be achieved if you take your time calmly (about 3 hours), so I would like to make an effort to increase this speed little by little. The performance is not good, but it was a time when I felt like I could fight. These times have been going on lately so I can finish solving during the contest
Problem A
Outputs three characters from the front.
A.py
s=input()
print(s[:3])
Problem B
I kept bugging this issue and the performance dropped by about 200. It's too dregs. You should think about the relative speed between A chasing and B running away. I hate myself because of this. I want to keep my normal spirit even during the contest.
B.py
a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())
if a<b and v<=w:
print("NO")
elif a>b and v<=w:
print("NO")
elif a<b:
if -((a-b)//(v-w))<=t:
print("YES")
else:
print("NO")
else:
if -((-a+b)//(v-w))<=t:
print("YES")
else:
print("NO")
C problem
I tried to use a delayed segment tree (which I have never implemented) just because I saw it as an interval update. ** The problem cannot be solved by relying on data structures and algorithms **. It's no good at all.
As you can see by reading the problem statement, each operation ** expands the section that the light bulb can illuminate **. Also, the light intensity of a light bulb is the number of light bulbs that illuminate the light bulb during operation. Now, given the bulb strength $ B_1, B_2,…, B_N $ for each operation, the $ i $ th bulb illuminates the $ i-B_i $ to $ i + B_i $ th bulb. In other words, if you repeat checking the light bulbs illuminated by each light bulb (preparing an array of length N with $ 0 $ as the initial value and $ + 1 $ for all the light bulbs in the illuminated section), you can do it once. The operation can be performed with $ O (N ^ 2) $. Also, ** it is inefficient to add $ + 1 $ to all illuminated intervals, and the complexity can be reduced to $ O (N) $ by using the imos method **.
At first glance, the amount of calculation seems to be $ O (NK) $, but when I experimented, I noticed that it can be completed in about $ \ log {N} $ times instead of $ K $ times. As an image, the decisive factor was that ** the minimum light intensity doubled ** as shown in the figure below. ** Even if you are worried about your thoughts, you can easily check if it will be TLE if you make the maximum case and check it **.
From the above, since it is $ O (N \ log {N}) $, you can write a program within the time limit.
C.py
from itertools import accumulate
n,k=map(int,input().split())
a=list(map(int,input().split()))
for _ in range(k):
b=[0]*n
for i in range(n):
b[max(0,i-a[i])]+=1
if i+a[i]+1<n:
b[i+a[i]+1]-=1
a=list(accumulate(b))
if a==[n]*n:
break
print(" ".join(map(str,a)))
D problem
First of all, there is no doubt from the problem that it would be better to formulate a policy based on the ** knapsack problem with a limited number **.
Under this premise, items can be selected from the ancestors of a certain vertex and those in the vertex itself, so if you select items in order from the root to the child vertex (** top down **), it is normal. You can think of it like a knapsack problem. In this case, ** the calculation in the query can be avoided **, so it will be $ O (NW_ {max}) $ in the precalculation by DP and $ O (Q) $ in the calculation of the query, but $ NW_ { Since max} $ is up to $ 2 ^ {18} \ times 10 ^ 5 $, this policy cannot make the calculation in time. (1)
On the other hand, considering that the calculation is performed in the query, it is sufficient to select the items in order from the given vertex to the parent vertex (** bottom-up **), so consider a knapsack problem similar to the previous one. For example, it will be $ O (Q W_ {max}) $ in the calculation of the query by DP. However, $ Q W_ {max} $ can be up to $ 10 ^ 5 \ times 10 ^ 5 $, so even this policy cannot make the calculation in time. (2)
However, since both (1) and (2) are about $ 10 ^ {10} $, it is considered that the basic policy is not wrong, and ** perform the pre-calculation well and perform the query calculation efficiently **. think.
First, in the calculation before (1), if DP is performed at all $ N $ vertices, it will not be in time, so it is assumed that DP is performed at $ K $ vertices. At this time, the amount of calculation of DP is $ O (KW_ {max} \ log {N}) $ and $ W_ {max} $ is $ 10 ^ 5 $ at the maximum, so $ K $ is about $ 10 ^ 3 $ at the maximum. If so, the pre-calculation can be performed within the time limit.
Here, we can see that the query calculation selects items in order from the given vertex to the parent vertex, so items with vertices closer to the root ** are more likely to be selected repeatedly . Therefore, you can calculate the query faster by selecting ** $ K $ vertices from the vertices close to the root ** ( The common part can be calculated in advance to improve efficiency !! * *). Also, since it is $ K \ simeq2 ^ {10} -1 $, it can be assumed that the pre-calculation by DP has been completed up to the apex of the depth of $ 9 $. Furthermore, since the maximum depth of vertices is $ 17 $ from $ N <2 ^ {18} $, we can see that we only need to calculate for items that are on up to $ 8 $ of depth from $ 10 $ to $ 17 $. ..
Therefore, consider maximizing the value when choosing from the items at the top of $ L $ with $ L = 8 $. Here, if DP is used, the query processing will be $ O (QLW_ {max}) $ and it will not be in time, but ** If you enumerate all, it will be $ O (Q2 ^ L) $, so ** $ Q2 ^ L \ simeq10 ^ 7 From $, you can also process the query in time. (Remember that the basis of the ** knapsack problem is a complete enumeration ** !!)
Also, it seems that the problem that ** enumerates all in time but enumerates only half in time and summarizes later is called half all enumeration **. Next, I want to be able to solve similar problems. If you know this, the idea is that ** the method of enumerating all in a query is $ O (QN) $, and the amount of calculation can be reduced to $ O (Q \ sqrt {N}) $ in a half full enumeration **. I think I could do it.
Also, since access to the array created by DP after enumerating half of it in the query must be $ O (1) $, the array created by DP must be ** the largest item with a weight of W or less. It is also important to note that the value ** needs to be stored, and the cumulative maximum value must be calculated after the value of the largest item with a weight W of normal DP.
The above is implemented and it becomes as follows, but the implementation is poor and it can not be passed with Python and PyPy, but it can be passed with C ++. I hope the implementation will get better and better.
D.cc
//Include(Alphabetical order)
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array
using namespace std;
typedef long long ll;
//macro
//for loop relationship
//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.
#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 is a container such as vector
#define ALL(x) (x).begin(),(x).end() //I want to omit arguments such as sort
#define SIZE(x) ((ll)(x).size()) //size to size_Change from t to ll
#define MAX(x) *max_element(ALL(x)) //Find the maximum value
#define MIN(x) *min_element(ALL(x)) //Find the minimum value
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array(Used for prime number enumeration etc.)
//Abbreviation
#define PB push_back //Insert into vector
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
ll n;vector<pair<ll,ll>> vw;vector<vector<ll>> dp;
ll c1,c2;
void dfs(ll i){
if(i==1){
dp[i-1][vw[i-1].S]=vw[i-1].F;
}else{
ll j=i/2;
FORD(k,c2,0){
if(dp[j-1][k]!=0 or k==0){
ll ne=k+vw[i-1].S;
if(ne<=c2)dp[i-1][ne]=max(dp[j-1][k]+vw[i-1].F,dp[i-1][ne]);
}
dp[i-1][k]=dp[j-1][k];
}
}
if(i*2<=c1 and i*2<=n)dfs(i*2);
if(i*2+1<=c1 and i*2+1<=n)dfs(i*2+1);
}
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
cin>>n;
vw.resize(n);
REP(i,n)cin>>vw[i].F>>vw[i].S;
c1=1<<10;c2=100000;
dp.resize(c1);REP(i,c1)dp[i].resize(c2+1);
dfs(1);//cout << 1 << endl;
REP(i,c1)REP(j,c2)dp[i][j+1]=max(dp[i][j],dp[i][j+1]);
ll q;cin>>q;
REP(i,q){
ll v,l;cin>>v>>l;
vector<ll> cand;
while(v>c1){
cand.PB(v);
v=v/2;
}
ll r=SIZE(cand);//cout << r << endl;
ll ans=0;
REP(j,1<<r){
ll v_sub=0;ll w_sub=0;
REP(k,r){
if((j>>k)&1){
v_sub+=vw[cand[k]-1].first;
w_sub+=vw[cand[k]-1].second;
}
}
if(w_sub<=l)ans=max(ans,dp[v-1][l-w_sub]+v_sub);
}
cout<<ans<<endl;
}
}
D_TLE_py
n=int(input())
vw=[list(map(int,input().split())) for i in range(n)]
#vmax=max(i[0] for i in vw)
#Prepare DP for pre-calculation
#1~2^Calculate up to 10 first
dp=[[0]*(10**5+1) for i in range(2**10)]
#Pre-calculation
def dfs(i):
global n,vw,dp
j=i//2
for k in range(10**5,-1,-1):
if dp[j-1][k]!=0 or k==0:
if k+vw[i-1][1]<=10**5:
dp[i-1][k+vw[i-1][1]]=max(dp[j-1][k]+vw[i-1][0],dp[i-1][k+vw[i-1][1]])
dp[i-1][k]=max(dp[j-1][k],dp[i-1][k])
if i*2<=2**10 and i*2<=n:
dfs(i*2)
if i*2+1<=2**10 and i*2+1<=n:
dfs(i*2+1)
dfs(1)
for i in range(2**10):
for j in range(10**5):
dp[i][j+1]=max(dp[i][j],dp[i][j+1])
q=int(input())
for i in range(q):
#Follow each subtree
#Explore the rest here
v,l=map(int,input().split())
cand=[]
while v>2**10:
cand.append(v//2)
v=v//2
r=len(cand)
ans=0
for j in range(2**r):
v_sub=0
w_sub=0
for k in range(r):
v_sub+=vw[cand[k]-1][0]*(j>>k)&1
w_sub+=vw[cand[k]-1][1]*(j>>k)&1
if w_sub>l:
continue
else:
ans=max(ans,dp[v-1][l-w_sub]+v_sub)
print(ans)
E problem
The F problem has not been solved yet (it will take some time to solve it), so this is the last problem to be explained in this article.
At first glance, I knew that it was an inclusion-exclusion principle, but I didn't feel like I could make it in time for my implementation, so I couldn't solve it. However, I found that I could pass it through if I calculated it later, and it was the same method as the other answer, so I would like to review it by the end of today **.
In the following, the number of DPs with a limited number is set as ** DP [i] [s, t] = (the number of methods in which the logical product is s and the logical sum is t when i numbers are selected) **. It was implemented, and if it was implemented correctly, it could be forced through. It is not a general method because I think that it will not be in time for the calculation amount, but ** In the case of DP of two dimensions or more, it can be speeded up by using map **, ** In unordeed_map, pair may be used as a key I learned three things: it is undefined **, ** there is a limit on the number of DP, and if you decide from the back side of the array prepared by DP, you do not need an array for temporary storage and you can speed up **.
E.cc
//Include(Alphabetical order)
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array
using namespace std;
typedef long long ll;
//macro
//for loop relationship
//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.
#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 is a container such as vector
#define ALL(x) (x).begin(),(x).end() //I want to omit arguments such as sort
#define SIZE(x) ((ll)(x).size()) //size to size_Change from t to ll
#define MAX(x) *max_element(ALL(x)) //Find the maximum value
#define MIN(x) *min_element(ALL(x)) //Find the minimum value
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array(Used for prime number enumeration etc.)
//Abbreviation
#define PB push_back //Insert into vector
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
signed main(){
//Code for speeding up input
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n,k,s,t;cin >> n >> k >> s >> t;
vector<ll> b(n);REP(i,n)cin >> b[i];
vector<ll> a;
REP(i,n){
bool f=true;
REP(j,18){
if((s>>j)&1 and !((b[i]>>j)&1)){
f=false;break;
}
if(!((t>>j)&1) and (b[i]>>j)&1){
f=false;break;
}
}
if(f)a.PB(b[i]);
}
n=SIZE(a);
k=min(n,k);
//cout << n << endl;
//cout << n << endl;
//unordered_map cannot use pair as a key
//dp_It is slow to prepare sub(It changes several times just by not preparing)
//OK if you do it in reverse order
vector<map<pair<ll,ll>,ll>> dp(k);
REP(i,n){
FORD(j,k-2,0){
for(auto l=dp[j].begin();l!=dp[j].end();l++){
dp[j+1][MP((l->F.F)&a[i],(l->F.S)|a[i])]+=(l->S);
}
}
dp[0][MP(a[i],a[i])]=1;
}
ll ans=0;
REP(i,k)ans+=(dp[i][MP(s,t)]);
cout << ans << endl;
}
F problem
I am satisfied with solving up to E, so I will omit it this time.
Recommended Posts