Little Piplup 8월 24일 팀연습

UCPC 이후 첫 팀연습은 고민 끝에 가장 쉬운 리저널이라는 평가를 받는 Pacific Northwestern으로 가기로 했다. 

ICPC 리저널에 Division이 있는건 처음 봤는데, Unofficial 스코어보드를 보니 Div2를 대략 퍼플~블루로 구성된 팀이 거의 다 풀 수 있는 셋인 것 같았다. 그정도면 우리입장에선 힐링셋으로 괜찮을 것 같다는 생각이 들어서 Div.2로 결정.

 

결과부터 말하자면 (...) 딱히 뭔가를 배울 만한 셋이 일단 아니었고, 제출 기록에서 보이는 O 14틀로 인해 사실상 1명 + 컴퓨터 시간 1시간이 사라진 상황이라서 매우 노답이었다. 

특히 우리 팀에서 가장 침착하게 구현 잘하는 Coffeetea가 저걸로 멘탈이 아예 탈주해 버려서;;; 

---

00:00~00:15 

Coffeetea는 O번, 나는 N번, Diordhd는 P번을 잡았다. Diordhd는 얼른 떠오르지 않는다고 종이에 뭔가를 적고 있었고, 나는 개쉬운 문제를 받아서 바로 코딩하려고 하던 순간에 Coffeetea가 "이거 바로 코딩 된다" 라고 하며 O번에 뭔가 코드를 작성하기 시작했다. 근데 은근히 구현에 헷갈리는 점이 조금 있는 것 같아서, 내가 그동안 Q번 솔루션을 생각하고 다시 N번으로 돌아갔다.

---

N. Odd Palindrome

Solve : Gratus907

Code : Gratus907

어떤 String에 대하여 Palindrome인 짝수 길이의 Substring의 존재 유무를 판단하는 문제.

짝수 길이의 모든 부분 문자열을 나열하면서 직접 팰린드롬 여부를 판정하면 $O(n^3)$. 전처리를 적절하게 해서 팰린드롬을 빠르게 판정할 수 있다면 $O(n^2)$ 로도 가능한..걸로 알고 있는데,

어차피 속도가 필요한 상황이면 Manacher's Algorithm을 쓰면 임의의 문자를 가운데로 하는 홀수 길이 팰린드롬 부분문자열을 모두 찾아낼 수 있다. 따라서, 매 글자마다 적절한 더미 '#' 같은걸 끼워넣고 돌려주면 $O(n)$ 에도 풀 수 있다.

 

하지만 $n = 100$ 이기 때문에 그냥 $O(n^3)$ 을 빨리 짜는 데 집중했다. 특히 Coffeetea가 다시 O번에 틀린점을 찾았다고 했기 때문에 빠르게 짜고 컴퓨터를 넘겨줘야겠다 싶었다.

 

문자열이 100만 글자였으면 Manacher 연습 문제로 좋았을 것 같다.

#include<bits/stdc++.h>
using namespace std;
 
char str[200];
char ans[2][200] = {"Odd.", "Or not."};
bool is_palindrome(int l, int r)
{
    int s = (r-l+1);
    for (int i = 0; i<(s/2); i++)
    {
        if (str[l+i]!=str[r-i])
            return 0;
    }
    return 1;
}
 
int main()
{
    int flag = 0;
    scanf("%s",str);
    int slen = strlen(str);
    for (int i = 0; i<slen-1; i++)
    {
        for (int j = i+1; j<slen; j+=2)
        {
            if (is_palindrome(i, j))
                flag = 1;
        }
    }
    printf("%s",ans[flag]);
}

---

Coffeetea가 O번을 연속 3틀했다. 처음 두 번은 놀랍게도 (...) No 를 출력해야 하는데 NO 를 출력해서 2틀 적립하고, 그걸 고치고 나니 WA on Test 4를 받았다. 이게 연습 끝까지 고통을 줄거라고는 생각 못했는데... 뭐 아무튼, 코드를 출력하고 내가 Q번을 풀러 갔다. 

