[일반] [컴퓨터 문제 베이스] 이거 증명해줄 수 있는 형 있음?

[익명(210.103)]

대충 전체적인 맥락은

단조성을 띄는 수열에 대해 저 연산을 해주면 zigzag permutation 비스무리한거 생성할 수 있음

근데 나는 컴퓨터만 하니까 저 연산이 어떻게 zigzag하게 만들 수 있는지 말끔한 증명이나 논리를 잘 모르겠음

[익명(221.160)]

써져있는 그대로임. p_i를 제일 끝으로 옮겼을때 수열의 absolute difference가 줄어들지 않는데 마지막 항이랑 같을 때만 그대로고, 다른 경우에는 증가함. 즉 (N*absolute difference + 끝에서 같은 값이 연속해서 나타나는 횟수)는 시행을 할때 늘 증가함. 항이 유한개니까 이건 최댓값을 가지므로 시행을 하다보면 시행을 할 수 없는 때가 온다는 뜻임

[익명(221.160)]

또는 약간 비효율적으로 하자면(어차피 제시한 방법도 전혀 효율적인 방법은 아님) 그냥 순서대로 정렬한 다음에 앞과 뒤에서 지그재그로 뽑아오면 됨

[익명(118.235)]

a b c * * * z에서 a b c가 감소하는 순서대로 있으면 이 수에서 연속한 항의 차의 합은 (a-b)+(b-c)지? 여기서 b를 맨 끝으로 보내면 a c * * * z b가 되는데 *가 들어가는 차는 전부 그대로고, 바뀐 항은 처음 차인 (a-c)랑 마지막 차인 |z-b|인데, a-c=(a-b)+(b-c)라서 바꾸고나서는 |z-b|만큼 늘어나지

[익명(210.103)]

다들 감사합니다 행님들

[시아닌(kimjg1119)]

ps갤 냅두고 여기서 뭐하냐 게이야...

[시아닌(kimjg1119)]

https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c
보니까 이거네

[익명(210.103)]

아 이걸 단속 당하네 ㅋㅋ 뭔가 수학틱한건 수잘갤 형들이 더 잘해줄 거 같아서 여기로 오는 편임