감조차도 안옴
[일반] F 진짜 어렵네
ㅁ(119.202)
2021-11-13 01:37
추천 1
댓글 10
다른 게시글
-
끝났냐 [5][일기] EN_SA(encludingsalt) | 21.11.13추천 0
-
이번 DIV2 난이도 체감 B >>>>> C [4][일반] 익명(14.33) | 21.11.13추천 0
-
CF 754 A-D 풀이/후기/ASMR [1][일반] 익명(180.231) | 21.11.13추천 0
-
아니 그래서 그 another competition이 뭐냐고 ㅋㅋ [1][일반] 익명(14.33) | 21.11.12추천 1
-
이번주면 c++ 기본서 끝난다 [5][일반] 익명(59.24) | 21.11.12추천 0
-
이거 왜 이렇게 되는지 아는 분 [3][일반] 익명(39.7) | 21.11.12추천 0
-
재귀로 별찍는 문제 시간 초과 남 [12][일반] 익명(211.221) | 21.11.12추천 0
-
두 단순다각형의 최대 공통 접선 길이 구하는법 [11][일반] 익명(172.107) | 21.11.12추천 13
-
오늘은 dfs/bfs 반절 풀엇음 [6][일기] 익명(121.170) | 21.11.11추천 1
-
오늘의 일기 - 바킹독 그리디 문제집 완료 [8][일반] 익명(175.196) | 21.11.11추천 5
E어케품
가장작은거부터 greedy하게 채워나가는게 최적의 방법임을 알 수 있음. b1을 정한다는건 i=1을 고르는 연산을 몇번하는지 고르는것과 마찬가지고, 또 이건 2~n번째를 몇번 +-하는지와 같음. 따라서 b_1 쿼리는 2~n번째 수를 몇이나 +-하는지 결정하는 쿼리라 보면 됨. 이 +-하는 수를 x라고 하자. 1부터 n까지 쭉 읽어가며 greedy하게 보면, i번째에서 해야하는 쿼리가 |a+bi|꼴이란걸 알 수 있음.
|a+bi|라는 규칙을 어케찾앗노 ㄷㄷㄷㄷ
ㄳㄳ
아니 |a+bx| 뭐 아무튼 그래서 각 숫자마다 a,b를 계산하고 절대값 그래프의 합을 만들고, 이는 각각의 -a/b를 기준으로 선형으로 되어있으니 x가 주어지면 이분탐색으로 적절한 선을 찾아서, a+bx연산 때려서 답을 내면 됨. 말로하기 굉장히 어려운 문제...
뭔가 약간 피보나치적으로 증가하는 거 맞지?? 아닌가?
그런건 아님. 예를들어 소수 p가 있다고 하자. x가 들어오면 현재 +x가 된 상태니까(1번 연산을 x번 한거니까) 원래대로 만들려면 -x를 해야겠지. 그래서 소수p의 경우 b=-1임. pq라는 합성수의 경우, +x가 된 상태고, 각 p,q에 의해 -x 2번씩 된 상태니까, 원래대로 만들려면 +x를 해야함. 그래서 합성수 pq꼴은 b=1임. 이런식으로 잘 채워나가면 됨... a의 경우도 비슷
아 아니겠네 준내어렵네 암튼 ㄳㄳ 능력자추
https://codeforces.com/contest/1605/submission/135166732
정 모르겠으면 내 풀이 봐도 되는데 썩 좋은 코딩은 아니고 또 풀이에 자신 없어서 sysfail 받을수도 있음
당신은p갤의보배야