데옴's 기록장

무작위화가 정해..? 오름차순 정렬을 통해 인원이 가장 적은 k개의 마을은 고려하지 말자. 인원이 가장 적은 k개의 마을을 다른 도시에 넣는다고 더 좋은 결과를 보장하지 않음을 알 수 있기 때문에 남은 2k개의 마을에서 적절히 선거구를 나누는 방법을 사용하자. 선거구를 나누는 방법으로 무작위화를 사용하면 된다.두 그룹으로 나눴을때 두 그룹 다 k*500을 만족하지 않는다면 계속 랜덤으로 배열을 섞어주는 방법을 사용하자. 이 방법이 왜 될까?? 는 잘 모르겠고 제한이 작고 문제의 조건을 만족하는 배치가 꽤나 많이 존재하기 때문에 충분히 시간안에 높은 확률로 답을 구할 수 있음을 보장할 수 있다.  신기한 문제

코드포스 대회에 참여하고 3번째 대회이다. 지금까지 본 코포중 제일 잘 친 대회인 것 같다..C번은 거의 신뢰의 제출이었는데 운좋게 한번에 맞았다. ㄷㄷ 어쩌다보니 블루 퍼포를 받아버렸다. 3번째 대회인만큼 보정치가 합해져서 +401 ㄷㄷ..첫 코포를 좀 잘쳤으면 그린 갔을듯하다.. A(00:00 ~ 00:30)처음에 일단 무작정 제출해봤다가 망했음을 감지하고 3틀을 해서 푼 문제다..나름(?) 어려웠었는데 틀려서 새로고침할때마다 푼사람이 1000명씩 늘어나는걸 보고 접고싶은 생각이 들었다.(이걸 왜 못풀었지) 아무튼 aeiou를 배치해서 펠린드롬의 개수를 최소하 하는 방법은 aaaaaeeeeeiiiiiooooouuu와 같이 배치하는 것이다.더보기int main(){ fastio; int t; ci..

실력 상승을 위해 골드 5~3 랜디를 해보았다. 효과는 있는 거 같기도..대충 어디가서 꿀리지 않을 정도로만 잘해지면 될 거 같다.BOJ 2024 - 선분덮기 태그: 스위핑, 그리디 현재 정점을 덮을 수 있는 선분 중 왼쪽으로 가장 길게 뻗은 선분을 선택하면 된다.0번 정점부터 시작해 이동하며 갱신해 준다. 범위 잘못 잡아서 많이 틀렸던..BOJ 23889 - 돌 굴러가유 태그: 그리디, 정렬 +누적합 간단하게 생각하면 쉽게 풀이를 얻을 수 있었다. 돌이 시작하는 지점들 사이의 합을 구해둔 뒤 그중 구간의 합이 가장 큰 k개를 선택해 주면 된다. BOJ 1633 - 최고의 팀 만들기 태그: dp 3차원 dp에서 반복문으로 테이블 전이 시키는 과정이 조금 힘들었다. dp의 길은 끝이 없고..dp테이블을 다..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

그리디(?)적으로 생각했을 때 그냥 자기 자리로 찾아가는 녀석의 수를 줄이면 된다.문제가 원하는 것은 오름차순으로 정렬을 하는데 움직이는 학생의 수를 줄이는 것이므로 전체에서 오름차순으로 정렬되어 있는 최대 학생의 수를 빼면 된다는 것을 쉽게 알 수 있다. 즉 전체에서 lis를 빼주면 된다.더보기int main() { fastio; int n; cin>>n; vectorarr(n); for(auto&v:arr)cin>>v; vectordp(n,0); int ans=0; for(int i=0; iarr[j])dp[i]=max(dp[i],dp[j]+1); } ans=max(ans,dp[i]); } cout

매우 쉽게 점화식이 나와서 기분이 좋았던 문제다. i일에 일을 받아서 작업을 하면 i+t[i]일에 p[i]원을 받는다.일을 받지 않고 다음날로 가는 경우에는 dp[i+1]=max(dp[i+1],dp[i])일을 받아서 하는 경우에는 dp[i+t[i]]=max(dp[i+t[i]],dp[i]+p[i]) n+1일까지 일을 할 수 있으므로 dp[n+1]이 구하고자 하는 값이다. 더보기int main() { fastio; int n; cin>>n; vector>arr(n); for(auto&[a,b]:arr)cin>>a>>b; vectordp(1500001,0); for(int i=1; i

더보기  dp가 어려운 나에게 실버 1 dp를 풀어보는것을 시도했다사실 어렵다기보다는 아이디어는 거의 나오는데 점화식을 못 세우는 기현상이 있었고 티어에 비해 기본기가 많이 부족한 거 같아서 시작.. 점화식 느낌 잡기 용으로 푼 4문제 정도 가볍게? 정리해본다.실버 dp였기는 했지만 이전에 구한 상태를 현재 구하고자 하는 값에 반영한다는 느낌을 가지고 문제를 보면 점화식이 쉽게 나왔다.BOJ 15645 - 내려가기 2 , BOJ 2096 - 내려가기내려가기 2를 풀면 내려가기를 풀 수 있다. 다음 칸으로 가는 경우는 바로 아래칸과 인접한 좌 우 칸으로 이동하는 것이다.그렇다면 i번째 줄에 j번 칸에 올 수 있는 최대 값은 max{i-1번째 줄에서 j번 칸으로 이동 가능한 칸}으로 볼 수 있다. 15645..

아마 이번에도 본선은 쉽지 않지 않을까 생각이 들정도로 못본거 같다. 1교시는 쉬운데 노가다성이 강한 문제가 아주많아서 그냥 더러웠다.1교시 연습을 좀 했는데 효과가 그래도 있던거 같기도.. 2교시 1번은 그냥 날먹 그리디너무 쉬워서 당황쓰 2번 트리 dp또는 금광세그 비슷하게 풀 수 있다는데.. 암튼 나는 못했다. 3번 r=n일때 긁기 시도, 개같이 멸망 결론: 그냥 망했다.운좋으면 장려는 타려나...

아이디어만 있다면 풀 수 있다 이건가요? 내가 문제 2개를 고르면 상대가 가장 자신 있는 문제 하나를 가져간 후 내가 남은 문제를 가져간다.'나'와 상대는 i 번째 문제에 대해 각각 Ai, Bi 만큼의 자신감 수치를 가지고 있다.내가 문제 2개를 고르지만 정작 문제의 선택권은 상대에게 있다.문제 2개를 적절하게 잘 고르면 최적의 상황을 얻을 수 있다는데.... 당장은 보이지 않는다.우선 문제의 선택권이 상대에게 있다는 것에 초점을 두고 Bi를 기준으로 정렬을 해보자.4 2 8 66 5 7 8  2 4 8 65 6 7 8 여기서 맨 뒤에 있는 문제는 무조건 상대가 가져가는 문제, 맨 앞의 문제는 무조건 내가 가져갈 수 있는 문제임을 알 수 있다.그럼 어떤 식으로 두 개의 문제를 골라야 자신감 수치를 최대화..