競プロ参加日記014 Educational Codeforces Round 95
＿人人人人人人＿
＞ Unrated!! ＜
￣Y^Y^Y^Y^Y^￣
・はじめに
A,B,C,Dの4完で非常に調子が良かったのにunratedは悲しい...。
・A. Buying Torches
unratedの原因。
以下、問題の要素を抜粋
・始めに棒を1つもっている。
・以下の2パターンのトレードを複数回行える
- 1本の棒をxの棒と交換する
- y本の棒と1個の石炭を交換する
・1本の棒と1個の石炭から、1個のトーチを作る
k個のトーチを作る際に必要なトレード回数の最小を求めよ。
トーチをk本作るには、k本の棒とk個の石炭が必要。
k個の石炭にはyk本の棒が必要なので、棒は最終的にyk+k本必要になる。
なので、yk+k本手に入れるのに、必要な木のトレード回数と、石炭のトレード回数k回を足せばよい。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int t;
cin>>t;
for(int i=0;i<t;i++){
long long k,x,y;
cin>>x>>y>>k;
x--;
long long nw=k*y+k;
//cout<<nw<<endl;
long long c=(nw-1)/x+((nw-1)%x!=0);
//cout<<c<<endl;
c+=k;
cout<<c<<endl;
}
}※こういう問題、すごく苦手。数式というか、こういう数字を上手く整えるコツが分からないですね...。
・B. Negative Prefixes
(地味にrejudgeあった問題)
l[i]=0である要素a[i]を並び替えたとき、a[]の累積和p[]の値がマイナスとなる最大のindexをできるだけ小さくする。
大きい数字を貪欲に入れていけば、マイナスにならずにプラスのまま終われることがありそうだったり、何かと良さそうです(感覚)。
幾つか手元で試しても反例が出なかったので提出。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int t;
cin>>t;
for(int i=0;i<t;i++){
int n;
cin>>n;
int a[n];
int l[n];
vector<int> v;
for(int j=0;j<n;j++){
cin>>a[j];
}
for(int j=0;j<n;j++){
cin>>l[j];
if(l[j]==0){
v.push_back(a[j]);
}
}
sort(v.begin(),v.end());
int idx=(int)v.size()-1;
for(int j=0;j<n;j++){
if(l[j]==0){
a[j]=v[idx];
idx--;
}
}
for(int j=0;j<n;j++){
cout<<a[j];
if(j==n-1) cout<<endl;
else cout<<" ";
}
}
}・C. Mortal Kombat Tower
n個フロアがあり、友人->自分->友人...の順に、1つor2つ進めることができる。友人はa[i]=1であるフロアを進む際にコストが1必要である。nフロアを進むコストを最小化せよ。
dp[友人or自分][フロア]でコストが最小になるようdpすればいいです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int t;
cin>>t;
for(int i=0;i<t;i++){
int n;
cin>>n;
int a[n+5];
for(int j=0;j<n;j++){
cin>>a[j];
}
a[n]=0;
a[n+1]=0;
a[n+2]=0;
int dp[2][n+5];
for(int j=0;j<n+5;j++){
dp[0][j]=INT_MAX;
dp[1][j]=INT_MAX;
}
dp[0][0]=0;
for(int j=0;j<n;j++){
//0 friend
if(dp[0][j]!=INT_MAX){
int c1=a[j];
int c2=a[j+1];
dp[1][j+1]=min(dp[1][j+1],dp[0][j]+c1);
dp[1][j+2]=min(dp[1][j+2],dp[0][j]+c1+c2);
}
if(dp[1][j]!=INT_MAX){
dp[0][j+1]=min(dp[0][j+1],dp[1][j]);
dp[0][j+2]=min(dp[0][j+2],dp[1][j]);
}
}
cout<<min(dp[1][n],dp[0][n])<<endl;
}
}※はじめ、2回目進むかどうかを以下の貪欲を組んでWAしました。
・友人->a[i]=0ならすすむ
・自分->a[i]=1ならすすむ
サンプルは通るのですが、1 1 1 1 0 0 1 1みたいなケースで落ちます。
・D. Trash Problem
n個のゴミ山があって、それぞれ座標p[i]にある。
一回の操作で、座標p[i]にあるゴミ山を全て+1か-1動かすことができる。ゴミ山の塊を2つ以下にする場合、最小操作はいくつか。
また、q個のクエリが与えられ、ゴミ山がなくなったり増えたりするので、そのあとの最小操作数も求めよ。
クエリがない場合、各p[i]の差の和-各p[i]の差の最大となります。(一番距離の長いところは使わず、それ未満の距離でゴミを集めるのが最適)
クエリのせいでゴミ山のp[i]の差が変わりますが、1つ追加か1つ削除なので、ゴミ山の位置やp[i]の差をset等のlogN系データ構造で管理していけば、答えが求められます。
※以下コードですが、やばいほど汚いので注意
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int n,q;
cin>>n>>q;
multiset<int> s;
multiset<int> s2;
int sum=0;
int p[n];
for(int i=0;i<n;i++){
cin>>p[i];
}
sort(p,p+n);
for(int i=0;i<n;i++){
s2.insert(p[i]);
if(i>0){
s.insert(p[i]-p[i-1]);
sum+=p[i]-p[i-1];
}
}
if(s.size()==0) cout<<"0"<<endl;
else cout<<sum-*(s.rbegin())<<endl;
for(int i=0;i<q;i++){
/*auto it=s.begin();
while(it!=s.end()){
//cout<<*it<<" ";
it++;
}
//cout<<endl;
auto it2=s2.begin();
while(it2!=s2.end()){
//cout<<*it2<<" ";
it2++;
}
//cout<<endl;*/
int t,x;
cin>>t>>x;
if(t==1){
auto it=s2.upper_bound(x);
int iti=*it;
if(it==s2.begin()){
s.insert(iti-x);
sum+=iti-x;
s2.insert(x);
}
else if(it==s2.end()){
it--;
int iti2=*it;
s.insert(x-iti2);
sum+=x-iti2;
s2.insert(x);
}
else{
it--;
int iti2=*it;
if(!s.empty()) s.erase(s.find(iti-iti2));
sum-=iti-iti2;
s.insert(iti-x);
sum+=iti-x;
s.insert(x-iti2);
sum+=x-iti2;
s2.insert(x);
}
////cout<<*(s2.upper_bound(x))<<endl;;
}
else{
auto it=s2.find(x);
auto it2=s2.find(x);
auto it3=s2.find(x);
it3++;
if(it==s2.begin()){
it++;
int iti=*it;
//cout<<iti<<","<<x<<endl;
if(!s.empty()) s.erase(s.find(iti-x));
sum-=iti-x;
//cout<<"AAAA"<<endl;
if(!s2.empty()) s2.erase(it2);
}
else if(it3==s2.end()){
it--;
int iti=*it;
//cout<<iti<<","<<x<<endl;
if(!s.empty()) s.erase(s.find(x-iti));
sum-=x-iti;
if(!s2.empty()) s2.erase(it2);
}
else{
it--;
int iti=*it;
it++;
it++;
int iti2=*it;
//cout<<iti2<<","<<x<<","<<*(s.find(iti2-x))<<endl;
if(!s.empty()) s.erase(s.find(iti2-x));
sum-=iti2-x;
//cout<<*(s.find(x-iti))<<endl;
if(!s.empty()) s.erase(s.find(x-iti));
sum-=x-iti;
s.insert(iti2-iti);
sum+=iti2-iti;
if(!s2.empty()) s2.erase(x);
}
}
while(*(s.begin())<0) {
sum-=*(s.begin());
s.erase(s.begin());
}
if(s.size()==0) sum=0;
if(s.size()==1){
auto it=s.begin();
sum=*it;
}
if(s.size()==2){
auto it=s.begin();
auto it2=s.begin();
it2++;
sum=*it2+*it;
}
if(s.size()<=1) cout<<"0"<<endl;
else cout<<sum-*(s.rbegin())<<endl;
//cout<<"----------"<<sum<<endl;
}
}unratedと深夜のテンションで勢いで書いてたらコードが暴走した。
こんなコード業務で絶対書かないでね。レビュワーに刺されます。
・おわりに
Educationalのわりに何が教育的なんだろう？という感じですね。(いつものこどふぉと変わらない)
E～は気分が乗ったら解きます...。今は何より寝たいです...。
この記事が気に入ったらサポートをしてみませんか？