[PYTHON] Codeforces Round # 521 (Div. 3) Bacha Review (10/9)
This time's results
Impressions of this time
It was a problem that should be solved up to F1, but it made DP a bug. I had a basic policy, but I was wondering whether to fix the transition destination or the transition source **, or I made a mistake in the index **, so I regret it.
Problem A
It was a problem that I could see in ABC's C problem. If you look at one operation that goes forward with $ a $ and returns with $ b $, this operation is performed $ [\ frac {k} {2}] $ times. Also, in the case of $ k $, it will advance by $ a $ once more at the end, so you can find the above total.
A.py
for _ in range(int(input())):
a,b,k=map(int,input().split())
ans=(a-b)*(k//2)
if k%2==0:
print(ans)
else:
print(ans+a)
Problem B
Prevents the $ 101 $ string from appearing. For such problems, consider the ** greedy algorithm ** first.
For example, look at the characters that can be $ 101 $ from the left. That is, $ i $ = 1 ~ $ n-2 $ gives $ a [i-1: i + 2] = "101" $. At this time, it is necessary to change 1 on either side of 0 to 0, but since there is nothing on the left side that is already $ 101 $, it is best to change 1 on the right side to 0 **. Repeat this and count how many times you changed it to 0.
B.py
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(1,n-1):
if a[i-1]==1 and a[i]==0 and a[i+1]==1:
a[i+1]=0
ans+=1
print(ans)
C problem
The policy was immediate, but I embedded a bug in the mystery.
First, suppose you exclude ** $ a [j] $ ** (let's assume that the remaining sequence is $ b $). At this time, $ sum (a) -a [j] = 2 \ times b \ _ {max} $ should hold. You can also select $ b_ {max} $ other than $ a [j] $. Here, $ sum (a) $ is calculated in advance and $ a [j] $ is given, so when ** $ a [j] $ is given, $ b \ _ {max} $ is fast. Think about what you want from **. First, when there are two or more elements that become $ a \ _ {max} $, ** always $ b \ _ {max} = a \ _ {max} $ **, so for any $ j $, respectively. It can be judged by $ O (1) $. Next, if there is only one element that becomes $ a \ _ {max} $, ** save the second largest element **, and $ a [j] = a \ _ {max} $ Only when $ a [j] $ is excluded, $ b \ _ {max} = $ (the second largest element) should be set. At this time as well, the judgment can be made with $ O (1) $.
I was able to determine, but because I sorted when finding the largest element and the second element, ** the index I wanted was different from the subject **. Therefore, I tried to store the value that satisfies the subject in the previous judgment in $ set $ for the time being, and finally find the index of the element included in $ set $.
C.py
n=int(input())
b=list(map(int,input().split()))
a=sorted(b)
s=sum(a)
ans=set()
if a[-2]==a[-1]:
ma=a[-1]
for i in range(n):
if s-a[i]==2*ma:
ans.add(a[i])
else:
ma1,ma2=a[-1],a[-2]
for i in range(n):
if i==n-1 and s-a[i]==2*ma2:
ans.add(a[i])
if i!=n-1 and s-a[i]==2*ma1:
ans.add(a[i])
realans=[]
for i in range(n):
if b[i] in ans:
realans.append(str(i+1))
print(len(realans))
print(" ".join(realans))
D problem
I made a mistake in the implementation and was impatient.
I will cut it, but I do not consider the order, so I will manage how many each number comes out in the dictionary $ c $. At this time, if you do not know how many times to cut, you will not know how to include the element in $ t $. Therefore, let's assume that we cut only ** $ x $ times ** and proceed with the discussion. Here, if the number $ i $ in $ c $ is included only in $ c [i] $, then $ t $ contains $ i $ in only $ \ frac {c [i]} {x} $. Can be included. Therefore, if you check this for any $ i $ managed in the dictionary, you can find the longest $ t $ ** when cutting ** $ x $ times. Here, if the longest length of ** $ t $ is greater than or equal to $ k $, then ** the subject $ t $ can be constructed. Furthermore, by increasing the number of cuts , the length of $ t $ decreases monotonically ** so that it becomes (the longest length of $ t $ when cutting $ x $ times) $ \ geqq k $. I want to find the largest $ x $, so I will find it by binary search (✳︎). Also, you can output $ t [: k] $ when the obtained $ x $ ( elements must be output only $ k $ **, note that here 1WA ).
(✳︎)… The binary search is created by referring to this article. Note that the roles of ** $ l, r $ are reversed ** because we want to find the initial value of ** $ l, r $ ** and the maximum value this time.
D.py
n,k=map(int,input().split())
s=list(map(int,input().split()))
from collections import Counter
c=Counter(s)
z=dict()
def f(x):
global n,k,c,z
if x>n:return False
if x==0:return True
ret=0
z=dict()
for i in c:
ret+=c[i]//x
z[i]=c[i]//x
#print(x,ret)
return ret>=k
#l:True,r:False
l,r=0,10**6
while l+1<r:
y=l+(r-l)//2
if f(y):
l=y
else:
r=y
f(l)
#print(z)
ans=[]
for i in z:
for j in range(z[i]):
ans.append(str(i))
print(" ".join(ans[:k]))
E problem
It took a long time due to an implementation error in all of C, D, and E. I will devote myself. Also, TL seemed to be tough on this issue, and I made it in C ++, but it was a correct choice.
At first I misread the problem ** and noticed by looking at the sample. Since $ pairwise \ distinct $, each contest can only deal with questions on the same topic, and questions on a topic can only be included in one contest.
Therefore, count how many problems there are in each topic and record them in the map once. Also, ** topic numbers are not needed **, so only the number of problems is stored in the array $ a $ ($ a $ is sorted, why will be explained later).
** If the first number is not decided, the number after that will not be decided **, so let the first number be $ x $. Also, $ x $ is more than 1 and less than $ 2 \ times 10 ^ 5 $. At this time, the number of questions of $ x, 2x, 4x… $ is required to open each contest. Also, since the maximum number of questions for each topic is $ 10 ^ 5 $, the maximum number of days for the contest is about $ 20 $ days ** ($ \ because \ 10 ^ 5 \ <2 ^ {20} $). I noticed that there was. Furthermore, when opening a contest with $ y $ questions, it is self-evident that you can open as many contests as possible ** after that by choosing the topic ** with the smallest number of questions above ** $ y $ **. .. Therefore, if you sort $ a $ earlier, use $ lower $ \ _ $ bound $ for $ a $ to count in order whether there are topics with the number of problems $ x → 2x → 4x →… $. I can go. Also, if the return value of $ lower $ \ _ $ bound $ is $ end $, subsequent contests cannot be opened, so counting will end. In addition, ** you cannot select questions for contests that you have already selected **, so store the topics you have selected in a variable called $ nxt $.
According to the above policy, how many days the contest can be held at each $ x $ and how many questions are included can be calculated by $ O ((\ log {n}) ^ 2) $, so the total amount of calculation is $ O ( It becomes n (\ log {n}) ^ 2) $. In the case of PyPy, even $ O (n \ log {n}) $ is worrisome, so I wrote it in C ++ from the beginning.
E.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
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n;
map<ll,ll> b;
REP(i,n){
ll z;cin>>z;
b[z-1]++;
}
vector<ll> a;
FORA(i,b){
if(i.S!=0)a.PB(i.S);
}
sort(ALL(a));
//REP(i,SIZE(a))cout<<a[i]<<endl;
ll ans=0;
FOR(x,1,200000LL){
//Search from nxt or later
ll ans_sub=0;
ll y=x;
auto nxt=a.begin();
while(true){
if(nxt==a.end())break;
nxt=lower_bound(nxt,a.end(),y);
if(nxt==a.end())break;
nxt++;
ans_sub++;
y*=2;
}
ans=max(ans,x*(1LL<<ans_sub)-x);
}
cout<<ans<<endl;
}
F1 problem
(The question sentence was difficult to read.)
The moment you see it, you can see how it looks like DP. At this time, at least one element to be reposted in a row of $ k $ ($ \ leftrightarrow $ **) is less than $ k $ and the distance to the nearest element to the right (same for the left) of an element , The distance to the edge is $ k-1 $ or less **), so ** information on the last reposted element ** is required, and the number of finally reposted elements is $ x $. From this, I realized that I also need information on the number of elements ** $ repost $ **. Therefore, the following DP is set.
$ dp [i] [j] [l]: = $ (when the number of reposted elements up to the $ i $ th element is $ j $ and the last selected element is the $ l $ th element Maximum total of reposted elements)
Next, consider the transition. The value of $ dp $ is initialized with -1 (corresponding to -INF), and only $ dp [0] [1] [0] $ is set to $ a [0] $.
** Consider the transition with or without selecting that element **. Consider the transition destination depending on whether to select the $ i + 1 $ th element based on the transition source of $ dp [i] [j] [l] $. Also, the following is performed when $ dp [i] [j] [l]! =-1 $.
① When choosing that element
When $ i = $ 0 ~ $ k-2 $, you can select it regardless of the value of ** $ l $ **, so you can select it if $ j! = X $. When $ i = k-1 $ ~ $ n-2 $, it is necessary to be $ (i + 1) -l \ leqq k $ in addition to $ j! = X $.
In addition, when $ i = $ 0 ~ $ k-2 $, ** is required when selecting the $ i + 1 $ th element for the first time **
Should be done first.
② When you do not choose that element
If not selected, there is no condition, only $ i $ is incremented by +1.
Doing the above completes dp. Also, when seeking an answer, I would like to find the maximum $ dp [n-1] [x] [l] $ with any $ l $, but ** $ n-1-l \ leqq k \ leftrightarrow l Note that it must be \ geqq n-1-k $ **.
F1.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
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n,k,x;cin>>n>>k>>x;
vector<ll> a(n);REP(i,n)cin>>a[i];
if(k==1){
if(x!=n){
cout<<-1<<endl;
}else{
cout<<accumulate(ALL(a),0LL)<<endl;
}
return 0;
}
//Initialization for some reason
//If not-1
vector<vector<vector<ll>>> dp(n,vector<vector<ll>>(x+1,vector<ll>(n,-1)));
//Initialization(Do you choose i)
dp[0][1][0]=a[0];
REP(i,k-1){
//When choosing for the first time
dp[i+1][1][i+1]=a[i+1];
REP(j,x+1){
REP(l,n){
if(true){
if(dp[i][j][l]!=-1){
//When choosing
if(j!=x){
dp[i+1][j+1][i+1]=max(dp[i+1][j+1][i+1],dp[i][j][l]+a[i+1]);
}
//If you do not choose
dp[i+1][j][l]=max(dp[i+1][j][l],dp[i][j][l]);
}
}
}
}
}
//transition
FOR(i,k-1,n-2){
REP(j,x+1){
REP(l,n){
if(true){
if(dp[i][j][l]!=-1){
//When choosing
if(j!=x and (i+1)-l<=k){
dp[i+1][j+1][i+1]=max(dp[i+1][j+1][i+1],dp[i][j][l]+a[i+1]);
}
//If you do not choose
dp[i+1][j][l]=max(dp[i+1][j][l],dp[i][j][l]);
}
}
}
}
}
//Range here
ll ans=-1;
FOR(l,n-1-(k-1),n-1){
ans=max(ans,dp[n-1][x][l]);
}
cout<<ans<<endl;
}
F2 problem
I will skip this time.
Recommended Posts