[일반] 재미있는 문제 하나 찾았다

[0xrgb(0xrgb)]

http://gall.dcinside.com/programming/907803

나중에 시간나면 풀이올림

[aa(59.31)]

도아주세여~~

[옥토끼(moonrabbit2)]

두 원소를 swap했을때 더 나으면 안된다고 하면 정렬 조건 구할 수 있는거같음 - dc App

[aa(59.31)]

제가 생각한 정렬 조건은

[aa(59.31)]

비교원소를 x , y라 한다면 (x.a+x.b)*y.a + y.b 가 (y.a + y.b)*x.a + x.b 보다 작을경우 x를 앞으로 반대의경우 y를 앞으로 정렬조건을 했지만 실패했습니다.

[aa(59.31)]

위의 문제의 곱셈을 쭉 풀어보면 a(0)*a(1)*.....*a(n) + b(0)a(1)a(2).......a(n) + b(1)a(2)a(3).....a(n) + .... + b(n) 이 나오지만 정렬 기준을 잡을 아이디어가 떠오르질 않네요

[0xrgb(0xrgb)]

다 풀었네

[aa(61.85)]

여기서 더이상 진전이 없어요...

[aa(59.31)]

풀어진 식을 보면 a값이 큰것부터 올리면 당연히 작은 수가 나올것이라 생각했지만 {10,4},{6,3},{7,6},{2,6},{1,6} 의 값이 {10,4},{7,6},{6,3},{2,6},{1,6} 값보다 작으므로 반례가 나옵니다..

[옥토끼(moonrabbit2)]

거의 다 푼듯 부등식만 한번 전개해봐 - dc App

[익명(218.54)]

이전까지의 합을 x라고 하고 (a, b)와 (c, d)를 비교해야하면 a(cx+d)+b < c(ax+b)+d인지 확인하면 되는 건데 풀면 ad+b < bc+d가 되니까 저걸 기준으로 정렬하면 되지 않을가

[asd(104.10)]

b1 / (a1 - 1) >= b2 / (a2 - 1) 식으로 정렬하면 되지 않나? a = 1일때는 무한대라고 가정하고.

[시아닌(kimjg1119)]

이거 계절학교 여학에 그리디 연습문제로 나왔음. 3분컷 뚝딱~~

[aa(61.85)]

풀이법좀

[aa(61.85)]

그니까 나도 곱하는 X가 가장 작으면 결국 최소값이라는 그리디는 알겠는데. 이제 정렬조건을 짜려고 식을 짜는데 자꾸 틀려

[시아닌(kimjg1119)]

처음에 방향을 잘못잡으면 좀 말릴수 있다고 생각함

[aa(61.85)]

두개의 레일 a, b 가있다 하면 정렬 조건은 a.a*b.b - a.a > a.b*b.a -a.b 만족하면 a가 앞, 아니면 b가 앞 으로 정렬 해서 풀려고 하는데 테스트케이스를 다 통과하질 못하네

[시아닌(kimjg1119)]

부등식을 제대로 풀었다는 가정 하에 자료형 범위를 초과하지 않는지 살펴봐

[aa(61.85)]

범위형 초과해 각각 의 a, b <= 백만 이니까ㅎㅎㅎ근데 난 이런 그리디 문제에서 증명을 통해 이게 최적의 답이다 라는 것을 찾고 문제를 풀어보고 싶었는데 아무리 생각해도 내가 세운 정렬 기준이 항상 최적의 해라는걸 증명을 못하겠어서.. 그래서 지금까지 붙잡고 있어

[aa(61.85)]

무슨 느낌이냐면.. 맞는거 같은데 확실히 맞는건 모르겠는 느낌..

[aa(61.85)]

정렬조건 잘못썼다 bool cmp(rail a, rail b) { if ((a.a*b.b + a.b) > (a.b*b.a + b.b)) return true; return false; }

[시아닌(kimjg1119)]

저 위에 옥톡끼가 다해줬네. 임의의 인접한 두 원소에 대해서 니가 고른 정렬 기준대로 두 원소만 정렬했을때 항상 기존보다 더 나아지거나 그대로임을 보여.

[aa(61.85)]

열심히 공부해야겠다............................ 알고리즘 넘나 어려운것

[익명(175.210)]

잘모르겟넹 머리가 나빠서 ㅠㅠ

[ㅇ(222.106)]

https://www.acmicpc.net/problem/2180

[0xrgb(0xrgb)]

있는문제였군

[0xrgb(0xrgb)]

아 그런데 조금 다르다

[aa(61.85)]

풀이법 올려줘영~~~~

[익명(223.33)]

품번좀