[Codeforce] Educational Codeforces Round 115 (Rated for Div. 2) 풀이

A : Computer Game (0:19)

---

    (0,0) 위치에서 (1,n) 까지 갈 수 있는지 확인하는 문제이다. 오랜만에 알고리즘 문제를 풀어서 Virtual participation(이하 VP) 당시 얼탔다. 그냥 느낌대로 풀었는데 시간도 20분 가까이 걸렸고, 코드도 안 예쁘다. 어차피 오른쪽 아래로만 가니 8방위가 아니라 오른쪽 위, 오른쪽 아래, 아래, 이렇게 3 방향만 고려하면 됐다. 다음에는 예쁘게 풀어보자.

 

#include <iostream>
#include <vector>
#include <string>
#include <queue>
 
using namespace std;
 
vector<vector<int>> field;
vector<vector<bool>> visited;
 
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int dy[8] = { 1,1,0,-1,-1,-1,0,1 };
 0
int main(void)
{
	int T, n;
	string input;
 
	cin >> T;
 
	while (T--)
	{
		cin >> n;
 
		field.assign(2, vector<int>(n+1, 1));
		visited.assign(2, vector<bool>(n + 1, false));
 
		for (int i = 0; i < 2; ++i)
		{
			input = "";
			cin >> input;
 
			for (int j = 0; j<input.size(); ++j)
			{
				field[i][j] = input[j] -'0';
			}
		}
 
		queue<pair<int, int>> bfs;
 
		bfs.push({ 0,0 });
 
		while (!bfs.empty())
		{
			int y = bfs.front().first;
			int x = bfs.front().second;
 
			if (y == 1 && x == n-1)
				break;
 
			bfs.pop();
 
			for (int i = 0; i < 8; ++i)
			{
				if (y + dy[i] < 0 || y + dy[i] >1 || x + dx[i] < 0 || x + dx[i] == n)
					continue;
 
				if (field[y + dy[i]][x + dx[i]] == 0)
				{
					if (visited[y + dy[i]][x + dx[i]])
						continue;
 
					bfs.push({ y + dy[i], x + dx[i] });
					visited[y + dy[i]] [x + dx[i]] = true;
				}
			}
		}
 
		if (bfs.empty())
			cout << "NO\n";
 
		else
			cout << "YES\n";
	}
}

 

    아래는 같이 스터디를 하는 기만러 Dreamw 님의 코드인데 허락을 구하고 글에 첨부했다. 오른쪽 부분이 아예 막혀있는지 확인하는 코드인데 나랑은 다르게 짧고 예쁘게 짠 걸 확인할 수 있다.

 

#include <bits/stdc++.h>
#define endl "\n"
#define MAX 100001
#define INF 1e9+7
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>
#define ll long long
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int tt;
    cin >> tt;
    while(tt--){
        int n, flag=0; cin >> n;
        string s1, s2; cin >> s1 >> s2;
        for(int i=1; i<n; i++){
            if(s1[i]-48 && s2[i]-48){
                flag=1;
                break;
            }
        }
        cout << (flag?"NO":"YES") << endl;
        
    }
 
    return 0;
}

 

 

B : Groups (0:43 - 대회 끝나고 5분 뒤에 AC 받음 ㅠㅡㅠ)

---

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t, n, input;
	bool flag;
	vector<int> student;
	vector<int> day_count;

	cin >> t;

	while (t--)
	{
		flag = false;

		cin >> n;

		if (n % 2 == 1)
		{
			cout << "NO\n";
			continue;
		}

		student.assign(n, 0);
		day_count.assign(5, 0);

		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < 5; ++j)
			{
				cin >> input;

				if (input == 1)
				{
					++day_count[j];
					student[i] += 1 << j;
				}
			}
		}

		for (int i = 0; i < 5 && !flag; ++i)
		{
			if (day_count[i] >= n / 2)
			{
				vector<int> count(5, 0);
				vector<int> both(5, 0);

				for (int j = 0; j < 5 && !flag; ++j)
				{
					if (i == j)
						continue;

					for (int k = 0; k < student.size(); ++k)
					{
						if ((student[k] & 1 << j) == 1 << j)
						{
							if ((student[k] & 1 << i) == 0)
								++count[j];

							else if ((student[k] & 1 << i) == 1 << i)
								++both[j];
						}
					}
				}

				for (int j = 0; j < 5 && !flag; ++j)
				{
					if (i == j)
						continue;

					int supplement = n / 2 - count[j];

					if (count[j] >= n / 2)
						flag = true;

					else if (both[j] >= supplement && day_count[i] - n / 2 >= supplement)
						flag = true;
				}
			}
		}

		if (flag)
			cout << "YES\n";

		else
			cout << "NO\n";
	}
}

 

    아래는 마찬가지로 같이 스터디를 하는 기만러 Dreamw 님의 코드인데 허락을 구하고 글에 첨부했다. 나와는 달리 조건이 깔끔하다. i 번 요일과 j 번 요일이 모두 안 되는 학생이 있다면 건너뛰고, 하나라도 된다면 각각 cnt1, cnt2 에 1을 더해서 가능한 학생 수를 집계한다. 이렇게 집계된 값이 둘 다 n/2 보다 크거나 같다면 가능하다고 판단하여 "YES"를 출력한다.

 

#include <bits/stdc++.h>
#define endl "\n"
#define MAX 100001
#define INF 1e9+7
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>
#define ll long long
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int tt;
    cin >> tt;
    while(tt--){
        int n; cin >> n;
        bool arr[1001][5]={0};
        for(int i=0; i<n; i++){
            for(int j=0; j<5; j++) cin >> arr[i][j];
        }
        int cflag=0;
        for(int i=0; i<4; i++){
            for(int j=i+1; j<5; j++){
                
                int cnt1=0, cnt2=0, flag=0;
                for(int k=0; k<n; k++){
                    if(!arr[k][i] && !arr[k][j]){
                        flag=1; break;
                    }

                    if(arr[k][i]) cnt1++;
                    if(arr[k][j]) cnt2++;
                }

                if(flag) continue;

                if(cnt1>=n/2 && cnt2>=n/2){
                    cflag=1;
                    break;
                }
            }
        }

        cout << (cflag?"YES":"NO") << endl;
    }

    return 0;
}

 

 

비고

---

    Tistory로 블로그 이전하면서 글들을 보기 좋게 정리하고 있는데 B번까지만 정리하고 게시한 글인 것 같다.