에디토리얼을 정말 오랜만에 써보는 것 같습니다 ^^ 저 개인적으로도 좋은 결과를 기록한 대회였고, 무엇보다도 문제를 설명하면서 꼭 언급하고 싶은 내용이 있어서 이렇게 일찌감치 에디토리얼을 질러 봅니다.
아무래도 퀄 대회인 만큼 난이도는 그렇게 높진 않은 편이었습니다. 하드를 그럭저럭 풀더라도 100위권 안에 드는게 쉽진 않았으니까요. 제 기억 속에 퀄 대회는 비교적 쉬운 대회란 기억이 남아 있는데, 막상 어제 대회 전에 작년 퀄을 풀어보니 그렇게 쉽진 않더라고요. 그래서 조금 긴장한 상태에서 대회에 임했던게 좋은 결과를 가져다 준게 아닐까 싶습니다 :)

결과는 위와 같았습니다. 최종 확정된 결과는 아니고, 현재까지 알려진 결과입니다. 한국인 중에는 총 16명이 퀄을 통과했습니다. 예년의 경우에는 이지만 잘 풀어도 Round 2 정도까지는 진출할 수 있었는데, 올해의 커트라인은 이보다는 높아 보입니다. 하지만 이지를 잘 풀고, 챌린지에서 좋은 결과를 낸다면 통과할 수도 있었네요 [....]
Level 1 (250)
정수로 이루어진 배열 A가 주어졌을 때, 이 배열을 정렬된 순서로 바꿔주는 순열(permutation) P를 찾으라. 즉, B[ P[i] ] = A[i] 를 이용하여 새로운 배열 B를 만들었을 때, B가 정렬된 상태가 되어야 한다. 이러한 P가 여러 개일 경우, 사전식으로 가장 앞서는 것을 구한다. 배열의 크기는 50 이하이며, 각 원소의 값은 1000 이하이다.
[spoiler="(풀이 보기)"]문제는 결국 A를 정렬했을 때, 각각의 원소를 어디로 보내느냐 입니다. 수어진 순열의 정의상 A[i] 는 P[i] 번째 위치로 가게 되기 때문입니다. 여기서 문제가 발생하는데, 가능한 위치가 여러 개인 경우입니다. 즉, A에 동일한 수가 여러 개 있을 경우, 이들의 순서도 고려해야 합니다. 우리는 사전식으로 가장 앞서는 P를 구하므로, A에서 보다 앞쪽에 나오는 수를 B에서도 보다 앞쪽으로 보내면 됩니다.
요약하면 A의 각 원소 크기 순서대로, 같은 원소가 여럿 있다면 앞에서부터 차례로 번호를 붙이면 그것이 답이 됩니다.

struct SortingWithPermutation
{
    vector<int> getPermutation(vector<int> a)
    {
        int l0, l1, idx = 0;
        vector<int> ret(n);
        for(l0=1;l0<=1000;l0++)
            for(l1=0;l1<n;l1++)
                if(a[l1]==l0)
                    ret[l1]=idx++;
        return ret;
    }
};

[/spoiler]
Level 2 (500)
어떤 수가 1보다 큰 제곱수(4, 9, 16, …)로 나누어 떨어지지 않는다면 square-free 하다고 말한다. 정수 A, B가 주어졌을 때 두 수 사이에는 몇 개의 square-free 한 수가 존재하는가? A는 10^12 이하, B는 A+10^6 이하이다.
[spoiler="(풀이 보기)"]일단 A

int check[1000001];
struct SquareFreeNumbers
{
    int getCount(long long min, long long max)
    {
        long long l1, l2;
        for(l1=2;l1<=1000000;l1++)
        {
            long long sqr=l1*l1;
            for(l2=min/sqr-1;sqr*l2<=max;l2++)
                if(min <= sqr*l2)
                    check[sqr*l2 - min] = 1;
        }
        int ret = 0;
        for(l1=0;min+l1<=max;l1++) ret += (check[l1] == 0);
        return ret;
    }
};

[/spoiler]
Level 3 (1000)
ㅁㅁㅁ
[spoiler="(풀이 보기)"] [/spoiler]
아직 결과가 확정된 건 아니지만 퀄 통과자 분들께 축하의 말씀을 드립니다~ 아울러 나머지 분들도 남은 두 번의 퀄에서 꼭 통과하시길 바랍니다!