[codeforces] Educational Codeforces Round 115 (Rated for Div. 2) A,B,C

https://codeforces.com/contest/1598

3솔

1. A

- 그래프 문제 , 구현문제

 

- 상하좌우 , 대각선 4방향 총 8 방향으로 움직여 (0,0)에서 끝까지 도달할 수 있는지 판단하는 문제

- 이 문제는 그래프 탐색으로 해결가능하고

- 그냥 3번째 샘플데이터처럼 1이 상하로 연속적일 경우를 찾아 문제를 해결할 수 있다.

 

2. B

- 구현문제, 포함 배제

- 학생들을 두그룹으로 나누는 문제

- 이 문제는 포함 배제의 원리를 응용하여 해결할 수 있다.

- 5 일에서 2일 을 고르는 모든 경우의 수를 탐색하여

- A + B - AnB = 학생수 인 요일 두개를 찾아야한다. (단 이때 A와 B가 n/2 보다 크거나 같아야한다.)

- AnB를 구하는것이 문제인데 이는 단순하게 아래와 같이 구하였다.

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < 5; j++)
            {
                cin >> student[i][j];
                if (student[i][j] == 1)
                {
                    oneday[j]++;
                }
            }
            for (int j = 0; j < 5; j++)
            {
                if (student[i][j] == 0)
                    continue;
                for (int k = j + 1; k < 5; k++)
                {
                    if (student[i][k] == 1)
                    {
                        twoday[j][k]++;
                    }
                }
            }
        }

 

 

3. C

- 이진 검색, 투 포인터

- 주어진 배열에서 원소 두개를 빼는데 이때 이전과 평균이 같도록해야하는 모든 경우의 수를 새는 문제.

- 정렬을 한뒤 upper_bound - lower_bound 해주면된다.

- 1:1 대응 함수이므로 하나의 값만이 같을 수 있다.

- 주의점: 평균이 실수일 수 도 있다. 하지만 찾는값은 정수, a의 입력으로 들어오는 값이 크므로 오버플로우가 발생할 수 있다.

unsigned long long solve()
{
    unsigned long long answer = 0;
    for (int i = 0; i < a.size(); i++)
    {
        double find = k * 2.0 - a[i];
        int lo = lower_bound(a.begin() + i + 1, a.end(), find) - a.begin();
        int hi = upper_bound(a.begin() + i + 1, a.end(), find) - a.begin();
        answer += (hi - lo);
    }
    return answer;
}