Post

백준 10944 랜덤 게임~~ 문제 풀이

Posted
By Park "ShapeLayer" Jonghyeon
5 min read
백준 10944 랜덤 게임~~ 문제 풀이

백준 온라인 저지, 10944번: 랜덤 게임~~

도입

채점 프로그램이 랜덤으로 선택하는 1부터 10,000 사이의 정수를 맞추는 문제이다. 채점 프로그램은 수를 매번 랜덤으로 제시하므로 매 제출은 1/10000, 0.01% 확률로 통과할 수 있다.

이 문제를 통과하기 위해서는 가능한 한 많은 답안을 제출해야 한다. 백준 온라인 저지는 당일 누적 제출 횟수 $S$에 대하여 $10 \times ( \lfloor S / 50 \rfloor + 1 )$ 초의 제출 시간 간격 제한이 있으므로, 제출을 거듭할 수록 대기해야 하는 시간이 길어진다.

더 나아가 문제의 채점 우선 순위는 3이다. 채점 순위 3 에는 재채점도 속해있어서, 상당한 제출을 가지고 있는 문제가 재채점되면 며칠이 지나도 채점 결과를 확인하지 못할 수도 있다.

풀어보기

1e-4의 확률을 독립시행하였을 때, 70%의 상황에서 1만2천회 전후의 제출로 문제를 통과할 수 있다. 직접 1만2천회의 제출을 시도하는 것은 꽤 끈기를 요구하는 일이다. 이에 더해 제출 시간 간격 제한이 있으므로, 사실 직접 제출로 문제를 해결하는 것은 불가능하다.

일반적으로 매크로의 사용은 부적절한 것으로 여겨지나, 이 문제는 매크로의 사용이 의도되는 것으로 보인다. 따라서 Tampermonkey 유저스크립트 확장을 통해 간단한 매크로를 작성하여 사용한다.

답안

유저스크립트 파트 1: 문제 제출 페이지로의 접근을 감지하면, 답안을 작성하고 제출한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

// ==UserScript==
// @name         10944 Random Game Random Submitter (Submit Part)
// @namespace    https://jonghyeon.me
// @version      1
// @description  Baekjoon Online Judge Random Game Random Submitter (Submit Part)
// @author       ShapeLayer
// @match        https://www.acmicpc.net/submit/10944
// @grant        none
// @run-at       document-end
// ==/UserScript==

function submitCode() {
  var newForm = document.createElement('form')
  newForm.id = 'newForm'
  newForm.method = 'post'
  var input__code_open = document.createElement('input')
  input__code_open.name = 'code_open'
  input__code_open.value = 'open'
  newForm.appendChild(input__code_open)
  var input__csrf_key = document.createElement('input')
  input__csrf_key.name = 'csrf_key'
  input__csrf_key.value = document.getElementsByName('csrf_key')[0].value
  newForm.appendChild(input__csrf_key)
  var input__language = document.createElement('input')
  input__language.name = 'language'
  input__language.value = '58'
  newForm.appendChild(input__language)
  var input__problem_id = document.createElement('input')
  input__problem_id.name = 'problem_id'
  input__problem_id.value = '10944'
  newForm.appendChild(input__problem_id)
  var input__source = document.createElement('input')
  input__source.name = 'source'
  input__source.value = '10'
  newForm.appendChild(input__source)

  document.getElementsByTagName('body')[0].appendChild(newForm)
  newForm.submit()
}

(function() {
  submitCode()
})()

유저스크립트 파트 2: 답안 제출 후 리다이렉트되는 채점 현황 페이지를 감지하면, 제출 시간 간격 제한만큼 대기한 후 다시 답안 제출 페이지로 리다이렉트한다. 답안 제출 페이지로 리다이렉트되면, 파트 1 스크립트가 작동하여 답안을 제출한다. 이 과정을 반복하여 많은 양의 답안을 제출한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// ==UserScript==
// @name         10944 Random Game Random Submitter (Redirection Part)
// @namespace    https://jonghyeon.me
// @version      1
// @description  Baekjoon Online Judge Random Game Random Submitter (Redirection Part)
// @author       ShapeLayer
// @match        https://www.acmicpc.net/status?*problem_id=10944*
// @grant        GM_setValue
// @grant        GM_getValue
// @run-at       document-end
// ==/UserScript==

(function() {
  const now = new Date()
  const key = now.getFullYear() + ' ' + now.getMonth() + ' ' + now.getDate()
  var nowTried = GM_getValue(key, 0)
  GM_setValue(key, nowTried+1)
  console.log(key + ' tried: ' + nowTried + ', delayed: ' + 10*((nowTried/50)+1)*1000)
  setTimeout(() => {window.location.href='https://www.acmicpc.net/submit/10944'}, 10*((nowTried/50)+1)*1000)
})();

마무리

이 문제 해결에 얼마나 많은 양의 답안을 제출했는지는 확인하지 않았다. 다른 문제들의 재채점이 활발하게 이루어져, 대략 보름 정도가 지나서 통과를 확인하였다.

ps
ps baekjoon algorithm