이번 에디토리얼은 세 문제 다 난이도가 어렵지 않은 편이라 PPP가 엄청나게 많았습니다. 다만 Hard에서 오버플로우, 나머지 처리 실수로 Systest Fail 나신 분들이 많았습니다.

Easy (300 pts)

1 이상 10억 이하의 N이 주어질 때, 10진수 모든
자릿수의 곱이 N이 되는 자연수를 찾으려 합니다. 가령, N이 27이면 333과 39가 있겠죠. 3*3*3=27=3*9니까요.
이러한 자연수들 중 가장 작은 자연수를 찾아, (이 경우엔 9가 되겠지요) 그 자연수의 자릿수의 개수를 출력하는 프로그램을
작성하시오.
풀이:
[spoiler="더 보기..."] 우선 N이 1일 때는 답이 1이 됩니다. 이것이 자릿수 중에 1이 들어가는 유일한 예가 되므로 예외처리 해 주시고,
풀이법은, 승리의 그리디입니다. 9부터 8, 7, 6, .. 차례로, N을 나누어 떨어지는지 체크해보고, 나누어 떨어지면 나눕니다. 몇 번이나 나누어졌는지 세어서 결과를 출력합시다.
제수로 사용된 한 자리 수를 나열했을 때 (예: 100: 5 5 4) , 이 수열의 길이와, 문제 조건을 만족하는 가장 작은 수의 자릿수가 동일하다는 것을 보일 수 있습니다.
자세한 증명은 아래에 친절하신 분이 리플로 달아주실 것입니다.
~~~ cpp

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
class ProductOfDigits {
public:
int smallestNumber(int N) {
int digits = 0;
if (N == 1) return 1;
for (int i = 9; i >= 2; i--) {
while (N % i == 0) {
N /= i;
digits++;
}
}
if (N != 1) return -1;
return digits;
}

[/spoiler]
Medium (600 pts)

당
신은 게임 캐릭터입니다. 게임을 시작하면 체력 (Strength)과 지력 (Intellect) 지수가 둘 다 1인 채로
시작합니다. 게임 상에 할 수 있는 퀘스트의 수가 N 개인데, i 번째 퀘스트를 하기 위해서는 체력이 strength[i] 이상이거나 지력이 intellect[i] 이상이어야 합니다.
해당 퀘스트를 수행하고 나면 스킬 포인트 points[i] 를 받는데, 하나의 스킬 포인트로 체력을 1 올리거나 지력을 1 올릴 수 있습니다. 무엇을 올릴지는 플레이어의 자유입니다.
퀘스트의 정보가 주어졌을 때, 한 플레이어가 한 번의 플레이동안에 수행할 수 있는 퀘스트의 최대 개수를 출력하시오.
풀이:
[spoiler="더 보기..."]어떤 캐릭터의 체력이 strength[i], 지력이 intellect[j] 라고 합시다. 자신이 할 수 있는 퀘스트는 다 하고, 스킬 포인트를 쌓아놨다고 합시다. 그러면:
(자신이 한 퀘스트의 수) = count( k  | strength[k] <=  strength[i]  ||  intellect[k] <= intellect[j] )
가 되고,
(자
신이 쌓은 스킬 포인트의 수) = sum(points[k] | strength[k] <=  strength[i]  || 
intellect[k] <= intellect[j] ) - (strength[i] - 1) - (intellect(j] -
1)
이 되지요. 맨 오른쪽에 두 항은 현재의 스탯을 만들기 위해 사용한 포인트의 개수입니다.
자.. 이제 할 수 있는 퀘스트는 다 하고, 포인트를 사용하여 능력치를 끌어올려 할 수 있는 퀘스트밖에 남지 않았습니다.
어떤 퀘스트 p가 있을 때, 이 퀘스트는
<ul><li>체력을 끌어올려서 하거나 : strength[p] &lt;= strength[i] + (쌓은 스킬포인트 수)
</li><li>지력을 끌어올려서 하거나 : intellect[p] &lt;= intellect[j] + (쌓은 스킬포인트 수)
</li></ul>
두 가지 방법으로 할 수 있습니다. 각각의 경우에, 전자는 상태가 (strength[p], intellect[j]) 가 되고, 후자는 상태가 (strength[i], intellect[p]) 가 됩니다.
자, BFS / DFS 고고싱 합시다.
~~~ cpp

#include <string>
#include <vector>
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <sstream>
#include <set>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof((x).begin())it=(x).begin();it!=(x).end();++it)
#define all(x) (x).begin(),(x).end()
#define CLR(x,v) memset(x,v,sizeof(x))
#define SMIN(a,b) a=min((a),(b))
#define SMAX(a,b) a=max((a),(b))
#define pb push_back
#define sz size()
#define exist(c,x) ((c).find(x)!=(c).end())
typedef pair<int, int> pi;
typedef pair<pi, pi> ppi;
class StrengthOrIntellect {
public:
int numberOfMissions(vector <int> strength, vector <int> intellect, vector <int> points) {
    int N = strength.sz;
    int result = 0;
    set<ppi> passed;
    vector<ppi> st;
    ppi init;
    int intdone = 0, intp = 0;
    REP(i, N) {
        if (strength[i] <= 1 || intellect[i] <= 1) {
            intdone++;
            intp += points[i];
        }
    }
    init = make_pair(make_pair(1, 1), make_pair(intdone, intp));
    passed.insert(init);
    st.pb(init);
    while(!st.empty()) {
        ppi th = st.back();
        st.pop_back();
        int stre = th.first.first;
        int inte = th.first.second;
        int done = th.second.first;
        int rema = th.second.second;
        //printf("%d %d %d %d\n", stre, inte, done, rema);
        result = max(result, done);
        REP(i, N) {
            if (stre < strength[i] && inte < intellect[i]) {
                REP(stra, 2) {
                    int nstre = stre;
                    int ninte = inte;
                    if (stra == 0)
                        nstre = max(stre, strength[i]);
                    else
                        ninte = max(inte, intellect[i]);
                    int todo = (nstre - stre) + (ninte - inte);
                    if (todo <= rema) {
                        int nrema = 0;
                        int ndone = 0;
                        REP(j, N) {
                            if (strength[j] <= nstre ||
                                intellect[j] <= ninte) {
                                ndone++;
                                nrema += points[j];
                            }
                        }
                        nrema -= ((nstre - 1) + (ninte - 1));
                        ppi nppi = make_pair
                            (make_pair(nstre, ninte), make_pair(ndone, nrema));
                        if (!exist(passed, nppi)) {
                            passed.insert(nppi);
                            st.pb(nppi);
                        }
                    }
                }
            }
        }
    }
    return result;
}

[/spoiler]
Hard (900 pts)
길
게 이어진 선상에 나무 N그루를 0번부터 N-1 번까지 차례로 심는다. 각각의 위치가 X_0, X_1, X_2, ...,
X_N-1 이라고 하자. 한 그루를 심을 때 드는 비용은, 이미 심어져있는 나무들 각각과의 거리의 함이다. 즉,
X_i 를 심는데에 드는 비용 : sum( abs(X_j - X_i) ) where 0 <= j< i
이다. 이 때, 0 번째 나무를 제외한 모든 나무들을 심는데 드는 각각의 비용의 곱을 1,000,000,007 로 나눈 나머지를 구하는 프로그램을 작성하시오.
풀이:
[spoiler="더 보기..."]i 번째 나무에 X_i 를 심는데 드는 비용은,
sum( abs(X_j - X_i) ) where 0 <= j < i
= sum( X_i - X_j | X_j < X_i ) + sum( X_j - X_i | X_i <
X_j ) where 0 <= j < i // X_i 의 왼쪽에 있는 나무와 오른쪽에 있는 나무로 나누어 계산
= X_i * count( X_j | X_j < X_i ) - sum( X_j | X_j < X_i ) + sum( X_j | X_i < X_j ) - X_i * count( X_j | X_i < X_j )
가 됩니다.
count(X_j | X_j < X_i ) 는 X_i 왼쪽의 나무 수,
count(X_j | X_j > X_i ) 는 X_i 오른쪽의 나무 수,
sum(X_j | X_j < X_i ) 는 X_i 왼쪽의 나무 좌표의 합
sum(X_j | X_j > X_i ) 는 X_i 오른쪽의 나무 좌표의 합
이 되지요.
자.. 그럼 위의 네 쿼리를 O( lg N ) 만에 답해줄 수 있고, 삽입도 O( lg N ) 만에 되는 자료구조를 찾으면 되겠군요. 네. Binary Indexed Tree 입니다.
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
~~~ cpp

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof((x).begin())it=(x).begin();it!=(x).end();++it)
#define all(x) (x).begin(),(x).end()
#define CLR(x,v) memset(x,v,sizeof(x))
#define SMIN(a,b) a=min((a),(b))
#define SMAX(a,b) a=max((a),(b))
#define pb push_back
#define sz size()
#define exist(c,x) ((c).find(x)!=(c).end())
#define cexist(c,x) (find(all(c),x)!=(c).end())
typedef long long ll;
ll modulo = 1000000007;
ll mx = 262143;
ll quad[524288], quad2[524288];
void summ(int p, int lo, int hi, int left, int right, ll& result, ll& count) {
result = 0;
count = 0;
if (left >= mx || right < 0) return;
if (hi < left || right < lo) return;
if (left <= lo && hi <= right) {
result = quad[p];
count = quad2[p];
return;
}
// left
int c2 = (lo + hi+1)/2;
ll t1 = 0, t2 = 0;
summ( p*2+1, lo, c2-1, left, right, t1, t2);
result += t1; count += t2;
result %= modulo; count %= modulo;
summ( p*2+2, c2, hi, left, right, t1, t2);
result += t1; count += t2;
result %= modulo; count %= modulo;
}
void insert(int p, int lo, int hi, int pos, ll value) {
if (hi < pos || pos < lo) return;
if (lo <= pos && pos <= hi) {
quad[p] += value;
quad[p] %= modulo;
quad2[p]++;
quad2[p] %= modulo;
}
if (lo == hi) return;
int c2 = (lo + hi + 1) / 2;
insert(p*2+1, lo, c2-1, pos, value);
insert(p*2+2, c2, hi, pos, value);
}
class ProductOfPrices {
public:
int product(int N, int L, int X0, int A, int B) {
REP(i, 524288) {
quad[i] = 0;
quad2[i] = 0;
}
ll Xp = X0 % L;
insert(0, 0, mx, Xp, Xp);
ll result = 1;
REP(i, N-1) {
ll Xn = (Xp * A + B) % L;
ll suma, count;
ll price = 0;
// left
summ(0, 0, mx, 0, Xn-1, suma, count);
suma %= modulo;
price = price + (Xn * count) % modulo;
price %= modulo;
price = (price + modulo - suma) % modulo;
summ(0, 0, mx, Xn+1, mx, suma, count);
suma %= modulo;
price += suma + modulo - (Xn * count) % modulo;
price %= modulo;
if (price < 0) price += modulo;
result *= price;
result %= modulo;
//printf("%lld %lld\n", Xn, result);
insert(0, 0, mx, Xn, Xn);
Xp = Xn;
}
return result;
}
};

[/spoiler]
<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/53221">원문보기</a>]</div>