그리고 1시간 동안 다같이 고통을 받았는데, 셋이 너무 쉽다 보니 Solve가 Code에 비해 지나치게 빨라서 컴퓨터에 코딩 큐가 쌓이기 시작했다. 나는 Q 답을 확신하고 있었고, Diordhd는 S번 로직을 대충 정리한 상태, Coffeetea는 출력한 O번 코드를 보면서 뭐가 틀렸는지 찾고 있는데 전혀 감을 못 잡고 있었다.

그리고 Q를 WA on Test 46을 받으면서 슬슬 팀원들이 다같이 3주만에 팀연습하는거라 그런지 망한거 같다는 얘기를 하고 있었다.

---

Q. Halfway

Solve : Gratus907

Code : Gratus907

1 부터 $n$까지 수들이 있는데, 1과 2, 1과 3, ... 1과 $n$을 비교하고, 다시 2와 3, 2와 4 ... 2와 $n$을 비교하는 식으로 비교 연산을 한다. 그런데 사실 실제로 뭔가를 비교하는 연산은 전혀 없고....

어떤 수를 들고 비교를 시작할 때, 그 수를 프린트한다. 즉 1과 2를 비교하기 전에 1을 프린트하고, $(1, n)$ 까지 작업을 수행한 다음, 2를 프린트하고 $(2, 3)$ 부터 작업을 진행한다.

이때 전체 작업이 반 진행됐을 때 마지막으로 print된 수를 찾으면 된다. 

종이에 식을 쓰다 보면, $k$가 프린트 되기 위해서 몇 번 비교 연산이 필요한지를 계산할 수 있는 $O(1)$ 짜리 식을 어렵지 않게 찾을 수 있다. 이제 이걸로 이분 탐색을 잘 하면 되는..데?

뭔가 코딩하다가 실수한건지, 아무튼 2번을 이렇게 틀렸다.

좀더 코딩이 간결한 답을 찾다가, 답이 대략

$$\left( 1 - \sqrt{\frac{1}{2}}\right) n$$ 부근에서 나타난다는 점을 파악하고 이걸 이용해서 다시 작성해서 AC.

#include<bits/stdc++.h>
using namespace std;
#define int ll
#define ll long long
 
int n;
 
int32_t main()
{
    cin >> n;
    int targ = n*(n-1)/2;
    int m = (1-sqrt(0.5))*n-3;
    m = max(0LL, m);
    while(m*(m-1) <= targ)
        m++;
    cout << n+1-m;
}

---

S. Purple Rain

Solve : Diordhd

Code : Diordhd

무슨 문제인지 잘 읽어보지는 않았는데, Diordhd가 그냥 잡고 코딩하면 된다고 하더니 적당히 잘 코딩해서 맞아왔다. 

Iterator 관련해서 약간의 이슈가 있긴 했지만 단순한 문제라서 (.end() 가 끝보다 하나 더 뒤의 iterator라는 것 때문에..) 처리하고, 자잘한 코딩실수들 때문에 3틀했지만 일단 AC.

이게 01:16 시점인데, 이 셋의 난이도를 생각하면 이때쯤 이미 O는 진작에 맞고, 5~6솔째를 하고 있었어야 했는데 뭔가 코딩이 굉장히 많이 말렸다.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int> pii;
 
char str[100020];
int ct[200020];
vector<pii> s;
int main()
{
    scanf("%s",str);
    int l = strlen(str), maxi = 0, mini = 0, sum = 0;
    s.push_back(pii(0,0));
    ct[100001]++;
    for(int i=0; i<l; i++)
    {
        if(str[i]=='B')
            sum++;
        else
            sum--;
        if(!ct[sum+100001])
            s.push_back(pii(sum,i+1));
        ct[sum+100001]++;
    }
    sort(s.begin(),s.end());
    maxi = max(s.begin()->second,(s.end()-1)->second);
    mini = min(s.begin()->second,(s .end()-1)->second);
    printf("%d %d",mini+1,maxi);
}

---

Coffeetea가 계속 O를 보면서 3틀을 적립하다가, 결국 포기하고 R을 풀러 갔다. R은 대략 뭔가 수학틱한 문제였는데 실수 오차도 크게 신경쓸거 없어 보여서 뭐.. 그냥 잘 되겠지.

