IOI 2017 Nowruz는 output only 문제로, 코드를 실행해서 나온 결과를 제출하면 되는 종류의 문제이다. 문제를 요약하자면, 몇몇 칸이 막혀 있는 격자가 있을 때, 뚫려 있는 칸들만을 사용해서 리프의 수가 가장 많은 트리를 만들어 내면 되는 문제이다. 전부 뚫려 있는 입력 몇 개와, 적절히 장애물이 있는 입력 몇 개가 있다. 내 접근은 다음과 같다. 리프의 수가 가장 많은 트리를 만드는 가장 좋은 방법 중 하나는, 기존의 트리에 포함되어 있지 않은 정점 중 포함시켰을 때 리프가 되는 정점을 포함시키는 것이다. 장애물이 많지 않으므로, 잘못 리프를 넣어 망칠 확률도 적다. 이러기 위해서는, 한 정점을 시작점으로 잡은 뒤 모든 격자를 돌아보면서 리프가 될수 있는 정점을 찾은 뒤 리프로 만들어..
결과: 78점을 받으면서 37등을 했다. A번을 틀리고 시작한 것과 C번을 푸는데 너무 오래 걸린 것이 아쉽다. 풀이: A번: Arithmetic Square: 중앙이 비어있는 3*3 배열 중앙에 수를 넣어서 가로, 세로, 대각선 방향으로 등차수열을 최대한 많이 만드는 문제이다. 중앙에 모든 수를 넣어 보면 서브태스크 1을 풀 수 있지만, 2에서는 시간초과가 난다. 2를 풀기 위해서는, map에다가 등차수열을 만들 수 있는 수와 그 때 만들어지는 등차수열의 개수를 저장한 뒤, 만들어지는 개수 중 최댓값에다가 가장자리 4개 중 등차수열을 만드는 개수를 더해주면 된다. 등차수열을 만들 수 있는 중앙 수는 총 4개이고, 중앙을 지나는 선들을 보며 찾을 수 있다. x가 반정수가 되는 경우를 처리하지 않아서 1틀..
ABC 209를 봤고, 5문제를 풀었다. A번: 단순한 계산 문제이다. A>B인 경우를 생각 안 해서 한 번 틀렸다. #include #include #include #include #include #include using namespace std; vectorlink[200100]; int arr[200100]; int d[200100]; int p[200100][20]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int T,N, M, a, b, c; cin >> N >> M; vectorx; int i; cout > N >> M; vectorx; int i; for (i = 0; i > a..