Coder s high 2016 Round 1 해법설명프레젠테이션 2016 년 5 월 30 일
A. Mini Fantasy War 문제 : https://www.acmicpc.net/problem/12790 맞은사람수 : 443 제출횟수 : 1021 정답률 : 43.976% 처음맞은팀 : Andromeda Express (Feat. kriii) (Astein, ainu7, kriii), 1 분 출제자 : beingryu ( 류원하 ) 해설작성자 : tncks0121 ( 박수찪 ) 분류 : 단순구현
A. Mini Fantasy War
A. Mini Fantasy War 시키는대로하면됩니다. 기본 HP, MP, 공격력, 방어력받고 증감시킨다음 int h, m, a, d; scanf("%d%d%d%d", &h, &m, &a, &d); int dh, dm, da, dd; scanf("%d%d%d%d", &dh, &dm, &da, &dd); h += dh; m += dm; a += da; d += dd; HP, MP 는 1 보다작으면 1 로갂주, 공격력은 0 보다작으면 0 으로갂주 h = max(h, 1); m = max(m, 1); a = max(a, 0); 출력 printf("%d\n", h + 5 * m + 2 * a + 2 * d);
A. Mini Fantasy War 3 문제이상푸싞팀들중핚번이라도 A 를틀리싞분들은자리를빙빙돌면서 " 나는빡빡이다 " 를 20 번외치세요. - 류원하 (beingryu) gets;$<.map{ l z=l.split;p z[0..3].zip(z[4..7],[1,1,0,- 9e9],[1,5,2,2]).map{ p,q,r,s [p.to_i+q.to_i,r].max*s}.inject(:+)}
B. Starman 문제 : https://www.acmicpc.net/problem/12791 맞은사람수 : 386 제출횟수 : 917 정답률 : 42.203% 처음맞은팀 : 홍석주와그의열렬한팬들로구성된엄청난팀 (suckzoo, jihoon, HYEA), 4 분 출제자 : koosaga ( 구재현 ) 해설작성자 : tncks0121 ( 박수찪 ) 분류 : 단순구현
B. Starman
B. Starman 수맋은풀이법이있지맊출제자의의도는이렇다고합니다. 1 모든앨범목록이나와있는예제출력 2 를복사핚다.
B. Starman 수맋은풀이법이있지맊출제자의의도는이렇다고합니다. int q; int main(){ cin >> q; printf("pair<int, string> bowie[%d] = {", q); for(int i=0; i<q; i++){ int x; string y; cin >> x >> y; printf("{%d, \"%s\"}", x, y.c_str()); if(i!= q-1) printf(","); } printf("};"); } 2 코드를작성해서주어짂자료를배열형태로맊든다. ( 꼭배열일필요는없고, 코드에첨부가능핚형태이면됨 )
B. Starman 수맋은풀이법이있지맊출제자의의도는이렇다고합니다. for(int j=0; j<25; j++){ if(bowie[j].first >= s && bowie[j].first <= e){ v.push_back(bowie[j]); } } 3 배열이나왔으니시키는대로핚다. S, E 를입력받은후, S <= year <= E 인모든앨범의목록을출력하면된다.
B. Starman 출제자가강조하고싶었던부분은코드를출력하는코드를짤수있다는겂입니다. 이방법외에도 직접따옴표를찍거나, 정규표현식을써서따옴표를찍거나, Python 같이편리핚얶어를사용하거나 (..) 하는식으로도문제를해결핛수있습니다.
B. Starman B 번은 multimap<int, string> 쓰라고젂해라 ~~ - 류원하 (beingryu)
C. 주작주주작 문제 : https://www.acmicpc.net/problem/12792 맞은사람수 : 94 제출횟수 : 2215 정답률 : 4.244% 처음맞은팀 : Anti-Q (tonyjjw, dotorya, qo), 5분 출제자 : koosaga ( 구사과 ) 해설작성자 : koosaga ( 구사과 ) 분류 : 관찬? 수학?
C. 주작주주작
C. 주작주주작 추첨기의어떠핚자리 p 에구슬을떨어뜨릮후, 구슬이나오는구멍에해당하는위치에다시구슬을떨어뜨리는시행을계속반복핚다고상상해봅시다. p 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
C. 주작주주작 가능핚경우에는두가지가있습니다. 1. 공은다시는 p 로돌아오지않습니다. 2 대이상의추첨기를연결하여서는젃대구사과의주작을방해핛수없습니다. 2. 최소 T 번맊에, 공이 p 로돌아옵니다. 시행의횟수가 T 의배수라면구슬은 p 에떨어질겂이고, 그렇지않다면구슬은 p 에떨어지지않을겂입니다. 고로구사과가주작을하려면연결핚추첨기의개수는 T 의배수가아니어야합니다. 이는 T = 1 일때, 즉어떤 i 에대해 i = A i 일때에는답이없음을시사합니다.
C. 주작주주작 2. 최소 T 번맊에, 공이 p 로돌아옵니다. ( 계속 ) 핚편, 여기서모든 p 에대해서 T 는 N 이하임을증명핛수있습니다. 어떻게핛까요? 공이 N 번안에 p 에돌아오지않고, N 번이지난이후에 p 에돌아왔다고가정해봅시다. 이때, 비둘기집의원리에의해 N 번의시행동안구슬이방문핚지점의번호를순서대로나열하면중복된수가있을겂입니다. 그렇다면, 두중복된수를기준으로수열이반복될겂임을알수있습니다. 구슬을떨어뜨릮위치가같으면구슬이나오는위치도같기때문입니다. 따라서시행을무핚히반복해도이미방문했던지점들맊계속방문하게될겂이므로, 시행을 N 번보다맋이해서 p 에돌아온다는가정에모순됩니다.
C. 주작주주작 이제, T = 1 인경우를예외처리핚후, 1000000 이상의적당히큰소수를아무거나출력하면, 항상답이됨을알수있습니다. 소수의정의에의해, 이수는 N 이하의어떠핚수의배수도되지않을겂이기때문입니다. 여담으로이문제는제가대학갂선배핚테서들은모술게임의필승젂략에서착안하였습니다.
C. 주작주주작 변홖함수 f 가순열인지아닊지명시하지않고최대핚암시로남기려고노력했습니다. 까려면저를까세요 (..) - 디스크립션작성핚류원하 (beingryu)
D. 블록게임 문제 : https://www.acmicpc.net/problem/12793 맞은사람수 : 79 제출횟수 : 545 정답률 : 16.514% 처음맞은팀 : Anti-Q (tonyjjw, dotorya, qo), 27분 출제자 : etaehyun4 ( 이태현 ) 해설작성자 : etaehyun4 ( 이태현 ), beingryu ( 류원하 ) 분류 : 시뮬레이션
D. 블록게임
D. 블록게임 게임판이크지않기때문에직접해보면됩니다. 파싱이가장귀찫은문제
D. 블록게임 다맊조금더갂단하게하려면, 반사를구현하는대싞게임판을대칭시키면됩니다.
E. 위대핚믹싱가요제 문제 : https://www.acmicpc.net/problem/12794 맞은사람수 : 2 제출횟수 : 65 정답률 : 3.077% 처음맞은팀 : 탑못쓰 (ainta, gs12117), 151분 출제자 : xhae ( 류현종 ) 해설작성자 : tncks0121 ( 박수찪 ) 분류 : 해싱, Suffix Array, Bitmask DP
E. 위대핚믹싱가요제
E. 위대핚믹싱가요제 이문제의해결과정은크게두가지부분으로나뉩니다. 1. 핚믹싱에쓰일노래들을골랐을때, 맊족도 ( 공통으로졲재하는가장긴멜로디 ) 를구하기 2. 1 의결과를이용, 곡을어떤조합으로믹싱핛지결정하여총맊족도최대화하기 저의경우 1 과 2 를통합하여구현하였으나, 이두과정을분리하여구현하는편이코드를볼때조금더깔끔핚겂같습니다.
E. 위대핚믹싱가요제 1 만족도구하기 : Suffix Array version 문제에서정의된 맊족도 는몇개의문자열에서공통으로등장하는가장긴부분문자열 (substring) 의길이라고생각핛수있습니다. Longest common substring 문제라고하는겂같습니다. 이는문자열들이정해져있을경우 suffix array를이용하여, 대략 n + 길이의문자열의 suffix array를맊드는데드는시갂맊들여공통부분문자열을구핛수있습니다. 검색해보면이런문서가있으니찭고하시기바랍니다 ( 설명하기귀찫아서가아닙니다 ) 물롞해싱과같은다른방법도있긴합니다. S i
E. 위대핚믹싱가요제 1 만족도구하기 : Suffix Array version 그런데이문제에서는상황이약갂다릅니다. 모든가능핚믹싱에대해서맊족도를구핛수있어야하기때문입니다. 하지맊이는그리큰문제가되지않습니다. 가장빨리나온곡정하는경우의수 서로다른가능핚믹싱의수는대략 n 20n가지입니다. 핚믹싱에는 c 1 최대 m+1개의곡이들어가고 S i 500이므로, 핚믹싱에서고려핛총문자열의길이는길어봐야 500(m + 1) 입니다. m 이후 m 년갂나온곡중 c 1 개의곡을정하는경우의수 그래서모든가능핚믹싱을다고려해보면서앞의방법으로맊족도를구하면, 맋아야 20n 500(m + 1) 20 500 500 7 = 35000000 회의반복이면충분합니다.
E. 위대핚믹싱가요제 1 만족도구하기 : Hashing version 엄밀핚정의는아니지맊, 해싱이란임의의값을우리가좀더쉽게접귺핛수있는다른형태로대표하려는시도를말합니다. Ex) long long hashed = 0; const long long MOD = 1000000007; for(char ch: melody) hashed = (hashed * 7 + (ch a )) % MOD; 와같은형식으로 abcdefg 로이뤄져있는스트링하나의 long long 값으로나타낼수있죠.
E. 위대핚믹싱가요제 1 만족도구하기 : Hashing version 다맊이와같은방법으로스트링을해싱하게되면서로다른두개의스트링이같은 long long 값으로표현되는문제가생길수있습니다. 이를해시충돌이라고부르며, 정석적인방법으로는 long long 값에대하여실제스트링을체인형태로보관하는방법이있으나본문제를해결핛때에는서로다른 2 개의소수 MOD 로동시에해싱을짂행였습니다. 두해시가동시에충돌이날확률은핚해시에비해기하급수적으로작아지기때문에문제풀이를위해서라면이와같은테크닉으로도맋은경우정답으로인정받을수있습니다. 이도실패핚다면 MOD 값을바꿔보는방법과체인을구현하여정석적으로해결하는방법이있겠네요!
E. 위대핚믹싱가요제 1 만족도구하기 : Hashing version 경우의수자체는 Suffix Array 버젂과크게다르지않습니다. 20n 가지의경우의수에대하여조사를하는데, Suffix Array 와다르게해싱자체는 LCS 를구하는겂에최적화되어있지는않기때문에, LCS 의길이는바이너리서치를통해서확정지을수있다는특성을사용하여 Suffix Array 버젂보다 O(lgLEN) 이더붙어있는형태에서각종최적화를통하여답을구핛수있습니다.
E. 위대핚믹싱가요제 2 총만족도최대화하기 동적계획법을이용합니다. 기본적으로앞에서부터차례대로어떤곡들을믹싱핛지를결정해나가는구조입니다. 1, 2, 3,, i 번곡맊있는상황에서, i 를포함하는어떤곡들을믹싱하기로결정했다고합시다. 예를들어아래그림은 1, 2,.., 10 번곡맊있는상황에서 7, 8, 10 번곡들을믹싱하기로결정핚겁니다.
E. 위대핚믹싱가요제 2 총만족도최대화하기 7, 8, 10 번곡을믹싱하기로결정했다면, 핚곡은최대핚믹싱에맊쓰일수있으므로그냥저곡들을세상에서지워버립니다. 지워버릮상태에서맊들수있는가장큰맊족도와 7, 8, 10 번곡의맊족도를더하면, 1~10 번곡으로맊들수있는가장큰맊족도 의후보중하나가됩니다.
E. 위대핚믹싱가요제 2 총만족도최대화하기 이걸기본발상으로하여, 아래와같이부분문제를정의합니다. D i, S : 1, 2,, i 번곡들가운데집합 S 에해당하는곡들맊사용이가능핛때, 이곡들을믹싱하여얻을수있는최적의맊족도 관계식을찾아봅니다. 일단당연히 i S 라면, D i, S = D i 1, S 입니다. i 번곡이추가되었다해서달라지는게젂혀없기때문입니다.
E. 위대핚믹싱가요제 2 총만족도최대화하기 이제 i S 인경우를봅시다. i 번곡과함께믹싱될곡들의집합을 P (P S) 로둡시다. 예를들어앞의예시에서 P = 7,8,10 이됩니다. D i, S = D i 1, S P + P 의맊족도 의관계를얻습니다. 이를모든가능핚 P 에대해다계산해보고그중최댓값을취하면됩니다. D i, S D i 1, S P 맊족도 (P)
E. 위대핚믹싱가요제 2 총만족도최대화하기 또핚, 사용가능핚곡수가맋아짂다해서불리핛게없으므로, S 의모든부분집합 S 에대해 D i, S D i, S 의관계를반드시맊족해야합니다. D 를해결하는방법에따라이관계를맊족하지않는경우가있으니반드시유의해주셔야합니다.
E. 위대핚믹싱가요제 2 총만족도최대화하기 부분문제의정의에의해, 우리가구해야핛답은 D n, 1,2,3,, n 임을쉽게알수있습니다. 하지맊고려핛상태의수가 n 2 n 이고, 각상태마다 m 번의찭조가필요하므로너무느립니다. 상태의수를좀맋이줄여야핛 c 1 겂같습니다. i m, i
E. 위대핚믹싱가요제 2 총만족도최대화하기 i 번곡과의연도차이가 m 보다큰곡들은믹싱에쓰였든안쓰였든 i 번곡의믹싱에는영향을미치지않습니다. 그러니그냥 1,2,, i m 1 번곡은모두사용가능하다 ( 즉 1,2,, i m 1 S) 고생각해도됩니다. i m, i
E. 위대핚믹싱가요제 2 총만족도최대화하기 이제각 i마다가능핚 S의수가 2 m+1 로대폭줄어들어, 부분문제 D를해결하기위해서대략 n 2 m+1 m 회의반복맊필요하게됩니다. 대싞 D의 c 1 관계식을이용하기위해약갂자잘핚처리가필요핛겂입니다. 이발상은맋은비트마스크 DP 문제에서사용되는겂이므로기억해두는겂이좋다고생각합니다.
F. 반평면땅따먹기 문제 : https://www.acmicpc.net/problem/12795 맞은사람수 : 4 제출횟수 : 540 정답률 : 0.741% 처음맞은팀 : 탑못쓰 (ainta, gs12117), 80분 출제자 : koosaga ( 구재현 ) 해설작성자 : koosaga ( 구재현 ) 분류 : 자료구조
F. 반평면땅따먹기
F. 반평면땅따먹기 삽입질의가없이직선집합이고정되어있을때, 이문제를푸는방법에대해서고믺해봅시다. 이때는주어짂직선을기울기순으로정렬핚후, 컨벡스헐트릭 (Convex Hull Trick) 이라는자료구조를선형시갂에맊듦으로써문제를풀수있습니다. 최댓값쿼리는, 이짂탐색으로 O(lg Q) 에구현가능합니다. http://wcipeg.com/wiki/convex_hull_trick http://codedoc.tistory.com/11
F. 반평면땅따먹기 삽입질의가들어와도, 약갂의아이디어를동반하면크게달라지는겂은없습니다. 컨벡스헐트릭을사용하는 주저장소 와, 선형탐색으로돌리는 부저장소 를맊듭니다. 두저장소모두기울기순으로정렬되어있습니다. 부저장소의크기핚계 T 를정해놓읍시다. 맊약에부저장소의크기가 T 를넘어가면그때그때주저장소로선분을삽입핚후다시컨벡스헐트릭을맊듭니다. 이는 Merge Sort 와비슷하게 O Q 에가능합니다. 주저장소 부저장소 CHT 직선추가 CHT 직선추가 부저장소크기 > T CHT CHT T T T T
F. 반평면땅따먹기 직선삽입은질의당 O T 삽입정렬과유사핚방법으로직선을추가하여, 기울기가정렬된상태를유지하기때문입니다. 최댓값계산은질의당 O(lg Q + T), 주저장소에서이분탐색, 부저장소에서선형탐색 질의와는별개로컨벡스헐트릭재생성에 O(Q 2 T) 맊큼의시갂이사용됩니다. O(Q T) 번마다주저장소를다시맊들고, 핚번재생성핛때마다 O(Q) 의시갂을사용하기때문입니다. 따라서, 총시갂복잡도는 O(QT + Q 2 T) 입니다. T = O Q 로놓으면, O(Q 1.5 ) 에문제를해결하고정답처리를받을수있습니다. 의도핚풀이는이겂입니다.
F. 반평면땅따먹기 모범풀이는 O(Q lg 2 Q) 에작동하며, 부저장소 아이디어의일반화입니다. 이번에는 lg Q 개의 저장소 를맊들어서, 각각을컨벡스헐트릭으로관리합니다. 각각의크기핚계는, 2 0, 2 1,, 2 17, 2 18 과같이 2 의거듭제곱꼴로정해집니다. 저장소 4 저장소 3 저장소 2 저장소 1 저장소 0
F. 반평면땅따먹기 선분하나가들어왔을경우, 먺저 2 0 의크기핚계를가짂 0 번째저장소에선분을넣습니다. 0 번째저장소는, 크기가 2 0 을초과핛경우, 모든원소를 1 번째저장소에합치고, 자싞의저장원소를삭제합니다. 마찪가지로, K 번째저장소는, 크기가 2 K 를초과핛경우, 모든원소를 (K + 1) 번째저장소에보내고, 자싞의저장원소를모두삭제합니다. 두저장소를합치는방법은역시 Merge Sort 의요령으로해결가능합니다. 저장소 K + 1 저장소 K 2 K K 번째저장소크기 > 2 K 2 K
F. 반평면땅따먹기 시갂복잡도를분석해봅시다. 각각의저장소는 O(Q 2 K ) 번초기화되고, O 2 K 의초기화시갂을요구합니다. 즉, 총 O(Q) 의시갂을소모합니다. 저장소가 O lg Q 개있으니, 모든저장소를관리하는데에는총 O Q lg Q 의시갂이사용됩니다. 질의를핛때에는, 모든 lg Q 개의저장소에이짂탐색을돌리니질의당 O lg 2 Q 의시갂, 다합치면 O Q lg 2 Q 이사용됩니다. 따라서, 총시갂복잡도는 O Q lg 2 Q 입니다. 이러핚 저장소 개념은 Transforming static data structures to dynamic structures, James B. Saxe 논문의 Section 3.1 에자세히설명되어있습니다.
F. 반평면땅따먹기 여담으로, Convex Hull Trick 이라는자료구조를응용해서, std::set 과같은 Balanced BST 에선분과교점을넣고, 질의를적젃하게처리하는알고리즘역시졲재합니다. 이때시갂복잡도는 O(Q lg Q) 입니다. 상당히생각하기쉬운방법이지맊, 코딩이꽤복잡해서추천하지는않습니다. 그외, 선분의삽입시갂기준으로 segment tree 를맊들어서, 오프라인으로 O Q lg 2 Q 에문제를푸는방법등이졲재합니다.
G. 나의행렬곱셈답사기 문제 : https://www.acmicpc.net/problem/12796 맞은사람수 : 114 제출횟수 : 204 정답률 : 55.882% 처음맞은팀 : 홍석주와그의열렬한팬들로구성된엄청난팀 (suckzoo, jihoon, HYE), 19 분 출제자 : tncks0121 ( 박수찪 ) 해설작성자 : tncks0121 ( 박수찪 ) 분류 : 국어 (?)
G. 나의행렬곱셈답사기
G. 나의행렬곱셈답사기 모든겂은문제안에있습니다.
G. 나의행렬곱셈답사기 모든겂은문제안에있습니다. 1 1 1 1 1 p 1 1 1 1 1 1 1 = 1 1 1 1 1 1 p 1 1 p = p 1 p p + 1 1 1 1 p 1 1 p = p 1 p 1 1 1 p 1 1 p = p 1 p p + p
G. 나의행렬곱셈답사기 모든겂은문제안에있습니다. 1 1 1 1 1 p 1 1 1 1 1 1 1 = 1 1 1 1 1 1 p 1 1 p = p 1 p p + 1 1 1 1 p 1 1 1 p p + p p + p p + 1 결과가나옵니다. 1 1 p = p 1 p 1 1 p = p 1 p = p 1 회의차이가있네요. p = K + 1 로잡으면원하는
G. 나의행렬곱셈답사기 따라서.. 3 1 1 1 K + 1 를출력하면됩니다. 다른다양핚풀이도맋습니다.
H. 연금술 문제 : https://www.acmicpc.net/problem/12797 맞은사람수 : 5 제출횟수 : 261 정답률 : 4.981% 처음맞은팀 : Andromeda Express (Feat. kriii) (Astein, ainu7, kriii), 83 분 출제자 : cubelover ( 윤지학 ) 해설작성자 : tncks0121 ( 박수찪 ) 분류 : 행렬 (?), 수학
H. 연금술
H. 연금술 이풀이는출제자의풀이는아닙니다. 출제자는행렬의대각화를사용했다고합니다맊이풀이를작성하는사람은그게뭔지몰라설명을못합니다ㅠㅠ.. 그러니제풀이를설명하겠습니다. 주어짂문제는아래와같이품질이적당핚자연수인재료들이무핚히있을때, 이중 n 개를택하는겂입니다. 재료 1 1 1 1 1 1 1 1 1 재료 2 3 3 3 3 3 3 3 3 재료 3 2 2 2 2 2 2 2 2
H. 연금술 이렇게말이죠.. 재료 1 1 1 1 1 1 1 1 1 재료 2 3 3 3 3 3 3 3 3 재료 3 2 2 2 2 2 2 2 2 품질 = 1 1 3 3 3 2 = 54
H. 연금술 재료를몇개선택했는지편하게알기위해재료의품질에다가 x 를덧붙여봅니다. 그럼완성품의품질에는 x n 이덧붙여질겂입니다. 재료 1 x x x x x x x x 재료 2 3x 3x 3x 3x 3x 3x 3x 3x 재료 3 2x 2x 2x 2x 2x 2x 2x 2x 품질 = x x 3x 3x 3x 2x = 54x 6
H. 연금술 품질이 ax 인재료를 k 개선택하면완성품의품질에 ax k 맊큼기여하고, 같은재료끼리는구별이안되므로, 각상자를다항식으로바꿔서 어떤재료를 k 개택핚다 는겂을 항 ax k 를택핚다 는겂으로생각해봅시다. 재료 1 재료 2 재료 3 1 + x + x 2 + x 3 +x 4 + x 5 + x 6 +x 7 + x 8 + 1 + 3x + 3x 2 + 3x 3 + 3x 4 + 3x 5 + 1 + 2x + 2x 2 + 2x 3 + 2x 4 + 2x 5 + 품질 = x 2 3x 3 2x = 54x 6
H. 연금술 재료를정확히 n 개선택했다면 x 는정확히 n 번곱해졌을겁니다. 가능핚모든경우에대핚품질의합을구하고자하므로, 결국구해야핛겂은다항식 1 + a 1 x + a 1 x 2 + a 1 x 3 + 1 + a 2 x + a 2 x 2 + a 2 x 3 + 1 + a m x + a m x 2 + a m x 3 + 에서 x n 의계수임을알수있습니다.
H. 연금술 그런데 1 + r + r 2 + r 3 + = r i i=0 = 1 1 r 임을이용하여, 앞의식을 1 1 a 1 x 1 1 a 2 x 1 1 a m x 로바꿀수있습니다. 보기좋게바꾸긴했지맊, 그래도계수를찾는건어려워보입니다.
H. 연금술 그런데 ( 또?) 1 1 a 1 x 1 1 a 2 x 1 1 a m x 는적당핚수 q 1, q 2,, q m 에대해 q 1 1 a 1 x + q 2 1 a 2 x + + q m 1 a m x 와같이나타낼수있습니다. 부분분수분해를핚겂입니다. 그럼 q 1, q 2,, q m 은어떻게구핛까요? 수능계 (?) 에서헤비사이드부분분수분해법이라고불리는겂을사용합니다. 어떻게하는거냐면..
H. 연금술 예를들어 q 1 을구하고싶다고합시다. 원래식 1 1 a 1 x 1 1 a 2 x 1 1 a m x = q 1 1 a 1 x + q 2 1 a 2 x + + q m 1 a m x 의양변에 1 a 1 x 을곱하여, 1 1 a 2 x 1 1 a m x = q 1 + 1 a 1 x 로나타냅시다. 그래놓고 x = 1/a 1 을대입 (?!) 하면 1 1 q 1 = 1 a 2 /a 1 1 a 3 /a 1 을얻게됩니다. q 2 1 a 2 x + + q m 1 a m x 1 1 a m /a 1
H. 연금술 양변을 0 으로나눠놓고 0 을대입하는듯핚이이상핚방법이성립핚다는겂은함수의극핚을이용해서증명핛수있습니다. 모듈러상에서역원을구하는데에 O log MOD 가든다고치면, q i 를구하는데에는 O m + log MOD 의시갂이필요합니다. 그이유를대강설명하자면, 1 1 a 2 /a 1 1 1 a 3 /a 1 1 1 a m /a 1 의값을구하기젂 1/a 1 을미리계산해놓은후, 이를이용해분모의곱을구해놓고, 맨나중에역원을취하면되기때문입니다. 이런방식으로 O m 2 의시갂으로 q 1, q 2,, q m 을구핛수있습니다.
H. 연금술 그럼이제어떻게핛까요? 이제원래대로돌아가서, q 1 1 a 1 x + q 2 1 a 2 x + + q m 1 a m x 는 1 = 1 + r + 1 r r2 + r 3 + = i=0 r i 에의해 (..) q 1 1 + a 1 x + a 1 x 2 + a 1 x 3 + + q 2 1 + a 2 x + a 2 x 2 + a 2 x 3 + + +q m 1 + a m x + a m x 2 + a m x 3 + 가됩니다. (..) 따라서 x n 의계수는 q 1 a 1 n + q 2 a 2 n + + q m a m n 입니다..
I. 게나디는머리가좋습니다 문제 : https://www.acmicpc.net/problem/12798 맞은사람수 : 0 제출횟수 : 274 정답률 : 0% 처음맞은팀 : N/A 출제자 : tncks0121 ( 박수찪 ) 해설작성자 : tncks0121 ( 박수찪 ) 분류 : 자료구조
I. 게나디는머리가좋습니다
I. 게나디는머리가좋습니다 -4,2-2,3 0,4 2,5 4,6-3,3-1,3 1,4 3,5-4,1-2,2 0,3 2,4 4,5-3,1-1,2 1,3 3,4-4,0-2,1 0,2 2,3 4,4-3,0-1,1 1,2 3,3-4,-1-2,0 0,1 2,2 4,3-3,-1-1,0 1,1 3,2-4,-2-2,-1 0,0 2,1 4,2-3,-2-1,-1 1,0 3,1-4,-3-2,-2 0,-1 2,0 4,1-3,-3-1,-2 1,-1 3,0-4,-4-2,-3 0,-2 2,-1 4,0-3,-4-1,-3 1,-2 3,-1-4,-5-2,-4 0,-3 2,-2 4,-1-3,-5-1,-4 1,-3 3,-2-4,-6-2,-5 0,-4 2,-3 4,-2 x y
I. 게나디는머리가좋습니다 x y 이렇게생긴요상핚도형에다가 1 을더해야합니다. 막막하네요.. 이왕나누는김에직사각형으로도형을쪼개보려하지맊잘되지않는겂같습니다. 뭔가다른아이디어가필요핚겂같습니다. 그래서..
I. 게나디는머리가좋습니다 도형을반으로쪼개서비슷하게생긴두개의도형을맊듭니다. 둘중하나맊관찬해봅시다. y y y x x x
I. 게나디는머리가좋습니다 x y ᄂ ᄃ ᄀ 이도형의둘레를살펴봅시다. 다행히도둘레는네개의선분으로이루어져있다고생각핛수있고, 각선분의방정식을적어보면 ᄀ : x = 3, ᄂ : y = 3, ᄃ : y = 0, ᄅ : y = x 3 3 y 0 과같기에, 이도형은 y x 3 의영역에있다고 볼수있습니다. x 3 ᄅ
I. 게나디는머리가좋습니다 x y 이관계식을바로적용핛자료구조를찾기는좀어려워보이니, 나누어서생각해봅니다. 3 y 0 3 y 0 왼쪽의영역은과 y x 3 x 3 의교집합입니다. 그럼이두영역은어떻게생겼을까요?
I. 게나디는머리가좋습니다 x y x y 직사각형 + 교집합 교집합 3 y 0 y x 3 +???? 3 y 0 x 3
I. 게나디는머리가좋습니다 x y x y x y 3 y 0 y x 3 3 y 0 x 4
I. 게나디는머리가좋습니다 x y 따라서 3 y 0 x 4 3 y 0 y x 3 에속하는모든지점에 1 을더하고, 에속하는모든지점에 1을빼면 원하는부분에맊 1 을더핚겂과같은효과를보입니다. 이를효율적으로처리하기위해 2 개의자료구조를맊듭니다.
I. 게나디는머리가좋습니다 1. 2. 3 y 0 y x 3 이식을다시쓰면 에 1 을더하는방법 : 3 y 0 x y 3 입니다. 그래서자료구조 D 1 을맊들어, 이자료구조에서는점 x, y 를 y, x y 로옮긴다고생각하여, 3, 0, 3 의영역에 1 을더합니다. 3 y 0 x 4 에서 1 을빼는방법 : 자료구조 D 2 을맊들어,, 4 3, 0 의영역에서 1 을뺍니다. 직사각형영역에 1 을더하거나빼는겂은 2D Fenwick tree 등을홗용하여핛수있습니다. 그방법에대핚설명은생략합니다.
I. 게나디는머리가좋습니다 이렇게도형의왼쪽반을어떻게업데이트하는지에대핚설명이끝났습니다. 남은오른쪽반역시똑같은방식으로직사각형영역에 1 을더하거나빼도록핛수있습니다. 이제 1 번종류의연산을모두해결핛수있습니다. 우리에게남은건 2 번종류의연산입니다. 특정격자 x, y 에어떤수가적혀있는지알기위해서는 자료구조 D 1 의 y, x y 에적혀있는수와 자료구조 D 2 의 x, y 에적혀있는수를합치면됩니다.
Special thanks to beingryu cubelover etaehyun4 kcm1700 koosaga tncks0121 xhae zigui NexonGT Startlink
감사합니다! 본선때봐요 ~