kjk9704   1년 전

비록 아직 AC 판정을 받지 못 했으나 구현하는 과정에서 23가지 테스트 케이스가 등장하여 여기에 공유합니다.

Python(PyPy) 혹은 C++로 계속 도전하고 있긴 한데 자꾸 1% 혹은 7% 구간에서 틀리네요.

kjk9704   1년 전

TLE가 발생하는 주 원인은 성격의 종류가 매우 다양한 경우(테스트 케이스 20, 테스트 케이스 23)입니다.

이를 개선할려면 O(N*T)에서 O(N*log T)으로 개선되어야 하나 어떤 방법으로 개선되어야 하는지 잘 모르겠습니다.

추가로 이 문제는 이분 매칭으로 뭔가 아이디어를 떠올리면 가능성이 보일 것 같은데 음...

+ 테스트 케이스 2에서 (3, 8) <-> (1, 2)가 확실히 최적해가 맞다는 정보를 미리 알고 있다면

3 10
4 2
1 5
1 3

여기서 (4, 2) <-> (1, 5)로 7이라는 최적해를 구하고, 그 다음 아까 미리 최적해를 구했던 (3, 8) <-> (1, 2)로 10을 구하여 7 + 10 = 17로 유도가 됩니다.

즉, 어떤 수많은 데이터가 존재하는 경우 매트로이드 등을 통하여 일부 데이터 쌍이 확실한 최적해를 보장 받을 수만 있다면 분할 정복 형식으로 해결할 가능성이 보입니다.

과연 그 방법은 무엇일까요?

+ 원본 그래프 + 복사 그래프로 이분 매칭 + 그리디 적용하여 구할려고 하는데 자꾸 일부 테스트 케이스에서 어긋난 경우가 많이 생겨납니다.

모든 테스트 케이스가 일치하고 TLE 안 뜨면 AC 판정 받을 수 있을 것 같은데 와... 이 문제 뭘까요?

kjk9704   1년 전

@koosaga 이 문제를 해결한 구사과님한테 정중히 도움 요청합니다.

이 문제를 해결하기 위한 힌트가 무엇인지 여쭤봐도 괜찮을까요?

에디토리얼 없이 할려니 한계가 느껴집니다.

jh01533   1년 전

이런 걸 원하실진 모르겠으나 이 문제는 World Tour Finals 2022 Day2 C번의 번역본이고 공식 에디토리얼이 존재합니다.

문제 - https://atcoder.jp/contests/wt...

에디토리얼 - https://atcoder.jp/contests/wt...

kjk9704   1년 전

@jh01533 진심으로 감사합니다! 덕분에 Python3으로 AC 판정을 받았습니다! 님 아니었으면 이 문제 절대 해결하지 못 했을 것입니다.

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