sgc109

/*
https://community.topcoder.com/stat?c=problem_statement&pm=11204

탄것과 덜익은것을 하나의 벡터에 담아서 X값으로 정렬했을때
맨왼쪽이 탄것이거나 맨오른쪽이 덜익은것이면 무조건 불가능하고
만약 아니라면, 한가지 사실을 파악해야한다. 양끝의 두개를 제외했을때
모든 탄 빵은 맨왼쪽에있던 덜익은 빵과 매치시킬수있고 
모든 덜익은 빵은 맨 오른쪽에 있던 탄 빵과 매치 시킬수가있으므로 답은 2보다 커질수가없다. 그런데 딱 한 경우에 답이 1이 된다.
바로 모든 덜익은빵이 모든 탄빵보다 왼쪽에 있을 때 이다.

sgc109

/*
https://community.topcoder.com/stat?c=problem_statement&pm=11233

그냥 재귀함수로 구현하면된다
인자로는 상하반전여부와 색반전여부 그리고 남아있는 왼쪽끝과 오른쪽끝만 가지고있으면된다
왜냐하면 공을 빼도 양 끝으로만 빠져나가기 때문에 가운데는 그대로 남아있게 되기떄문에 좌 혹은 우로 한칸씩만 변하게 되기때문이다.
시간 복잡도는 O(N) 즉 10만번정도 돈다.
*/

#include <bits/stdc++.h>

sgc109

/*
https://community.topcoder.com/stat?c=problem_statement&pm=11334

처음엔 상태들을 잘 정의한뒤 그래프를 형성해서 다익스트라를 돌리는 식으로 풀 수가 있을 거라고 생각했는데
쉽지않았다. 아마 지금까지 그렇게 풀었던 문제들은 문제에서 주어진 경로대로 이동하는 것이 아니라
출발지와 도착지만 주어지고 출발지에서 도착지로 이동하는 가장 적은 비용을 묻는 문제였던것같고
이 문제는 경로가 주어지고 반드시 그 경로대로 이동해야 하면서 한정된 자원이 존재할 때에 최소 비용을 구하는 문제이다.
그래서 이 문제는 network flow graph 로 풀 수가 있고 최소 비용을 찾아야 하기 때문에 mcmf 로 풀 수가 있다.
우선 한가지 사실을 깨달아야 한다. 경로가 주어졌으니 k번째 도시가 출발지일때 k+1번째 도시는 도착지라고 볼 수가있다.
그렇다면 맨처음 0번도시에 있다는 것을 고려했을때 입력으로 주어진 도시들의 배열의 크기가 M 이라면

sgc109

/*
https://community.topcoder.com/stat?c=problem_statement&pm=11063

우선 Linearity of expectation 을 알아야 한다.
그니까 건설한 도로들의 길이의 총 합의 기대값은
각각의 도로의 길이의 기대값들의 총 합과 같다라는 것이다.
Editorial 에 있는 식을 인용하자면

Expected Length of all roads build after picking all villages =
Expected Length (Sum of lengths of the roads built when village i is picked, for all i) =

sgc109

/*
https://community.topcoder.com/stat?c=problem_statement&pm=11342

처음에 이 문제가 해석이 너무안돼서 방치해 놓다가 결국 날잡고 스스로 풀었다.
확률에 대한 이해와 숨겨진 규칙의 발견이 요구되는 문제라고 생각한다.
우선 가장 중요한 규칙을 발견해야하는데
맨 처음에 definite decisions 를 바탕으로 다른사람에게 선택된 수를 각각의 사람마다 세어보면
한 명에게도 선택되지 않은 사람은 0, 한 명에게 선택된 사람은 1, ... 이런식으로 가게되는데
선택된 횟수가 모두 0 또는 1이라면 다음번 round 에도 모두가 vulerable 해진다. 왜냐하면
definite decisions 에 포함 되지않은 나머지 사람들에 대해서는 현재 가장 적게 뽑힌 사람들을 랜덤하게 뽑게되는데

sgc109

/*
https://community.topcoder.com/stat?c=problem_statement&pm=11315

단순한 그리디+구현+자료구조 문제이다.
map 에 색을 key 값으로 개수를 세어준뒤 두개이상이 있는 색이있으면 무조건
마주보는 두 면에 쓰고 버리는게 이득이다.
그리고 서로 다른 색들은 아무렇게나 붙여도 된다.
*/

#include <bits/stdc++.h>

sgc109