나랑 Diordhd는 다른 문제들을 쭉 보다가, 나는 P번 풀이를 생각해서 코딩했지만 예제가 잘 안 나왔고 생각보다 반례가 많았다. Diordhd가 잡은 Y번은 정말 쉬운 문제였기 때문에 그냥 내가 마저 코딩해서 맞췄다.

---

Y. Delayed Work

Solve : Diordhd

Code : Gratus907 

임의의 자연수 $M$에 대해

$$\frac{KP}{M}+MX$$ 의 값을 최소화하는 문제.

산술기하평균 등등 여러 부등식으로 찾는 문제인가 했지만, 사실 모든 제한이 너무 작아서 그냥 가능한 $M$을 모두 열심히 탐색하면서 답을 찾아도 문제가 없다. 

#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
    int k, p, x;
    cin >> k >> p >> x;
    double minval = 1e11;
    for (int i = 1; i<=(int)1e7; i++)
        minval = min(minval,p*1.0*k/(double)i + (x*1.0*i));
    printf("%.3lf",minval);
}

---

R. Straight Shot

Solve : Coffeetea

Code : Coffeetea

O번 코드를 도저히 디버깅 못하겠다는 Coffeetea가 그냥 다른 문제를 잡아서 열심히 종이에 수식을 쓰다가 맞아왔다.

무슨 문제인지는 제대로 안 읽어 봤는데, 그냥 케이스를 나누고 실수연산을 막 돌려도 아무 문제가 없는것 같았다. 근데 종이에 뭔가 굉장히 복잡하게 많이 썼던데 식정리를 잘한건가? :frozen_thinking:

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n;
    double x;
    double v;
    scanf("%d %lf %lf", &n, &x, &v);
 
    double up = 0, down = 0;
 
    for ( int i = 0 ; i < n ; ++i ) {
        double left, right, speed;
        scanf("%lf %lf %lf", &left, &right, &speed);
        up += (right-left) * speed;
        down += (right - left);
    }
    if ( down == 0 ) {
        printf("%lf", x / v);
    } else {
        double vy = abs(up/x);
        if ( vy >= v ) {
            printf("Too hard");
        } else {
            double upmost = 2 * x / v;
            double vx = sqrt( pow(v,2) - pow(vy,2) );
            if ( vx > upmost ) {
                printf("Too hard");
            } else {
                printf("%.3lf", x / vx);
            }
        }
        
    }
}

---

Z. Forbidden Zero

Solve : Gratus907

Code : Gratus907

숫자 0을 사용하지 않고 쓸 수 있는 수들 중 주어진 $n$보다 큰 첫 번째 수를 찾는 문제.

$n$ 이 999,999 까지라서 답은 1,111,111 이하이므로 그냥 돌면서 찾자.

#include<bits/stdc++.h>
using namespace std;
 
int n;
 
bool check(int x)
{
    string str = to_string(x);
    sort(str.begin(),str.end());
    return (str[0]!='0');
}
int main()
{
    cin >> n;
    n++;
    while(!check(n))
        n++;
    cout << n;    
}

---

P. Fear Factoring

Solve : Gratus907, Diordhd

Code : Gratus907

어떤 수 $n$의 약수의 합을 $\sigma(n)$ 이라고 하자. 이때.

$$\sum_{x = a}^{b} \sigma{x}$$ 를 빨리 구하는 문제.

$a$, $b$ 가 $10^{12}$ 까지니까 직접은 못 구하고, $b-a \leq 10^{6}$ 을 잘 이용해야 한다. 

대략 느낌은, 어떤 수 $i$ 가 만약 $n$의 약수라면, $n / i$ 도 약수이므로 $10^{12}$ 정도의 약수를 판정하는데 $10^{6}$ 만 돌아 보면 된다. 즉, 어떤 작은 수 $i$를 이용해서 $u$ 와 $v = u+ki$를 만나면 이때 $i$를 두 번 더하면서 $u/i$ 와 $u/i + k$ 를 답에 같이 더해 주는 식으로 움직이면 한 $i$당 $(b-a)/i$ 정도 시간에 처리할 수 있고, 이건 결국 조화급수의 합이므로 시간 복잡도 $O(n \log n)$ 에 전체 문제를 해결하는 셈이 된다.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
int a, b;
int ans = 0;

