Codeforces Round 865 (Div. 2) - B. Grid Reconstruction (1000)

B. Grid Reconstruction

개인적으로 좀 생각이 필요했던 문제이다.

기본적으로 $2 \mid (i+j)$ 라면 $[n+1,2n]$ 의 큰 수들을 채워넣고, 그렇지 않다면 $[1,n]$ 의 작은 수들을 채워넣는 것이 좋아보인다.

이런 문제는 증명은 어렵지만 적당히 이렇게 하면 되겠다 하고 직관을 잡고 푸는 문제이다.

$(1,1) \to (2,n)$ 까지 가는데는 총 $n$ 개의 경로가 존재한다.

$n=3$ 이고

$(1,1) \to (1, 2) \to (2,2) \to (2,3)$과

$(1,1) \to (2,1) \to (2,2) \to (2,3)$ 이 있다고 하자.

경로들 중 내려가는 위치가 하나만 차이나는 인접한 경로끼리 경로에서 차이나는 부분은

$(1,2)$ 와 $(2,1)$ 임을 볼 수 있고, 이를 좀 더 일반화하면 $\pm(a_{1,k}-a_{2,k-1})$ 이다.

따라서 이것을 동일하게 유지시키는 것이 모든 경로들을 동일한 합을 갖게 만드는 방법임을 알 수 있다.

그리고 동일한 합일때가 가장 최소가 최대가 되는 지점이 될 것이다.

void solve() {
   int n;
   cin >> n;
   vvi ans(2, vi(n));
   vector<array<int, 3>> even, odd;
 
   int val = 2 * n - 1;
   for (int i = 0; i < n; i += 2) {
      ans[0][i] = val;
      val -= 2;
   }
   val = 2;
   for (int i = 0; i < n; i += 2) {
      ans[1][i] = val;
      val += 2;
   }
   val = 2 * n;
   for (int i = n - 1; i >= 0; i -= 2) {
      ans[1][i] = val;
      val -= 2;
   }
   val = 1;
   for (int i = 1; i < n; i += 2) {
      ans[0][i] = val;
      val += 2;
   }
 
   for (int y = 0; y < 2; y++) {
      for (int x = 0; x < n; x++) {
         cout << ans[y][x] << ' ';
      }
      cout << endl;
   }
}