いがメモ

プログラミング関連についてやったことの記録を書いていきます。

TopCoder SRM 617 Div1 Easy MyLongCake [1人競技プログラミング Advent Calendar 2016 16日目]

この記事は1人競技プログラミング Advent Calendar 2016 16日目の記事です。

問題概要:
TopCoder Statistics - Problem Statement
長さn(2<=n<=100,000)のケーキがある。
これから来る友人全員に同じサイズのケーキを渡したい。
来る人数はnの約数の人数のいずれかの人数である。

どの人数が来てもいいように予めケーキをカットしておきたい。
例えばn=6の時は1,2,3人が来るので、[2,1,1,2]とケーキをカットしておくと、1人来たときは全部、2人来たときは[2,1]と[1,2]のケーキを渡し、3人来たときは[2],[1,1],[2]のケーキを渡せば同じサイズのケーキを渡すことが出来る。
渡すケーキは連続である必要があるので、上記の例では[2,1,2,1]とカットしておくことは許されない。(3人来た時に渡せなくなる為)
あらかじめケーキを分けて置く個数を答えよ。

解いた方法:
どの人数が来たときも、(n/人数)のサイズのケーキを渡せばよい。
ということは、あらかじめ約数の個数毎に切り込みを入れておけばよい。(対応する約数があるので)

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

class MyLongCake {
    public:
    int n;
    int cut(int _n) {
        n = _n;
        set<int> used;
        REP2(i, 2, n){
            if(n % i == 0){
                int tmp = i;
                while(tmp != n){
                    used.insert(tmp);
                    tmp += i;
                }
            }
        }

        return used.size()+1;
    }
};