beet's soil

競プロのことなど

AtCoder Regular Contest 073

1977 -> 2022 (+45) highest!! 念願のyellow

【C - Sentou】

押してからT秒間お湯が出るシャワーがある。N回ボタンを押した時間が与えられるので、
お湯が出ている時間の総和を求める。

一個後の時間までがTより短ければその時間、そうでなければTを答えに足していけばいい。
O(N).

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n,t;
  cin>>n>>t;
  int a[n];
  for(int i=0;i<n;i++) cin>>a[i];
  int ans=0;
  for(int i=0;i<n-1;i++){
    if(a[i+1]>=a[i]+t) ans+=t;
    else ans+=a[i+1]-a[i];
  }
  ans+=t;
  cout<<ans<<endl;
  return 0;
}
【D - Simple Knapsack】

よくあるナップザック。重さW以下で価値を最大化する。

あからさまな制約があるので頑張ってDPする。
O(N^3).

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[111][111][333];
signed main(){
  int n,w;
  cin>>n>>w;
  int a[n],b[n];
  for(int i=0;i<n;i++) cin>>a[i]>>b[i];
  int t=a[0];
  //cout<<n<<" "<<w<<" "<<t<<endl;
  for(int i=0;i<n;i++) a[i]-=t;
  memset(dp,-1,sizeof(dp));
  dp[0][0][0]=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<111;j++){
      for(int k=0;k<333;k++){
	if(dp[i][j][k]<0) continue;
	dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]);
	if(k+a[i]<333)
	  dp[i+1][j+1][k+a[i]]=max(dp[i+1][j+1][k+a[i]],dp[i][j][k]+b[i]);
      }
    }
  }
  int ans=0;
  for(int j=0;j<111;j++){
    for(int k=0;k<333;k++){
    if(dp[n][j][k]<0) continue;
    if(j*t+k<=w) ans=max(ans,dp[n][j][k]);
    }
  }
  cout<<ans<<endl;
  return 0;
}
【E - Ball Coloring】

N個のボールのペアが与えられる。赤と青に分けた時の(Rmax-Rmin)*(Bmax-Bmin)の最小値を求める。

コンテスト中は嘘解法を考えていて2ケース落ちた。
終わってから解説を見て通した。
2N個のボールのうち最大のものと最小のものは赤と青どちらかの最大、最小になるのはそれはそう。
それぞれ別の色の場合は小さいもの同士と大きいもの同士で分けるのが最適。
同じ色の場合はまず小さい方を青、大きい方を赤と分けたと仮定する。
またx[i]<y[i]が満たされていてxが昇順にソート済みと仮定する。
最初は青の最小値はx[0]で青の最大値はx[n-1]。
最小値が大きくなりえるのはi番目の要素をx[i]からy[i]に変えるときだけ。
(つまり赤のボールと入れ替えるとき。)
y[i]が今の最大値より大きい時は最大値も大きくなる。
i番目の要素を変えた場合に最小値が変化しないことがある。
(x[i]==x[i+1]のときやy[j]<x[i+1](j<i)のときなど)
まあそのへんはえいってやるとできる(デバッグに無限に時間を溶かした)

ソートがボトルネックでO(NlogN).

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
signed main(){
  int n;
  cin>>n;
  int x[n],y[n];
  for(int i=0;i<n;i++) cin>>x[i]>>y[i];
  int mi=min(*min_element(x,x+n),*min_element(y,y+n));
  int ma=max(*max_element(x,x+n),*max_element(y,y+n));
  int ans=1LL<<62LL;
  int r=mi,b=ma;
  for(int i=0;i<n;i++){
    if(x[i]>y[i]) swap(x[i],y[i]);
    r=max(r,x[i]);
    b=min(b,y[i]);
  }
  ans=min(ans,(r-mi)*(ma-b));
  //cout<<ans<<endl;
  vector<P> v;
  for(int i=0;i<n;i++){
    v.push_back(P(x[i],i));
  }
  sort(v.begin(),v.end());
  int ri=v[0].first,ra=v[n-1].first;
  int tmp=ra;
  for(int i=0;i<n-1;i++){
    //cout<<ra<<" "<<ri<<endl;
    ans=min(ans,(ma-mi)*abs(ra-ri));
    ra=max(ra,y[v[i].second]);
    ri=min(y[v[i].second],v[i+1].first);
    tmp=min(tmp,y[v[i].second]);
    if(tmp<=v[i+1].first){
      ri=tmp;
      break;
    }
    if(y[v[i].second]<=v[i+1].first) break;
    if(ri>=ra) break;
  }
  ans=min(ans,(ma-mi)*(ra-ri));
  cout<<ans<<endl;
  return 0;
}

速解きは正義。
完数で上がりたかった気もするけどまあ上がれればなんでもいいや(ア
落ちないように&橙になれるようにがんばるぞい!