(200617) 코드포스

Codeforces materials usage license (v. 0.1) 에 따라 codeforces.com 의 문제임을 알립니다.

Original problem link: Problem - 1366C - Codeforces


INPUT

4
2 2
1 1
0 1
2 3
1 1 0
1 0 0
3 7
1 0 1 1 1 1 1
0 0 0 0 0 0 0
1 1 1 1 1 0 1
3 5
1 0 1 0 0
1 1 1 1 0
0 0 1 0 0

OUTPUT

0
3
4
4

풀려고 하는 문제 먼저 올려요.
저는 4세트 남아서 마저 끝내고 씻고 풀기 시작하겠습니다.

이건 뭐…문제 이해하기도 어렵네여

12시 30분부터 풀어서 막 accept 됬네요.

예리도가 정말 많이 떨어진 것 같아요.
솔루션은 바로 떠올랐는데 스파게티 만들다가 그냥 밀고 다시 짰네요. ㅋㅋ

1366C 답
#include <iostream>

using namespace std;

namespace {
  constexpr int kMaxDistance = 30;
}  // unnamed namespace

int cell_count[kMaxDistance];
int true_count[kMaxDistance];

int main(int argc, char** argv)
{
  ios::sync_with_stdio(false); 
  cin.tie(NULL);

  int test_case;
  cin >> test_case;

  while (test_case--) {
    int n, m;
    
    cin >> n >> m;

    for (int i = 0; i < kMaxDistance; ++i) {
      cell_count[i] = 0;
      true_count[i] = 0;
    }

    int max = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        int dummy;
        cin >> dummy;

        int distance = ((i + j) < (n - 1 - i + m - 1 - j)) ? (i + j) : (n - 1 - i + m - 1 - j);
        max = distance > max ? distance : max;
        ++cell_count[distance];
        true_count[distance] += dummy;
      }
    }

    max -= !((n & 0x01) ^ (m & 0x01));

    int ans = 0;
    for (int i = 0; i <= max; ++i) {
      ans += ((true_count[i] < (cell_count[i] - true_count[i])) ? true_count[i] : cell_count[i] - true_count[i]);
    }

    cout << ans << endl;
  }
  return 0;
}

이건 오렌지 코더의 4배 빠른 답안, 적어놓고 복기는 주말에 갑니다.
https://codeforces.com/contest/1366/submission/83398235

1 Like

@sh 님은 이미 이해하셨지만… ㅎㅎ 적어놓자면요.

문제 해석?

NxM 크기 맵에서 0,0에서 n.m으로 가는 모든 경로를 펠린드롬으로 만드는데 필요한 맵의 최소 수정 횟수 구하라는 문제입니다.
펠린드롬은 eye나 level 처럼 거꾸로 읽어도 같은 단어가 나오는 것을 말합니다.

예제의 2x2 맵을보면
1 1
0 1
이고 111 101 두가지 경로가 나오죠. 111과 101은 이미 펠린드롬이니 맵의 최소 수정 횟수는 0이죠.

1336C outersky의 답
#include <iostream>
#include <vector>

#define min(a,b) (((a)<(b))?(a):(b))

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;
		vector<pair<int, int>> vec((n + m - 2) / 2 + 1, { 0,0 });
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				int num;
				cin >> num;
				int pos = min(i + j, n + m - i - j - 2);
				if (num) vec[pos].second++;
				else vec[pos].first++;
			}
		}
		int ans = 0;
		for (int i = 0; i < vec.size(); i++) {
			if (i != vec.size() - 1 || (n + m) % 2)
				ans += min(vec[i].first, vec[i].second);
		}
		cout << ans << '\n';
	}
}
1 Like