Educational Codeforces Round 93 Bacha Review (8/17)
This time's results
Impressions of this time
I still feel that the place where D cannot pass is not stable. I got stuck trying to do it with a non-assumed solution. Even if you try to go crazy, ** make sure you have a good perspective before implementing it **.
Problem A
I almost misread the problem. The problem is to answer a set of three numbers that do not form a triangle, and since the sequence $ a $ has been sorted in ascending order, $ a \ _i + a \ _j <a \ _k (i <j <k) $ Make sure it exists. This can be done by considering making $ a \ _i + a \ _j $ smaller and $ a \ _k $ larger, so make sure that $ (i, j, k) = (1,2, n) $ holds. All you have to do is.
A.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
if a[0]+a[1]<=a[-1]:
print(f"1 2 {n}")
else:
print(-1)
Problem B
It seemed difficult for a moment, but it was easy.
Both aim to maximize the number of 1s to choose, so ** alternate from the longest continuous subsequence of 1s **. Therefore, the length of the continuous subsequence of 1 contained in the string $ S $ is stored in ʻansand then sorted in descending order of values, and the sum of the odd-numbered ones is the maximum value of Alice's score. It's very convenient in Python because you can write with just ʻans [:: 2]to choose to skip two.
B.py
for _ in range(int(input())):
s=input()
n=len(s)
ans=[0]
for i in range(n):
if s[i]=="1":
ans[-1]+=1
else:
if ans[-1]!=0:
ans.append(0)
ans.sort(reverse=True)
print(sum(ans[::2]))
C problem
I suspected DP because it was easy to handle as a transition of addition, but it is difficult ** because I can't manage the state ** (as a result, the D problem was DP. I'm disappointed).
Here, we deal with ** intervals, so we decided to consider the difference in cumulative sum **. Therefore, the sum up to the $ x $ th is set as $ S \ _x $. At this time, the condition of the subject is $ S \ _r- S \ _ {l-1} = r-l + 1 \ leftrightarrow S \ _ r-r = S \ _ {l-1}-(l-1) $ I will. Therefore, if $ S \ _0-0 = 0 $, then any $ i (0 \ leqq i \ leqq n) $ with the same $ S \ _i-i $ will be paired. Therefore, this is divided into the same ones using a dictionary such as Counter, and when there are $ l $ $ i $ such that $ S \ _i-i = k $, $ \ _l C \ _2 $ Is the number of combinations of those $ i $. Do this calculation for each $ k $, and the sum is the answer.
AtCoder also seems to have come out recently, so I was able to solve it at high speed. Probably it took about 30 minutes a month ago, so I felt the importance and growth of devotion.
C.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
if a==[i+1 for i in range(n)]:
print(0)
continue
#Excluding the edges
for i in range(n):
if a[i]!=i+1:
break
for j in range(n-1,-1,-1):
if a[j]!=j+1:
break
#Index error
for k in range(i,j+1):
if a[k]==k+1:
print(2)
break
else:
print(1)
D problem
** I felt that a gap in one consideration makes a big difference **. I would like to consider with higher accuracy.
The first policy that you can easily come up with is ** to greedily combine the ones with the largest values **. In other words, the pairs of edges of $ r, g, and b $ are put into priority \ _queue in the order of longest, and the pairs are made from the longest one. However, if this method is used, ** only one color side will be left over . What should I do in this case? The first method is to retrofit the extra sides. However, since the greedy algorithm is used ( I decide the order of selection arbitrarily **), there is a possibility that the greedy algorithm will be broken by ** retrofitting **. I thought I wouldn't break it, but I couldn't implement it because I was about to step on the corner case. In this way, ** it is difficult to think to some extent, and if other policies can be established, you should consider another method **.
Here, the above-mentioned greedy algorithm has a considerable ** margin for execution time **, so you can think of it without being particular about the greedy algorithm. The next method I can think of is DP. In addition to considering the ** transition to choose **, $ r, g, b $ is at most 200, so there are only ** states ** of about $ R \ times G \ times B = 8 \ times 10 ^ 6 $. From that point of view, it seems that DP is a very effective means.
The DP considered here is as follows. Also, since it is best to select $ r, g, and b $ from the largest ones, we will proceed with the discussion assuming that they are sorted in descending order.
$ dp [i] [j] [k]: = $ ($ i $ pieces of $ r $, $ j $ pieces of $ g $, $ k $ pieces of $ b $, the largest rectangle when paired Total area)
Furthermore, in a normal transition, we will consider adding elements one by one, but this time we can make a rectangle by making a pair, so we will consider a transition that adds ** pairs **. So it looks like this:
(1) When $ i <R $ and $ j <G $
You can choose a pair from $ r $ and $ g $, so choose the largest $ r [i] $ and $ g [j] $ you can choose ($ i, j $ are 0-indexed). Please note that.).
(2) When $ i <R $ and $ k <B $
You can choose a pair from $ r $ and $ b $, so choose the largest $ r [i] $ and $ b [k] $ you can choose ($ i, k $ are 0-indexed). Please note that.).
(3) When $ j <G $ and $ k <B $
You can choose a pair from $ g $ and $ b $, so choose the largest $ g [j] $ and $ b [k] $ you can choose ($ j, k $ are 0-indexed). Please note that.).
(4) At other times Since there is nothing to choose as a group, the following are the answers. [1] When $ i <R $, $ dp [i + 1] [j] [k] = max (dp [i + 1] [j] [k], dp [i] [j] [k] ) $ [2] When $ j <G $, $ dp [i] [j + 1] [k] = max (dp [i] [j + 1] [k], dp [i] [j] [k] ) $ [3] When $ k <B $, $ dp [i] [j] [k + 1] = max (dp [i] [j] [k + 1], dp [i] [j] [k] ) $
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 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 R,G,B;cin>>R>>G>>B;
vector<ll> r(R);REP(i,R)cin>>r[i];sort(ALL(r),greater<ll>());
vector<ll> g(G);REP(i,G)cin>>g[i];sort(ALL(g),greater<ll>());
vector<ll> b(B);REP(i,B)cin>>b[i];sort(ALL(b),greater<ll>());
vector<vector<vector<ll>>> dp(R+1,vector<vector<ll>>(G+1,vector<ll>(B+1,0)));
REP(i,R+1){
REP(j,G+1){
REP(k,B+1){
//DP to choose and distribute for each pair
//It's easy if you think of it
//dp[i][j][k]:=When the i-th j-th and k-th are paired
bool f=false;
if(i<R and j<G){
dp[i+1][j+1][k]=max(dp[i+1][j+1][k],dp[i][j][k]+r[i]*g[j]);
f=true;
}
if(i<R and k<B){
dp[i+1][j][k+1]=max(dp[i+1][j][k+1],dp[i][j][k]+r[i]*b[k]);
f=true;
}
if(j<G and k<B){
dp[i][j+1][k+1]=max(dp[i][j+1][k+1],dp[i][j][k]+g[j]*b[k]);
f=true;
}
if(!f){
if(i<R)dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]);
if(j<G)dp[i][j+1][k]=max(dp[i][j+1][k],dp[i][j][k]);
if(k<B)dp[i][j][k+1]=max(dp[i][j][k+1],dp[i][j][k]);
}
}
}
}
cout<<dp[R][G][B]<<endl;
}
After the E problem
I will skip this time
Recommended Posts