int ask(int x)
{
    int res = 0;
    int s = (a-1)/x + 1;
    for (int i = s*x; i<=b; i+=x)
    {
        if (i/x < x)
            continue;
        if (i == x*x)
            res += x;
        else 
        {
            res += x;
            res += i/x;
        }
    }
    return res;
}
int32_t main()
{
    cin >> a >> b;
    for (int i = 1; i*i<=b; i++)
        ans += ask(i);
    cout << ans;
}

---

U. Unloaded Die

Solve : Diordhd

Code : Diordhd

읽어본다음 "어 이것도 개쉬운 문제네" 를 외치며 바로 코딩해서 AC.

주사위 눈과 확률이 주어지는데, 이 눈들 중 하나만을 조작해서 주사위의 기댓값을 $3.5$ 로 맞춰야 한다.

조작하는 수를 최소화 (최대한 작은 차이만큼 조작) 해야 하고, 눈은 임의의 실수로 조작할 수 있다. (아니 어차피 음수나 2.12 같은 숫자가 될거면 왜 굳이 주사위같은 이상한 방법으로 준거야?)

조금만 생각해보면 가장 확률이 높은 눈을 조작해야 작은 조정으로 기댓값을 크게 바꿀 수 있으므로 그렇게 해주면 된다.

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    double pos[7], sum = 0, maxi = 0;
    for(int i=0; i<6; i++)
    {
        scanf("%lf",pos+i);
        sum += ((double)(i+1)) * pos[i];
        maxi = max(maxi,pos[i]);
    }
    printf("%.3lf",abs((double)3.5-sum)/maxi);
}

---

X. Star Arrangements

Solve : Diordhd

Code : Diordhd

내가 Coffeetea와 함께 W번을 고민하는 동안 Diordhd가 컴퓨터를 잡고 X번을 나랑 같이 대충 읽어본 뒤 코딩했다. 잘 모르겠지만 일단 $n$, $n-1$ 을 교대로 쓰거나 (처음은 $n$으로 시작해야 하지만 끝은 상관 없음), $n$ 들만 써서 $k$를 만들 수 있는지 판단하면 되는 문제.

 

경우를 침착하게 나눠서 코딩하면 된다.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
vector<pii> ans;
int main()
{
    int n;
    scanf("%d",&n);
    printf("%d:\n",n);
 
    for(int i=2;i<=(n+1)/2;i++)
    {
        if(n%(2*i-1)==0||(n+i-1)%(2*i-1)==0)
            printf("%d,%d\n",i,i-1);
 
        if(n%i==0)
            printf("%d,%d\n",i,i);
    }
}

---

W. Grid Coloring

Solve : Coffeetea, Gratus907, Diordhd

Code : Gratus907

제일 팀연습 스럽게 푼 문제. 

어떤 Grid에 Blue와 Red로 색을 칠해야 하는데, 이미 칠해진 점들이 몇 개 있으며,

Blue인 점 $(x, y)$ 에 대해서 반드시 $(1, 1)$ 부터 $(x, y)$ 까지의 왼쪽 위 부분 직사각형이 전부 Blue여야 한다.

조금 생각해 보면, 이 조건이 사실상 Star-shaped domain (또는 Radially Convex) 을 의미하는 것을 알 수 있다. 

 

$i$ 번째 행에서, Blue인 칸의 가장 오른쪽 index를 $k_i$ 라고 하자. 그러면, 이 $k_i$는 위에서부터 ($k_1$) 아래로 내려갈 때 ($k_n$) monotonic decreasing 해야 한다. 또한, 이미 Blue 인 점이 있다면 그 점보다는 반드시 뒤에 있어야 하므로 어떤 lower bound가 생기게 되며, 이미 R인 점은 건드릴 수 없으므로 어떤 upper bound가 생기게 된다.

