A Leap Day

문제 easy : https://codeforces.com/problemset/problem/1718/A1 hard : https://codeforces.com/problemset/problem/1718/A2 길이 \(n\)인 배열 \(a\)가 있다. 다음의 연산으로 배열 \(a\)의 모든 원소의 값을 0으로 만들어야 한다. 두 인덱스 \(l,r\)과 0 이상의 정수 \(x\)를 선택한다. (단, \(1 \le l \le r \le n\) ) \(l \le i \le r\)을 만족하는 모든 \(i\)에 대하여, \(a_i := a_i \oplus x\)을 수행한다. 이 때 연산 수행 시간은 \(\lceil {r-l+1 \over 2} \rceil \)초이다. 연산을 이용하여 배열 \(a\)의 모든 원소의..

문제 : https://codeforces.com/problemset/problem/1672/E 메모장에 \(n\)개의 단어가 있고, 각 단어의 길이 \(l_i\)는 최대 2000을 넘지 않는다. 본 문제에서는 \(n\)만 주어지고, \(l\)은 주어지지 않는다. 메모장은 각 단어 사이를 공백으로 구분하여 보여준다. 이 때 메모장의 너비를 \(w\)라 하면, 메모장은 한 줄에 표시되는 단어들의 길이 합이 \(w\)를 넘지 않도록 표시한다. 즉 메모장의 첫 번째 줄의 경우, \(l_1+1+l_2+1+\cdots +1+ l_x \le w\)를 만족하고 두 번째 줄도 \(l_{x+1}+1+l_{x+2}+1+\cdots +1+ l_y \le w\)를 만족한다. 메모장의 너비가 \(w\)일 때, 메모장은 단어들을..

문제 : https://codeforces.com/problemset/problem/1081/F 길이가 \(n\)이고, 0과 1로만 이루어진 문자열 \(s\)가 있다. 그리고 \(s\)의 길이 \(n\)과 함께, \(s\)에서 1의 개수인 \(t\)가 주어진다. 인터렉션을 이용하여 \(s\)를 구하는 문제 인터렉션 ? \(l\) \(r\) \(s\)에서 구간 내에 있는 모든 0은 1로, 모든 1은 0으로 플립된다. 이 때 구간은 \([1,r]\) 혹은 \([l,n]\), 두 구간 중 하나가 랜덤으로 선택된다. 이 때 해당 구간이 선택될 확률은 둘다 0.5다. 플립 후 \(s\)에 있는 1의 개수 \(t'\)를 입력받을 수 있다. 플립 된 \(s\)는 원상복귀 되지 않는다. 인터렉션은 최대 1만 번 수행할..

문제 : https://codeforces.com/problemset/problem/1666/I \(n \times m\) 그리드가 있다. \(nm\)개의 셀 중 두 개의 보물이 파묻혀 있다. 인터렉션을 이용하여 두 개의 보물을 찾는 문제 인터렉션 SCAN \(r\) \(c\) 보물과 \((r,c)\)의 Manhattan distance 합을 입력받을 수 있다. 즉, 두 보물이 파묻힌 좌표가 각각 \((y_1,x_1),(y_2,x_2)\)일 때, \(|x_1-c|+|x_2-c|+|y_1-r|+|y_2-r|\)을 입력받을 수 있다. 두 보물 중 하나 이상을 찾은 경우라도, 두 보물의 원래 좌표와의 거리 합을 입력받는다. DIG \(r\) \(c\) \((r,c)\)에서 보물을 찾는다. \((r,c)\)가 ..

문제 : https://codeforces.com/problemset/problem/1665/D 양의 정수 \(x\)가 있다. 서로 다른 양의 정수 \(a,b\)를 이용하여 인터렉션을 수행할 수 있다. 인터렉션을 수행하면, \(\gcd(x+a,x+b)\)의 값을 입력받을 수 있다. 인터렉션을 이용하여 정수 \(x\)를 찾는 문제 제약사항 \(1 \le x \le 10^9\) \(1 \le a,b \le 2 \cdot 10^9 \) \(a \ne b \) 인터렉션은 테스트 케이스당 최대 30번 수행 가능 풀이 더보기 \(a=2, b=4\)로 지정 후 인터렉션을 수행하자 \(x\)가 짝수라면, \(\gcd(x+a,x+b)\)는 2가 나오고, \(x\)가 홀수라면, \(\gcd(x+a,x+b)\)는 1이 나올..

문제 : https://codeforces.com/contest/1687/problem/C 길이가 \(n\)이면서, 정수로 이루어진 두 배열 \(a\)와 \(b\)가 있다. 구간 \([l,r]\)에 대하여, \(a[l...r]\)의 값을 \(b[l...r]\)의 값으로 바꿀 수 있는 연산을 수행할 수 있다. 단 연산 이후, \(\sum_{}^{}a\)의 값은 변하면 안된다. 연산을 수행하기 위한 \(m\)개의 구간 \(l_i\)와 \(r_i\)가 주어진다. 주어진 \(m\)개의 구간에서만 연산을 할 수 있다고 할 때, \(a\)를 \(b\)로 바꿀 수 있는지 찾는 문제 주어진 구간 순서대로 연산을 수행할 필요는 없으며, 해당 구간의 연산을 0번 혹은 2번 이상 수행해도 상관없다. 제약사항 \(n\)과 \..