Codeforces Round #372 (Div. 1)

대회 링크

문제를 일일이 설명하기에는 제 필력이 딸립니다 ㅠㅠ 풀이(또는 생각)만 덜렁 적혀있더라도 이해해주세요...

A. Plus and Square Root (AC)

레벨 \(i\)에서 \(i+1\)로 넘어갈 때에 변수가 \((i(i+1))^2\)의 값을 가지고 가면 됩니다.

간단한 수학 문제였네요... 이런 걸 풀 때는 "느낌"으로 푸는 거라고 누가 그랬습니다 (?)

소스

B. Complete The Graph (못품)

비용이 0인 엣지를 다 끊어놓고 Dijkstra를 돌리나...? 일단 Dijkstra를 돌리고 0인 엣지가 포함된 것의 여부에 따라 어떻게 잘 처리를 하나...? 여러 생각을 해 보았는데 정말 아무 생각이 안 들어서 일단 넘겼습니다.

그리고 대회 끝날 때까지 다시 보지 않았습니다 ㅎㅎ

C. Digit Tree (못품)

"어려운 트리 분할정복 문제구나!"

라고 생각한 뒤 잠시 공황 상태에 빠졌습니다 ㅠㅠ

그러다가 혹시 몰라서 D를 봤는데....

D. Create a Maze (AC)

"수학 문제"의 느낌이 왔습니다. 정보 실력이 떨어지는 저로써는 이런 문제를 안 잡으면 잡을 문제가 없었기에 잡았습니다. 한 40분동안 열심히 삽질을 한 뒤 풀이같아 보이는 걸 생각해 냈습니다.

이런 식으로 생긴 모양을 만듭니다. (X자는 막힌 곳을 의미) 이렇게 되면 이제 원하는 수 \(T\)를 3진법으로 표현하여 각 자릿수 별로 그 자리가 \(0\)이라면 파란색과 초록색을 모두 닫고, \(1\)이라면 파란색만 열고(또는 초록색만), \(2\)라면 둘 다 여는 식으로 하면 결국 최종 목적지에 도달하는 경우의 수는 정확히 \(T\)가 됩니다. 정확히 이렇게 생긴 모양을 만들면 보드 크기가 \(41 * 41\), 최대 벽 사용 수가 \(299\)(!)로 문제 조건에 부합합니다.

짜서 냈더니 (중간에 디버깅 과정이 좀 있었습니다) pretest passed!가 뜨길래 그 순간에 팝콘을 뜯었습니다. 결국 맞았으니 잘 된 거죠 뭐 ㅎㅎ

소스

(*참고로 저 모양에서 벽을 좀 없앨 수 있습니다. 대회 중엔 몰랐는데 끝나고 나니 보이네요! (한 60개 정도?))

E. Complete the Permutations (못품)

D 생각하다가 잠깐 봤는데 너무 어려워 보여서 아무 생각을 하지 않았습니다....

소감

이번 라운드에서 어떻게 운이 잘 받쳐줬는지 수학문제인 A와 D를 풀어서 12등(???!???)을 했습니다!

레이팅이 298이나 올랐어요!!!! 우와!!

앞으로는 좀 더 정보틱한(?) 문제인 B와 C도 잘 풀 수 있도록 열심히 공부해야겠습니다!