[editorial] SRM 424 Div 1

  • Pan
    Pan

    이번 에디토리얼은 세 문제 다 난이도가 어렵지 않은 편이라 PPP가 엄청나게 많았습니다. 다만 Hard에서 오버플로우, 나머지 처리 실수로 Systest Fail 나신 분들이 많았습니다.
    srm424div1.png
    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) , 이 수열의 길이와, 문제 조건을 만족하는 가장 작은 수의 자릿수가 동일하다는 것을 보일 수 있습니다.
    자세한 증명은 아래에 친절하신 분이 리플로 달아주실 것입니다.

    #include <string>
#include <vector>
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <sstream>
#include <set>
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가 있을 때, 이 퀘스트는

    • 체력을 끌어올려서 하거나 : strength[p] <= strength[i] + (쌓은 스킬포인트 수)
    • 지력을 끌어올려서 하거나 : intellect[p] <= intellect[j] + (쌓은 스킬포인트 수)

    두 가지 방법으로 할 수 있습니다. 각각의 경우에, 전자는 상태가 (strength[p], intellect[j]) 가 되고, 후자는 상태가 (strength[i], intellect[p]) 가 됩니다.
    자, BFS / DFS 고고싱 합시다.

    #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

    #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]

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    15년 전
3개의 댓글이 있습니다.
  • Toivoa
    Toivoa

    Hard가 count랑 sum으로 계산이 되는거였구나 -_-q 난 뭘 했던거지?? ㅠㅠ


    15년 전 link
  • nocut98
    nocut98

    사실은 이날 최초의 한국인 타겟이 등장하려나... 하던 매치였습니다. 화이팅!!


    15년 전 link
  • JongMan
    JongMan

    다음엔 꼭 등장해 보도록 하겠습니다. :)


    15년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.