Codeforces Round # 657 (Div. 2) Review
This time's results
Impressions of this time
I joined codeforces for the first time in 2 months. A I was prepared for a cold weather because I couldn't solve the problem for a long time, but for some reason it got quite warm. It may have come to the ground.
Anyway, the color changed after a long time, so I think it was a good experience. I will do my best to aim for AtCoder: Blue, Coderforces: Purple.
Problem A
I was placed in the A problem, so I lost my composure and couldn't solve it. In principle, nothing is difficult ...
It is not so difficult because the amount of calculation of $ O (t \ times n ^ 2) $ is allowed. First, check which part of the string "abacaba" (hereinafter referred to as the string S) is likely to appear. If the character string S appears more than once when checked, "No" is output, and if the character string S appears only once, change "?" To "d ~ z" and output. It's fine. In other cases, we will check if there is something that can be a character string S by changing the "?", Which creates only one ** character string S **.
Also, if you separate the check of the substring that can be the string S and whether there is only one ** string S **, the implementation will be easy to understand.
A.py
#Check where abaca can do
#Strange
#Index mistakes ...
a=["a","b","a","c","a","b","a"]
t=int(input())
for _ in range(t):
n=int(input())
s=list(input())
check=[0]*(n-6)
for i in range(n-6):
for j in range(i,i+7):
if s[j]!=a[j-i] and s[j]!="?":
break
else:
if s[i:i+7]==a:
check[i]=2
else:
check[i]=1
if check.count(2)>1:
print("No")
continue
elif check.count(2)==1:
print("Yes")
print(("".join(s)).replace("?","z"))
continue
#?Change and only one pattern
g=False
for i in range(n-6):
if check[i]==1:
f=False
cand=[a[j-i] if i<=j<=i+6 else s[j] if s[j]!="?" else "z" for j in range(n)]
for j in range(n-6):
if i!=j:
for k in range(j,j+7):
if cand[k]!=a[k-j]:
break
else:
f=True
if not f:
print("Yes")
print("".join(cand))
g=True
break
if not g:print("No")
Problem B
First, consider the range that can be expressed by $ a, b, c $. Since this is more than $ l $ and less than $ r $, we will apply each to the given formula. Then, it becomes as follows.
Based on this, consider fixing one of ① and ②. ** ② is continuous and easy to think **, so consider fixing ①.
Then, ① is optimally close to m, so it becomes $ ceil (\ frac {m} {a}) \ times a $ or $ floor (\ frac {m} {a}) \ times a $.
Therefore, if the difference between this value and the absolute value of $ m $ is $ r-l $, then $ b, c $ also exist and the answer is.
You can search for this for any $ a $ and find the answer.
Also, the amount of calculation is $ O (t \ times (r-l)) $, and it is written in the question sentence that the answer is always obtained, so write the code as follows.
B.py
t=int(input())
for _ in range(t):
l,r,m=map(int,input().split())
f=False
for a in range(l,r+1):
n1,n2=m//a,-((-m)//a)
if l-r<=m-n1*a<=r-l:
for c in range(l,r+1):
b=m-n1*a+c
if l<=b<=r:
if m+c-b!=0:
print(a,b,c)
f=True
break
if f:break
if l-r<=m-n2*a<=r-l:
for c in range(l,r+1):
b=m-n2*a+c
if l<=b<=r:
if m+c-b!=0:
print(a,b,c)
f=True
break
if f:break
C problem
I don't think the policy is difficult, but is it just barely in Python? ?? I'm scared, so I used C ++.
I can't try everything because $ n $ is big. However, after a certain number of trials, you only need to ** select some $ b_i $ **. I thought it would be best to take the maximum $ b_i $, but the sample didn't fit. If you think about it carefully, you need to select $ a_i $ when you select ** $ b_i $ **, and depending on the value, it is not optimal to take the maximum $ b_i
Also, when ** $ b_i $ is not taken **, $ n \ leqq m $ holds, and in this case, you can select $ n $ from the larger of $ a $. Also, $ a_i $ must be arranged in ascending order, but since $ a_i $ corresponding to ** $ b_i $ will be needed later **, prepare an array $ c $ in which $ a_i $ is arranged in ascending order. To do.
Here, when selecting $ b_i $, the ones larger than $ b_i $ in $ a $ are also the best for maximizing the sum, and the array $ c $ is more than the element searched for in upper_bound. All you have to do is select. At this time, it is inefficient to calculate the sum of these elements each time, so it is calculated by the cumulative sum **.
Also, you need to select $ a_i $ at the same time as $ b_i $, and ** $ a_i $ will be classified according to whether it was selected earlier. You can repeat the above and find the maximum answer.
C.cc
//For compiler optimization
#pragma GCC optimize("Ofast")
//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
//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
#define Umap unordered_map
#define Uset unordered_set
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll t;cin>>t;
while(t--){
ll n,m;cin>>n>>m;
vector<ll> a(m);
vector<ll> b(m);
vector<ll> c(m);
REP(i,m){cin>>a[i]>>b[i];c[i]=a[i];}
//Sorted guy in a
sort(ALL(c));
//Find the cumulative sum of c(From the opposite direction)
vector<ll> d(m+1);d[m]=0;
REPD(i,m)d[i]=c[i]+d[i+1];
ll ans=0;
//When choosing only a
if(n<=m)ans=max(ans,d[m-n]);
//Which b element to choose
REP(i,m){
auto as=upper_bound(ALL(c),b[i]);
ll anum=distance(c.begin(),as);
if(a[i]>b[i] and m-anum<=n)ans=max(d[anum]+b[i]*(n-(m-anum)),ans);
if(a[i]<=b[i] and m-anum<=n-1)ans=max(d[anum]+b[i]*(n-(m-anum)-1)+a[i],ans);
}
cout<<ans<<endl;
}
}
After D problem
I will skip this time
Recommended Posts