글 읽기 - 통과된 제 코드가 잘못된 것 같은데 반례를 못찾겠습니다.

BaaaaaaaaaaarkingDog 3년 전 1

일단 아래는 제 코드이고 그리디로 해결했습니다. 설명을 간략하게 해보자면 우선 diff는 곽철용의 점수입니다. 23 to 27번째의 for문에서는 현재 k로 나눈 나머지가 i인 카드들을 봅니다. val에는 현재 k로 나눈 나머지가 i-diff-1 이하인 카드의 개수가 저장되어 있습니다.

그런데 저 코드에는 심각한 결함이 있는데, diff = 1이고 cnt[0] = 2, cnt[2] = 2, cnt[4] = 2라고 할 때 2점 이상을 낼 수 있는 경우의 수는 분명 3일텐데((0 4) (0 2) (2 4)), 저 코드의 로직 상으로는 ans = 4가 됩니다. cnt[2]가 cnt[0]이랑 묶여서 ans에 2가 더해지고, 이후 cnt[2]의 값을 빼주지 않기 떄문에 cnt[4]와 cnt[2]를 묶어 ans에 2가 더 추가됩니다. 즉 특정 수가 작은 쪽, 큰 쪽으로 두 번 쓰이는 사태가 벌어집니다.

그런데 정답 처리가 되었고 반례를 나름대로 고민해봤는데 전혀 떠오르지가 않습니다. 다른 분들의 풀이를 봐도 저와 같은 결함을 가지고 있거나 코드를 이해하기가 힘든 경우가 더러 있네요,, 혹시 비슷한 고민을 해보신 분이 있다면 이렇게 풀어도 수학적으로 맞는건지, 아니면 반례가 있는데 제가 못찾은건지 알려주실 수 있나요?

#include <bits/stdc++.h>
using namespace std;

int cnt[400005];

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,m,k;
  cin >> n >> m >> k;
  for(int i = 1; i <= 4*n; i++) cnt[i%k]++;
  for(int i = 0; i < 2*m; i++){
    int t;
    cin >> t;
    cnt[t%k]--;
  }
  int a,b;
  cin >> a >> b;
  int diff = abs(a%k - b%k);
  cnt[a%k]--; cnt[b%k]--;
  int ans = 0;
  int val = 0;
  for(int i = diff+1; i < k; i++){
    val += cnt[i-diff-1];
    ans += min(val, cnt[i]);
    val -= min(val, cnt[i]);
  }
  cout << min(ans, m-1);
}

sait2000 3년 전 0

일단 n = m이고 답이 m-1보다 작은데 실수로 m-1이 나오는 경우는 없습니다

그런 일이 일어나려면 남은 카드를 나머지 순으로 정렬했을때 어떤 연속한 m장은 '빽빽하게' 채워져서 최대와 최소의 차이가 diff 이하여야 합니다. 그러면 이 빽빽한 구간을 포함해 그 왼쪽 카드들은 최대 빽빽한 구간 왼쪽의 카드 개수만을 ans에 기여하고 오른쪽 카드들은 오른쪽 카드 개수만을 기여하므로 ans는 최대 m-2가 나옵니다

그 외에는 아직 잘 모르겠네요

shjohw12 3년 전 0

글에서 설명하신게 반례 아닌가요?

5 6 5
8 9
13 18
2 7
1 6
11 16
5 10
3 4

answer : 3

output : 4

BaaaaaaaaaaarkingDog 3년 전 0

@shjohw12

M이 N 이하여야한다는 조건이 있어서 지금 데이터는 잘못되었습니다.

코드가 어떤 경우에 문제가 된다는건 알겠는데 그 문제가 발생하게끔 데이터를 만드는게 쉽지 않았어서(N이 작을 때 DM도 돌려봤는데 반례가 잘 안나오더라구요) 어쩌면 수학적으로 반례가 없는건 아닐까 고민을 했었네요. 사실 아직도 잘 모르겠습니다.

shjohw12 3년 전 0

아 그러네요 랜덤 돌려봐도 반례가 안나오는 것으로 보아 위와 같이 풀어도 되는 것 같습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

통과된 제 코드가 잘못된 것 같은데 반례를 못찾겠습니다.

BaaaaaaaaaaarkingDog 3년 전 1

sait2000 3년 전 0

shjohw12 3년 전 0

BaaaaaaaaaaarkingDog 3년 전 0

shjohw12 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말