裏紙

ほぼ競プロ、たまに日記

SRM 669 Div1 Easy - SubdividedSlimes

問題

TopCoder Statistics - Problem Statement

問題概要

スライムを分割するゲームをする。最初は大きさがSのスライムが1体いる。ゲームはターン制で、1ターンの内に次のことを行う:

今いるスライムの中から1体を選んで、2体に分裂させる。選んだ1体のスライムの大きさがzなら、2体の大きさは2つの自然数xyを選ぶことに酔ってx,y \, (x+y=z, \,1 \le x, \, 1 \le y)に分裂させることが出来る。その時に、プレイヤーは得点としてx*yを得る。

SMが与えられる時、Sの大きさのスライムを分裂させて合計の得点がM以上になるのに必要なターン数の最小値を求めよ。

イデア

分裂の方法によらず最終的には1のスライムがS個生まれるのは想像に難くない。また、その分裂の方法によらずに最終的に得られる得点も決まっているので、それ以上の得点を取ることは不可能であることから、それを基に不可能判定をまず行っておく。以下、ターン数があるものとして考える。

最終的に得られる得点は同じなのだから、できるだけ最初の方に得られる点数が大きい方がいいだろう、と思って最終的な状態(1がS個)から優先度付きキューを使って最小の2つをマージしていってそれを逆からみるのが最良なのではないか、と思って試してみたけどそれだとうまくいかない。

見る方向をちょっと変えて、ターン数を決め打ちにする。kターン与えられるので、その時に得られる最大スコアを考えてみると、スライムはk+1体いる状態で終わっていることになる。さっきと同じように、これをマージしていく方向で考えると、このk+1体のスライムはできるだけ均等な大きさのほうがよい。よって、小さいターン数からこの方法で得られる最大スコアを試していき、これがMを初めて超えた位置が解となる。

Editorialみると、もっと数学的にわかりやすい説明書いてあった。Lagrangeの未定乗数法とかそういえば習ったなぐらいの感覚だった...

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(i=0;i<n;++i)
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define mp make_pair
#define pb push_back
#define fi first
#define sc second

class SubdividedSlimes {
    public:
    int needCut(int S, int M){
      int i,j;

      int lim=0;
      rep(i,S) lim+=i;

      //このサイズで得られる点数上限を超えている
      if(lim<M) return -1;

      int ans=0;
      for(i=1;i<=S;++i){//i回の分割に対してベストな方法
        vector<long> ends(i);
        rep(j,i) ends[j]=S/i;
        rep(j,S%i) ++ends[j];

        //printf("start %d\n",i);
        priority_queue<long,vector<long>,greater<long>> minpq;
        rep(j,i) minpq.push(ends[j]);

        long sc=0;
        while(minpq.size()>1){
          long x=minpq.top(); minpq.pop();
          long y=minpq.top(); minpq.pop();
          //printf("merge %ld %ld makes %ld\n",x,y,x*y);
          sc+=x*y;
          minpq.push(x+y);
        }

        if(sc>=M){
          ans=i-1;
          break;
        }
      }


      return ans;
    }
};