競プロ参加日記009 Codeforces Round #667 (Div. 3)
ぬるからです。
https://codeforces.com/contest/1409
競プロの勉強にブーストをかけたい一心で、CodeForcesの方にも参加してみました。こちらにも、ちょくちょく顔を出すと思いますのでよろしくお願いします。
・初めに
A,B,C,Dの4完でした。
レートは603からのスタートです。
コンテスト後の解きなおしで、E,Fも解けたので概ね満足しています。
・A. Yet Another Two Integers Problem
Aに1～10加えてBにするための最小手順を求める問題。
10加えられるなら10加えるのが最も最善なのは明らかです。10加えて超過する場合、1～9のどれかでBと同値になるため、A/10に割り切れなかった場合の補正をすればOKです。
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<climits>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
int main(){
int N;
cin>>N;
for(int i=0;i<N;i++){
int a,b;
cin>>a>>b;
int sa=abs(a-b);
cout<<sa/10+(sa%10!=0)<<endl;
}
}※どうでもいい話ですが、#define int long longを外しました。(お行儀が悪すぎる)
・B. Minimum Product
a>=x,b>=yの範囲で、n回までaとbを減らしa*bを最小化する問題。
aを減らせばb分だけ減り、bを減らせばa分だけ減ります。なので、なるたけ小さい数字を減らした方が効率は良さそうです。
ただ、Test: #1にあるような
10 10 8 5 3 -> a==bでx,yが違う
10 11 9 1 10 -> a<bだけど、xが大きいためbを減らした方が最小になる
がややこしいです。z=xyのグラフを見た感じ、山のようになっているため、a,bを均等に減らすよりどっちかを一気に減らした方が最小になりそうなのは正しそうです(感覚ですが)。
場合分けを頑張れば解けそうですが、それも面倒なのでaを減らすパターンとbを減らすパターンでminを取りました。
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<climits>
/*
#include<boost/multiprecision/cpp_long long.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Blong long = mp::cpp_long long;
*/
using namespace std;
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
int main(){
long long t;
cin>>t;
for(long long i=0;i<t;i++){
long long a,b,x,y,n;
cin>>a>>b>>x>>y>>n;
long long m1=a-x;
long long m2=b-y;
long long ans1,ans2;
long long at=a,bt=b,nt=n;
at-=min(m1,nt);
nt-=min(m1,nt);
if(nt>0){
bt-=min(m2,nt);
}
ans1=at*bt;
at=a,bt=b,nt=n;
bt-=min(m2,nt);
nt-=min(m2,nt);
if(nt>0){
at-=min(m1,nt);
}
ans2=at*bt;
cout<<min(ans1,ans2)<<endl;
}
}・C. Yet Another Array Restoration
サイズNのx,yを含む等差数列の要素の最大を最小にする問題。
公差は小さいほうが良いので、x,yから公差のminを求めて、できるだけy以下に要素が集まるように設定すればよいです。
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<climits>
/*
#include<boost/multiprecision/cpp_long long.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Blong long = mp::cpp_long long;
*/
using namespace std;
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
int main(){
int t;
cin>>t;
for(int i=0;i<t;i++){
int n,x,y;
cin>>n>>x>>y;
int n2=n;
n-=1;
int sa=y-x;
if(n==1){
cout<<x<<" "<<y<<endl;
}
else{
int n3=0;
while(sa%n!=0) n--,n3++;
int w=sa/n;
while(n3!=0){
if(x-w<1) break;
n3--;
x-=w;
}
for(int j=0;j<n2;j++){
cout<<x+w*j;
if(j==n2-1) cout<<endl;
else cout<<" ";
}
}
}
}・D. Decrease the Sum of Digits
sにnを加えたとき、各桁の和がt以下になる最小のnを答える問題。
基本的に、nを加えるので各桁の和が増えますが9->0になるときだけ減ります。また、上位桁より、下位桁で減らすように仕向けた方が、nの桁数も減ってお得です。
纏めて、下位桁から0になるようにnを調整していけばよいです。
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<climits>
/*
#include<boost/multiprecision/cpp_long long.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Blong long = mp::cpp_long long;
*/
using namespace std;
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
int main(){
long long t;
cin>>t;
for(long long i=0;i<t;i++){
long long N;
long long s;
cin>>N>>s;
long long wa=0;
for(long long i=N;i>0;i/=10){
wa+=i%10;
}
string ans="";
long long dig=0;
int nn=0;
//cout<<"---"<<wa<<endl;
while(wa>s){
//cout<<",,,"<<nn<<","<<dig<<","<<ans<<","<<wa<<","<<N<<endl;
while(nn>0){
nn--;
ans="0"+ans;
}
if(N%10==0){
ans="0"+ans;
dig++;
N/=10;
continue;
}
//cout<<"....."<<(char)((10-N%10)+'0')<<","<<ans<<","<<wa<<","<<N<<endl;
ans=(char)((10-N%10)+'0')+ans;
// cout<<(char)((10-N%10)+'0')<<","<<ans<<","<<wa<<","<<N<<endl;
dig++;
wa-=N%10;
N/=10;
while(N%10==9){
wa-=9;
N/=10;
dig++;
nn++;
}
wa+=1;
N++;
// cout<<ans<<","<<wa<<","<<N<<endl;
}
if(ans=="") cout<<"0"<<endl;
else cout<<ans<<endl;
}
}非常に実装が重かったです...。
ansがlong longだとオーバーフローするっぽいのでstringにしたのですが、バグの嵐でやばかったです。
・E. Two Platforms
yはめっちゃ下にすれば関係ないので、この問題は範囲kを二つ決めて、その中にあるxの個数を最大化する問題となります。
各点から左に伸ばす場合と、右に伸ばす場合に何個他の点と重なるかを調べ(C++ならupper_boundなどの二分探索で調べる)、累積maxを取ります。
こうすることで、各点のx以下に範囲を決めたとき、x以上に範囲を決めたときの最大が分かるようになり、全点での最大を取れば答えが分かります。
注意点としては、左に伸びる範囲と右に伸びる範囲を同じxに置いた場合、その位置にある点が二重カウントされます。除外するようにしましょう。(わたしは、右に伸びるほうはxより大きい点から選ぶようにしました)
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<climits>
/*
#include<boost/multiprecision/cpp_long long.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Blong long = mp::cpp_long long;
*/
using namespace std;
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
int main(){
int t;
cin>>t;
for(int i=0;i<t;i++){
int n,k;
cin>>n>>k;
vector<int> v,vl,vr;
for(int i=0;i<n;i++){
int x;
cin>>x;
v.push_back(x);
vl.push_back(0);
vr.push_back(0);
}
for(int i=0;i<n;i++){
int y;
cin>>y;
}
sort(v.begin(),v.end());
int ans=0;
for(int i=0;i<(int)v.size();i++){
//cout<<"///"<<v[i]<<endl;
auto a=upper_bound(v.begin(),v.end(),v[i]-k-1);
auto b=upper_bound(v.begin(),v.end(),v[i]);
vl[i]=b-a;
auto c=upper_bound(v.begin(),v.end(),v[i]-1);
auto d=upper_bound(v.begin(),v.end(),v[i]+k);
//cout<<v[i]<<","<<*a<<","<<*b<<","<<*c<<","<<*d<<endl;
vr[i]=d-c;
}
for(int i=1;i<(int)v.size();i++){
vl[i]=max(vl[i],vl[i-1]);
}
for(int i=v.size()-2;i>=0;i--){
vr[i]=max(vr[i],vr[i+1]);
}
ans=vl[0];
for(int i=0;i<(int)vl.size();i++){
//cout<<vl[i]<<","<<vr[i+1]<<endl;
int l=vl[i];
int ln=v[i];
auto rn=upper_bound(v.begin(),v.end(),ln);
int r=0;
if(rn!=v.end()){
r=vr[rn-v.begin()];
}
ans=max(ans,l+r);
}
cout<<ans<<endl;
}
}左からと右からのmaxを取る感じ、何か典型っぽい匂いがします。
忘れないようにします...。
F. Subsequences of Length Two
sをn文字変え、そのsから任意文字削除してtを作る際に、削除するパターンを最大化する問題。
制約も弱いのでdpすれば行けそうですね。
t[0]の出現回数、文字を変えた回数を状態としてもち、パターン数をmaxとなるように更新していけばよいです。
dpの更新の際、s[i]が既にt[0]かt[1]である可能性があるため、そういった場合は別途処理が必要です。(例えばt[0]である場合は、s[i]を更新しないパターンでもt[0]の出現回数を増やす必要があります。)
t[0]=t[1]の場合も注意です。dpの更新に組み込むのも面倒なので、sを可能な限りt[0]=t[1]に変えた際のパターン数を別途求めるようにしました。
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<climits>
/*
#include<boost/multiprecision/cpp_long long.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Blong long = mp::cpp_long long;
*/
using namespace std;
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
#define MAX 201
int main(){
int n,k;
cin>>n>>k;
string s,t;
cin>>s>>t;
if(t[0]==t[1]){
int c1=0;
int c2=0;
for(int i=0;i<(int)s.size();i++){
if(s[i]==t[0]) c1++;
else if(k-->0) c2++;
}
int c=c1+c2;
int ans=0;
c--;
while(c>0){
ans+=c;
c--;
}
cout<<ans<<endl;
return 0;
}
int dp[MAX][MAX][MAX];
for(int i=0;i<MAX;i++){
for(int j=0;j<MAX;j++){
for(int k=0;k<MAX;k++){
dp[i][j][k]=-1;
}
}
}
dp[0][0][k]=0;
for(int i=0;i<(int)s.size();i++){
for(int j=0;j<MAX;j++){
for(int l=0;l<MAX;l++){
if(dp[i][j][l]!=-1){
int x=0;
if(s[i]==t[1]) x=1;
int y=0;
if(s[i]==t[0]) y=1;
//cout<<"pat1---"<<s[i]<<","<<i<<","<<j<<","<<l<<","<<x<<","<<y<<","<<dp[i][j][l]<<endl;
dp[i+1][j+y][l]=max(dp[i][j][l]+j*x,dp[i+1][j+y][l]);
if(l!=0){
if(y==0) dp[i+1][j+1][l-1]=max(dp[i][j][l],dp[i+1][j+1][l-1]);
if(x==0) dp[i+1][j][l-1]=max(dp[i][j][l]+j,dp[i+1][j][l-1]);
}
}
}
}
}
int ans=0;
for(int i=0;i<MAX;i++){
for(int j=0;j<MAX;j++){
for(int k=0;k<MAX;k++){
if(dp[i][j][k]!=-1){
ans=max(ans,dp[i][j][k]);
}
}
}
}
cout<<ans<<endl;
}コンテスト後に解きましたが、解法も実装も個人的に楽に感じたので、Eを捨ててFやれば5完いけてましたね...。
・おわりに
始めての参加でしたが、個人的にatcoderより問題が好きです。
今回だけかもしれませんが、ガリガリ書けばOKみたいな問題が多いので個人的に好きです。
(Atcoderはたまに、数学ガチの問題が出ると冷えるので嫌いです。
前のアカウントではABC130-Cにやられました。)
この記事が気に入ったらサポートをしてみませんか？