PS 방법 정리

솔루션을 제시하는 방법 : 기술

학생들과 함께 일하면서 종종 첫눈에 문제가 명확 해 보이지 않으면 해결할 수없는 상황에 직면합니다. 실제로, 당신은 항상 특정 방법과 기술에 대해 듣게됩니다. 그러나 당신은 그 (것)들을 적용하기 위하여 생각하는 방법에 관하여 듣지 않는다. 이 글에서는 프로그래밍 콘테스트 문제를 해결하는 경험을 요약 해 보겠습니다. 그러나 수학에 대한 올림피아드 및 학술 연구의 첫 번째 단계에 대한 조언도 제공됩니다.

그래서 당신은 문제를 읽고 그것을 해결하는 방법을 모른다. 다음 기술을 시도해보십시오. 그 중 일부는 종종 유용 할 수 있습니다.

기술 1 : "총 리콜"

해결해야 할 몇 가지 유사한 문제를 기억하십시오. 확실히 많은 문제는 새로운 아이디어를 가지고 있지 않습니다. 아마도 비슷한 문제를 푸는 경험을 사용하여이 문제를 해결할 수 있습니다.

기술 2 : "특정에서 일반으로"

문제에 대한 해결책을 찾았다 고 가정 해 봅시다 (만세!). 문제의 특별한 경우를 생각해 봅시다. 물론 알고리즘 / 솔루션을 적용 할 수 있습니다. 그렇기 때문에 일반적인 문제를 해결하기 위해 특정 사례를 모두 해결해야합니다. 일부 또는 여러 개의 특정 사례를 해결 한 다음 주 문제의 해결 방법으로 일반화하십시오. 이러한 특수한 경우는 문제의 단순화라고 볼 수 있습니다. 즉, 우리는 다음과 같은 원칙에 의해 추론 할 수 있습니다. "복잡한 문제를 해결하는 방법을 모른다면 단순화하고 단순화 된 솔루션을 찾을 것입니다. 번역".

단순화의 일반적인 예 (특정 사례) :

• 당신은 나무에 문제가 생깁니다. 나무가 경로로 퇴화하는 변종을 생각해보십시오.
• 문제는 가중치가 있습니까? 모든 가중치가 하나 또는 임의의 수와 같거나 두 개의 분명한 가중치 (및 기타 등등) 만있는 변형을 고려하십시오.

특정 케이스의 솔루션은 일반적으로 일반적인 솔루션보다 쉽지 않으므로 가능한 쉽고 효율적으로 솔루션을 찾으십시오.

기술 3 : "대담한 가설"

너에게 진실 된듯한 대담한 가설을 세우는 것을 부끄러워하지 말라. 컨테스트 중 솔루션을 증명할 필요가없는 경우 내부 직감을 살짝 누르십시오. 당신의 가설을 생각해 냈을 때 그것을 증명하려고 노력하십시오 - 그것은 잘 풀리거나 당신에게 그것을 반증하는 방법에 대한 아이디어를 줄 수 있습니다. 가설을 기반으로 한 솔루션을 구현할 때 그리고 가설을 반증 한 후에 만 ​​시간을 낭비하는 것은 고통이 될 수 있으므로 다양한 테스트 세트에 대한 가설을 테스트 해보십시오.

예 :

• 해결책은 항상 존재합니다.
• 항목 수는 크지 않습니다.

기법 4 : "문제를 해결하려면 문제라고 생각해야합니다"

나는 진지해, 문제의 성격을 나타내는 신발에 자신을 넣고, 입력 세트를 다루는 것이 자신의 직업이라고 상상해보십시오. 이 경우 어떻게 행동할지 생각해보십시오. 작은 샘플을 직접 처리하십시오. 문제가 게임에 관한 것이라면 게임하십시오. 때로는 더 나은 이해를 위해 프로세스 나 모델을 시각화하려고합니다. 영화가 과학자들의 사고 방식을 보여주는 것과 조금 비슷합니다. 이미지로 생각하고 솔루션을 상상해 보시고 펼쳐보십시오.

기술 5 : "함께 생각하라"

이 기술은 팀 콘테스트에만 적용됩니다. 2 ~ 3 명으로 구성된 그룹에서 문제에 대한 몇 가지 분명한 사실을 말하기 시작합니다. 예를 들어, "n이 짝수이면 대답은 항상 0입니다.", "n이 소수라면 해결책은 그렇게되어야합니다."등등. 때로는 팀원들이 아이디어를 얻고 개발하여이 전략을 통해 문제를 해결할 수 있습니다.

기법 6 : "방법 선택"

어떤 방식 으로든 문제에 적용 할 수있는 인기있는 알고리즘이나 방법을 시도해보십시오. 문제 제한을 보는 것이 유용합니다. 메소드를 선택했다면,이 메소드를 사용하여 문제가 해결되었다고 가정하고 솔루션을 생각해보십시오. 귀하의 추론은 다음과 같아야합니다 : "문제를 나누고 정복하여 해결한다고 가정 해 봅시다. 그러면 왼쪽과 오른쪽 절반에 대해이 문제를 재귀 적으로 풀어 봅시다. 이제 남은 것은 이러한 솔루션을 통합하는 방법을 찾는 것입니다. 우리가 어떻게 할 수 있는지 궁금해 ... "

기술 7 : "인쇄 및보기"

매우 자주 (특히 작은 입력 문제 : 1 / 2 숫자) 솔루션 구성에 몇 가지 패턴이 있습니다. 패턴을 보려면 때때로 문제를 푸는 간단한 방법을 쓰고 큰 한계에 대한 많은 수의 테스트에 대한 대답을 생성하고 잠시 동안 대답을 묵상해야합니다. 컴퓨터를 계속 사용하지 않으려면 얻은 결과를 인쇄하고 인쇄 시간에 명상하는 것이 좋습니다.

때로는 답을 인쇄 할뿐만 아니라 해결책을 얻는 방법과 같은 몇 가지 추가 정보를 인쇄하는 것이 좋습니다.

기법 8 : "Google"

이 기술은 라운드 / 컨테스트 규칙에서 허용하는 경우에만 사용할 수 있습니다. 문제가 시퀀스에 관한 것이라면 사이트 https://oeis.org/ 에서 솔루션 7 (기술 7 참조)을 찾을 수 있습니다 . 문제의 공식 모델을 이해하고 정확한 수학 용어를 Google에 알리는 데 도움이됩니다.

코드포스에 정리된 내용을 가져왔다.

번역기 번역

출처 : https://codeforces.com/blog/entry/20548