/*
https://community.topcoder.com/stat?c=problem_statement&pm=11355

일단 몇가지를 캐치해야한다.
우선 맨윗줄은 변하지 않는다.
그리고 특정 줄은 무조건 바로 윗줄에 의해 영향을 받는다. 왜냐하면 문제에서 주어진 코드를 보면 색을 바꿔주는 순서를 알수있는데
특정 줄을 볼때는 이미 윗줄이 바뀐 상태이기 때문에 입력으로 주어지는 output상에서의 바로윗줄과 같은상태에서 영향을 받는것이다.
그리고나서 두가지를 잘 따져줘야한다.
첫번째는 W와 B 둘다 가능한 곳이 생기는 조건들
두번째는 특정 위치가 무조건 W나 B중 한가지 여야하는 조건들

sgc109

/*
우선 몇가지 발견해야 하는 규칙들은 앞의 풀이와 같고 조건들에 대해 모든 패턴을 따져주지 않아도 되는 구현도 간단하고 깔끔한 풀이가 있다.
반대로 뒤에서 부터 보는 것이다. 전에 뭐가 있었을지 모르는건 ? 라는 별개의 문자를 하나 정해서 표시를 해주고 BB 일경우
아래 두개를 실제로 swap을 해주며 WB 나 BW 일경우는 둘다 아래 두개를 ??로 바꿔주면 된다. WW일땐 가만히 두면된다.
그리고 마지막에 ?의 개수만큼 2를 곱해주면 된다. 물론 중간에 불가능한 경우를 따져줘야하는데 이건 WB일때와 BW일때 아래에 각각 B나 W가
하나라도 있으면 불가능한 경우이고 각각 W와 B는 있어도되고 ?는 둘다 언제든지 있어도 된다.
*/

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)

sgc109

/*
우선 1x1x1 큐브들과 LxLxL 큐브들의 부피의 총합을 구해보면
Ns+Nb*L^3 인데 이것을 T 라고 해보자. 그럼 적어도 우리가 이 큐브들을 포장하는 하나의 큐브의 부피 V는 T보다 크거나 같다.
그렇다면 T보다 크거나 같은 모든 V에 대해 검사해보자. 그런데 여기서 따져줘야 할 것이 세가지가 있다.
첫번째로 큐브의 모서리의 길이를 x,y,z 라고할때 x<=y<=z 관계를 유지해줘야 셌던것을 또 안센다. 회전하면 결국 같은게 나오기때문이다.
(그렇기 때문에 x^3 <= 2e9 일 것이다)
두번째로 지금 보는 V의 부피가 T보다 크다 할지라도 Nb개의 큐브가 모두 들어갈 수 없는 상황이 있다. 이것을 분리 해주기 위해서
LxLxL 큐브가 들어갈 수 있는 개수를 세어 줘야하는데 이것은 (x/L)*(y/L)*(z/L) 이다. 이것이 Nb보다 크거나 같은지를 봐주면된다.
세번째로 x와 y가 정해지면 x*y*z가 T보다 크거나 같아야하기때문에 최소 z가 정해질텐데
이 최소z부터 모든 가능한 z값을 다 봐주지 않아도 된다는 것이다. 딱 이거 하나만 봐주면된다. 그렇기 때문에 시간복잡도는

sgc109

/*
https://community.topcoder.com/stat?c=problem_statement&pm=11434

이 문제는 수학적 지식이 필요하다. 우선 문제에서 칸들이 K개가 있을 때 K의 약수이면서 소수인 수로 나눌 수가 있다고 했는데
이것은 바로 매 회에 소인수로 한번 나눌 수 있다는 것을 의미한다. 그렇기 때문에 소인수 분해를 했을 때 소인수들의 지수 들을 모두 더한 값이
최대한으로 나눌 수 있는 횟수인 것 이다. 그렇다면 우리가 특정 칸을 가져가기 위한 최소 횟수가 있다고 치면 그 최적해는
몇번은 나눌것이고 몇번은 옆으로 이동시킬 것이다. 우선 나누는 행위를 먼저 보면 각각의 소인수 마다 나누는 횟수가 있을 거고 그 횟수는 0일 수도 있을것이다.
그렇다면 각각의 소인수에 대하여 나누는 횟수들의 모든 조합에 대한 경우들을 모두 보면서
우리가 고르려고하는 놈이 맨 왼쪽 칸으로 부터 몇 만큼 떨어져 있는지 봐서 그중 최소 값이 답이 될것이다.
물론 맨 왼쪽 칸으로 부터 떨어진 거리는 min(좌측으로 갔을때 거리, 우측으로 갔을대 거리) 일 것이다.