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

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

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

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=11342

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

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=11334

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

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=11204

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