따라서 이 문제는 각 항 $k_1$ 부터 $k_n$ 까지에 각각 다른 최소, 최댓값들이 주어질 때, 그 사이를 잘 통과하는 감소수열의 개수를 세는 문제로 바뀌게 되고 이건 DP로 $O(n^2)$에 풀 수 있다. 다만 칸이 30칸밖에 안되므로 전처리고 뭐고 집어치우고 그냥 $O(n^3)$ 을 구현했다.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define int long long
int mini[40];
int maxi[40];
int dp[40][40];
char board[40][40];
int n, m;
int32_t main()
{
    scanf("%lld %lld",&n, &m);
    for (int i = 1; i<=n; i++)
    {
        scanf("%s",board[i]+1);
    }    
    for (int i = n; i>=1; i--)
    {
        int rr = m+1;
        for (int j = 1; j<=m; j++)
        {
            if (board[i][j]=='R')
            {
                rr = j;
                break;
            }
        }
        maxi[i] = rr-1;
    }
    for (int i = 2; i<=n; i++)
    {
        maxi[i] = min(maxi[i],maxi[i-1]);
    }
    for (int i = 1; i<=n; i++)
    {
        int lb = 0;
        for (int j = 1; j<=m; j++)
        {
            if (board[i][j] == 'B')
            {
                lb = j;
            }
        }
        mini[i] = lb;
    }
    for (int i = n-1; i>=1; i--)
    {
        mini[i] = max(mini[i],mini[i+1]);
    }
    for (int i = mini[n]; i<=maxi[n]; i++)
        dp[n][i] = 1;
    for (int i = n-1; i>=1; i--)
    {
        for (int j = mini[i]; j<=maxi[i]; j++)
        {
            int tmp = 0;
            for (int k = 0; k<=j; k++)
            {
                tmp += dp[i+1][k];
            }
            dp[i][j] = tmp;
        }
    }
    int res = 0;
    for (int i = 0; i<=m; i++)
    {
        res += dp[1][i];
    }
    printf("%lld",res);
}

---

마지막 1시간 동안 나랑 Diordhd는 T번을 보고, Coffeetea는 다시 O번을 디버깅하기 시작했다. 

결국 O번에서 뭐가 틀린 건지는 못 찾았고, T번 솔루션이 생각나서 그냥 T번 코딩.

---

T. Security Badge

Solve : Gratus907, Diordhd

Code : Gratus907 (거의 다같이 페어코딩하긴 했다)

방 $n$개 사이에 문 $m$개가 있는데, 이 문은 단방향이고, $c$ 이상 $d$ 이하의 번호를 가진 직원만 이 문을 지날 수 있다.

이때, $s$에서 $t$ 로 갈 수 있는 사람의 수를 세는 문제.

 

단순 BFS 같이 보이지만, 사람이 무려 $10^{9}$ 명이라서 BFS를 모두 돌아 볼 수 없다. 다만 방과 문이 1000개, 5000개 정도로 작다.

생각해 보면, 문이 5천개 밖에 없어서, 여러 명의 사람들이 사실상 같게 취급된다. (여기서 사실상 같다는 것은, $i$가 지나는 문은 항상 $j$도 지날 수 있고, 그 역도 성립) 따라서 이 사실상 같은 사람들을 한 그룹으로 묶어 버리고, 각 그룹에서 1명씩만 실제로 보내 본 다음 그 1명이 도착 가능하면 그룹원의 수만큼 더해주면 $O(nm + m^2)$ 정도 시간에 풀 수 있다. (한 명 보내 보는데 $O(n+m)$, 보내야 할 사람은 대충 $2m$명 정도)

예를 들어 1~10까지 사람이 있고, 3부터 5까지 통과할 수 있는 문과, 5부터 9까지 통과할 수 있는 문이 있으면 

(1, 2) , (3, 4), (5), (6, 7, 8, 9), (10) 이렇게 5개 그룹만 돌아 보면 된다는 뜻.

#include<bits/stdc++.h>
using namespace std;
 
struct door
{
    int to, left, right;
    door (int a, int b, int c)
    {
        to = a, left = b, right = c;
    }
};
int n, m, k, s, t;
vector <int> changer;
vector <door> graph[1010];
vector <pair <int, int>> group;
 
