ACM - 뱀

[2018-06-12]

링크: https://www.acmicpc.net/problem/10875

뱀의 모든 좌표를 한개씩 저장하게되면 약 40PB가 필요하다. 메모리 제한에 걸린다. 좌표를 하나씩 보는 것이 아닌 직선 정보처럼 양끝점을 가지고 있고, 뱀이 이동하면서 그러한 직선들이 계속 갱신되거나 합쳐진다면 뱀의 좌표들을 저장할 공간을 상당히 많이 줄일 수 있을것이다. 어차피 뱀은 수평방향과 수직방향으로만 이동하기 때문에, 방향성을 고려하지 않고 수평방향과 수직방향에 대한 정보를 map으로 저장했다. 최대 L*2(200MB)크기 만큼의 메모리가 필요하기에 주어진 조건에 맞다.

※ 더 최적화 할 수 있는 방법
직선이 아닌 사각형 형태로 저장할 수 있다면, 메모리를 더 줄일 수 있을거 같다. 문제는 사각형을 어떠한 기준으로 나눌 것인가 이다. 추후에 이 방법으로 풀어보려고 한다.

GCC 컴파일러와 VC++ 컴파일러의 Associative container (set, map)의 Iterator 처리 차이점

• Content

VC++은 연관 컨테이너인 set과 map에서 iterator 변수가 begin()인 시작 iterator를 가지고 있을때, -- 연산자를 하게되면 end() 로 가게된다.

GCC는 end()가 아닌 바로 그 전의 주소값을 접근한다. (잘못된 메모리 접근)

• Ex

std::set<int> s;
std::map<int, int> m;

bool sb = false;
bool mb = false;

s.insert(2);
s.insert(3);

auto iter1 = s.begin();

iter1--;

sb = iter1 == s.end();

m[1] = 2;
m[2] = 3;

auto iter2 = m.begin();

iter2--;

mb = (iter2 == m.end())