어제 저녁 8시에 열린 매치..~
이번 매치를 통해서 거의 2년전에 찍었던 역대 최고 rating을 깼다.. 푸하하
250은 삽질끝에 간신히 풀어내고.. 500은 왠지 greedy로 푸는사람이 있을것같아서..
미리 챌 데이타를 만들어 둔게 도움이 됐다..






Level1 - UnfoldingTriangles
주어진 그림에서 만들 수 있는 최대 직각 이등변 삼각형의 크기를 구하기.. 여기서 크기라함은 차지하고있는 cell의 개수이다.. 단 직각삼각형의 빗변은 모두 '/' 이어야 하고 내부는 모두 '#' 이어야 한다.. 그리고 직각삼각형의 임의의 선분이 외부의 '#' 와 만나서는 안된다.. '/' 로 되어있는 cell 은 최대 unfoldLimit 개 만큼 '#' 로 만들 수 있다..

처음에 문제를 보고 좀 어리둥절 했으나.. 그냥 brute force로 풀면 된다는것을 간파..~
일단 직각삼각형을 생각하면 어려우므로 가장 큰 정사각형을 고려한다.. (그걸 반으로 자르면 원하는 답이 됨)

임의의 cell에 대해서 정사각형의 upper left 와 lower right 점을 찍어서 가능한지 모두 체크한다..

1. 정사각형의 오른쪽 윗부분은 아무 종류의 cell이어도 상관없고..
2. 대각선에 걸치는 cell은 모두 '/' 이어야 한다..
3. 그리고 오른쪽 아래는 '#' 이어야 하고 '/' 일 경우 fold 를 하나 쓰게 된다..
4. 마지막으로 이 정사각형 오른쪽과 아래쪽 경계 외부에 이웃한 cell은 모두 '#' 이 아니어야 한다..

이렇게 만들 수 있는 정사각형 중 가장 큰게 답이 된다..
코드에 고심한 흔적이 철철 넘치지 않는가..?

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 //#define min(x, y) ((x) > (y) ? (y) : (x))
  8 #define max(x, y) ((x) > (y) ? (x) : (y))
  9 //#define INF 999999999
 10
 11 class UnfoldingTriangles {
 12 public:
 13
 14 int solve(vector <string> grid, int unfoldLimit)
 15 {
 16     int max1;
 17     int row, col;
 18     int i, j, k, l, m;
 19     int fl, cnt;
 20     row = grid.size();
 21     col = grid[0].size();
 22     max1 = -1;
 23     for (i = 0; i < row; i++) {
 24         for (j = 0; j < col; j++) {
 25             for (k = 0; i+k < row && j+k < col; k++) {
 26                 fl = 1;
 27                 cnt =0;
 28                 for (l = 0; l <= k; l++) {
 29                     for (m = 0; m <= k; m++) {
 30                         if (k-l == m) {
 31                             if (grid[i+l][j+m] != '/') {
 32                                 fl = 0;
 33                                 break;
 34                             }
 35                         }
 36                         else if (k-l > m) {
 37                             // antl
 38                         }
 39                         else {
 40                             if (grid[i+l][j+m] == '.') {
 41                                 fl = 0;
 42                                 break;
 43                             }
 44                             else if (grid[i+l][j+m] == '/') {
 45                                 cnt++;
 46                             }
 47                         }
 48                     }
 49                     if (fl == 0)
 50                         break;
 51                 }
 52                 if (fl) {
 53                     l = i+k+1;
 54                     for (m = 0; l < row && m <= k; m++) {
 55                         if (grid[l][m+j] == '#') {
 56                             fl = 0;
 57                             break;
 58                         }
 59                     }
 60                     m = j+k+1;
 61                     for (l = 0; l <= k && m < col; l++) {
 62                         if (grid[l+i][m] == '#') {
 63                             fl = 0;
 64                             break;
 65                         }
 66                     }
 67                 }
 68                 if (fl && cnt <= unfoldLimit) {
 69                     max1 = max(max1, (k+1) * (k+2) / 2);
 70 //printf("(%d, %d) k = %d, cnt = %d\n", i, j, k, cnt);
 71 //printf("max1 = %d\n", max1);
 72                 }
 73             }
 74         }
 75     }
 76 printf("ret = %d\n", max1);
 77 if (max1 == 0)
 78     max1 = -1;
 79     return max1;
 80 }
 81
 82 };



Level2 - FourBlocks
하나의 16점짜리 4 by 4 block이 있고 하나에 1점짜리 1 by 1 block이 있다.. 주어진 board에서 이미 채원지는거는 어쩔수 없고 빈 공간을 이 두가지 block으로 채워서 최대 많은 점수를 먹기..



to be updated..



Level3 - AvoidFour



to be updated..


to Top