bool canpass(int x)
{
    bool visit[1010];
    memset(visit,0,sizeof(visit));
    visit[s] = 1;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto it:graph[u])
        {
            if (!visit[it.to])
            {
                if (it.left <= x && x <= it.right)
                {
                    q.push(it.to);
                    visit[it.to] = 1;
                }
            }
        }
    }
    return visit[t];
}
int main()
{
    scanf("%d %d %d",&n,&m,&k);
    scanf("%d %d",&s,&t);
    changer.push_back(1);
    changer.push_back(k+1);
    for (int i = 0; i<m; i++)
    {
        int u, v, c, d;
        scanf("%d %d %d %d",&u,&v,&c,&d);
        graph[u].push_back(door(v,c,d));
        changer.push_back(c);
        changer.push_back(d+1);
    }
    sort(changer.begin(),changer.end());
    changer.erase(unique(changer.begin(),changer.end()),changer.end());
    int s = changer.size();
    for (int i = 0; i < s-1; i++)
    {
        group.push_back({changer[i],changer[i+1]-1});
    }
    int ss = group.size();
    int ans = 0;
    for (int i = 0; i<ss; i++)
    {
        if (canpass(group[i].first))
        {
            ans += (group[i].second-group[i].first+1);
        }
    }
    printf("%d",ans);
}

---

이 문제까지 코딩 끝난 후, V와 O가 남은 상태였고, V를 남은 20분에 푸는건 무리인거 같아서 O를 내가 Coffeetea의 코드를 보지 않고 Python3으로 처음부터 다시 구현했다.

그리고 똑같이 WA on Test 4 를 받았다 (...)

 

라운드가 끝난 후, BOJ에서 해당 문제 (O번, 링크)를 찾아서 채점했더니 AC를 받았다. 생각해보면 이렇게 간단한 문제를 두명이 다른언어로 처음부터 코딩을 해서 틀린다는것도 이상해서, 공식 채점 데이터를 받아서 돌려보니 다 맞았다.

 

퍼시픽 리저널의 장점중 하나로 Jury solution이 여러 언어로 제공된다는 점이 있어서, 이 Jury Solution을 받아서 Codeforces에 제출해 보니 WA On Test 4 를 받았다. Jury solution도 WA를 받는걸 보고 이건 문제가 이상한가 보다 하고 그냥 집에 왔는데, 아무리 생각해도 맞은 사람이 꽤 있다는게 이상해서 이 문제에서 AC를 받은 사람에게 개인적으로 부탁해서 코드를 받았더니 (Gym은 원래 다른 사람의 코드를 못 보는 것 같았다. 가끔 열리는 것도 있던데 뭔지 잘 모르겠다) \texttt{while(cin << n)} 으로 시작하는걸보고 뭔가 이상하다는 생각이 들었다. Codeforces Gym에서 공지로 "The input may contain multiple cases. Process the cases until end of file." 을 Announce했다는걸 이때 알았다.

 

아니 상식적으로 이런건 좀 크게 알림을 주던지 (문제지에는 안 써 있다;;) 

리저널에서 이런 Announce가 있었던거면 문제지에 이걸 고쳐 놓든가. (수정본 문제지가 따로 업데이트되는 대회가 꽤 많다) 리저널이 그런 수고를 해줄리가 없는거면 코포에서 데이터를 넣을때 한 파일에 여러개가 들어오는 입력을 다 빼고 케이스를 따로따로 만들던가

셋중에 하나만 했어도 상관이 없는데 이걸로 최소 컴퓨터 시간 1시간 + Coffeetea의 라운드 중 멘탈 + 나랑 Diordhd의 멘탈 일부를 날려먹고 나니 상당히 어이가 없었다. 

---

이건 코포의 실수니까 별개로 하고, 앞으로 퍼시픽 딥2로 팀연습을 돌진 않을 것 같다. 뭔가를 배웠다 (또는 팀연습을 하면서 의미가 있었다) 는 생각이 드는 문제는 P, W, T 세개밖에 없는데 셋 다 Division 1 이랑 공유하는 문제다. 퍼시픽으로 돌거면 딥1을 돌아야 우리가 목표로 하는 대회의 난이도 (ICPC Preliminary, Seoul Regional) 에 대충 맞을 것 같다.