Codeforces round #66

Codeforces 参加記録

Result

コンテスト2ヶ月ぶりくらいな気がする。
最近、大学の授業についていけなくて、このままだと大学を辞めることになってしまうので悩んでます。


372(00:14) / 332(02:22) / 772(00:57) / - / - / -
1476点 95位


1841 -> 1903

A. The Elder Trolls IV: Oblivon

問題概要

辺の長さがx*y*zの直方体がある。この直方体をk回、辺に平行な面（座標は整数）で切断する。
このとき最大いくつの直方体を作ることができるか求めよ。


x,y,z≦10^6, k≦10^9を満たす。

試行錯誤

x軸、y軸、z軸に垂直な面で切る回数をX回、Y回、Z回としたら、
できる直方体の数は(X+1)*(Y+1)*(Z+1)回。
ということはk回の切断をなるべく違うX,Y,Zに均等に振り分けるのが最適。


x≦y≦zとしてもおｋ。
xにmin(x-1,k/3)回を振り分けて、yにmin(y-1,残りのk/3)回を振り分けて、残りをzに振り分ければ良いよね。


提出→WA. x,y,z大きい順に並べてた。
提出→WA. min(x-1,k/3)をmin(x,k/3)にしてた。
提出→pretest AC.

ソースコード
void run(){
  vector<int> a,b;
  int l,k;
  rep(i,3)cin>>l,a.push_back(l);
  cin>>k;
  sort(all(a));
  
  rep(i,3){
    b.push_back(min(k/(3-i),a[i]-1));
    k-=b[i];
  }
  long long ans=(long long)(b[0]+1)*(b[1]+1)*(b[2]+1);
  cout<<ans<<endl;
}

B. Need For Brake

問題概要

nチームの名前と現在の得点a[i]が与えられる。
1度レースを行い、上位mチームにi位にb[i]の得点が入る。
自分のチームの名前が与えられるとき、自分のチームのありえる順位として最高のものと最低のものを求めよ。

試行錯誤

2分探索っぽい？
あれ、greedyでいい気がしてきた。


書いてみる。いやいや、得点が高い人を高い順位に仮定して良い訳ないじゃん。
てことは、最高でi位が取れると仮定して、その得点以下の人をn-i-1人作るような解法？

うーん……自分以下の得点をギリギリで作るとして、二分探索+リストの削除が必要になるので、これは計算時間間に合うんだろうか。


いや、なんか尺取でいけそう。
チームを強い順に並べて、得点を低い順に足していく。
今の得点で自分より強いチームが作れなかったら次の得点を使う。


チームを強い順に並べてあるので、前のチームの処理のときに使わなかった得点で、自分より強いチーム作れる可能性はない。


書いた。WA(pretest 4).
なんか泥沼になりそう。Cを解いている人が多いので保留してCに行く。


（C解いた)


もう一度全部書き直す。
サンプル合った。WA(pretest 4)


以後1時間泥沼のデバッグ。

  • a!=bをa=!bと書いているというバグを発見。
  • ソートを逆順にしてたというバグを発見。

で、直して提出。pretest AC.
残り10分とかになったのでDに取り組む間もなく終了。

ソースコード
struct S{
  string name;
  int pt;
  S(string name,int pt):name(name),pt(pt){}
  S(){}
  bool operator<(const S &r)const{
    if(pt!=r.pt)return pt<r.pt;
    return name>r.name;
  }
};
bool win(string n,int p,S s){
  if(p!=s.pt)return s.pt>p;
  return s.name<n;
}

void run(){
  int n,m,t; cin>>n;
  vector<S> v,w;
  rep(i,n){
    S tmp;
    cin>>tmp.name>>tmp.pt;
    v.push_back(tmp);
  }
  
  cin>>m;
  vector<int> p;
  rep(i,n-m)p.push_back(0);
  rep(i,m)cin>>t,p.push_back(t);
  sort(all(p));

  string myteam; cin>>myteam;
  rep(i,n-1)if(v[i].name==myteam)swap(v[i],v[n-1]);

  sort(v.begin(),v.end()-1);

  int mx=n,mn=1;
  v[n-1].pt+=p[n-1];

  for(int i=0,j=n-2;i<n-1;i++){
    while(j>=0&&!win(v[i].name,v[i].pt+p[j],v[n-1]))j--;
    if(j>=0)mx--, j--;
  }
  
  v[n-1].pt+=p[0]-p[n-1];
  reverse(v.begin(),v.end()-1);

  for(int i=0,j=1;i<n-1;i++){
    while(j<n&&win(v[i].name,v[i].pt+p[j],v[n-1]))j++;
    if(j<n)mn++, j++;
  }

  cout<<mx<<" "<<mn<<endl;
}

C. LionAge II

問題概要

自分の名前が与えられる。これをk文字変えて、
もっともスコアの高い名前にしたい。このときのスコアを求めよ。


スコアは、以下のように算出される。
(前のアルファベット) (後のアルファベット) (得点)というm行の表があたえられる。
前のアルファベットと後のアルファベットが連続するときその得点が加えられる。

試行錯誤

単純なDPでいけそう。
dp[i][j][k]をi番目の文字までで、最後の文字がj、残りの変える回数がkのときの最高スコアにして、表を更新していけばいい。


書いて送信。WA.
初期化が間違っているらしい。k=0（一回も文字を変えていけない）の場合を考慮してなかった。


訂正して送信。pretest AC.

ソースコード
int dp[101][26][101];
int pt[26][26];

void run(){
  string nm; cin>>nm;
  int l=nm.size(), m, n; cin>>m;

  cin>>n;
  rep(i,26)rep(j,26)pt[i][j]=0;
  rep(i,n){
    int t;
    char a,b; cin>>a>>b>>t;
    pt[a-'a'][b-'a']=t;
  }

  rep(i,101)rep(j,26)rep(k,101)dp[i][j][k]=-100000000;
  rep(i,26){
    if(m-(i!=nm[0]-'a')>=0)
    dp[0][i][m-(i!=nm[0]-'a')]=0;
  }

  for(int i=1;i<l;i++)rep(prev,26)rep(next,26)rep(k,m+1){
    if(k-(next!=nm[i]-'a')>=0)
    dp[i][next][k-(next!=nm[i]-'a')]=
    max(dp[i][next][k-(next!=nm[i]-'a')],dp[i-1][prev][k]+pt[prev][next]);
  }

   int ans=-100000000;
   rep(i,26)rep(j,m+1)ans=max(ans,dp[l-1][i][j]);
   cout<<ans<<endl;
}