Processing math: 100%
알고리즘 블로그
article thumbnail
[ABC 270] G. Sequence in mod P ★
PS 문제들 2022. 9. 25. 21:05

문제 링크 버추얼을 돌면서 만난 문제이다. 처음에는 함수형 그래프에서 사이클을 다루는 알고리즘 floyd cycle finding을 떠올렸는데, 이내 입력을 보아하니 안 될 것 같아서 접고 수식을 정리해봤다. G=AnS+BAn1A1이 나왔는데, n을 결정하는 것이 난관이였다. 식을 n에 대해서 정리하고 이산 로그로 구할 수 있을까라는 생각을 했고, 딱히 발전이 없던 차에 시간이 끝났다. 알고 보니 이산 로그도 풀이가 될 수 있고, 혹은 baby-step giant-step이라는 알고리즘을 사용할 수도 있었다. 사실 이산 로그를 구할 때 이 알고리즘이 들어간다. 아무튼 baby step giant step의 원리를 이해했다. 이것으로 이산 로그를 구할 수 있다..

article thumbnail
[JOI 2012 예선] ジグザグ数(지그재그 숫자) ★
PS 문제들 2022. 9. 13. 03:15

문제 링크 질문은 언제나 환영입니다. 풀이 더보기 지그재그의 조건을 생각해보자. 지그재그는 인접합 2~3개 정도의 원소만 보면 된다. 지그 다음에는 재그 그 다음에는 지그... 따라서 지그 또는 재그의 상태끼리 다 묶어서 관리하면 계산량이 10500 가까이에서 훅 줄어서 reasonable해 질 것이다. 그리고 지그와 재그를 표현함에 있어서 그 자리의 숫자들도 당연히 관리해야 할 것이다. 지그/재그 상태와 자리 숫자가 같아도 몇 자릿수인지에 따라 달라질 것이다. 그래서 자릿수도 관리하고... M의 배수라고 하니까, 좀 고민하다가 보면 M으로 나눈 나머지를 잘 써주면 좋겠다 싶은데, 이 정보도 함께 관리하면 되겠다. U(i,j,k):=i자리에서 증가세로 숫자 j에 도달했을 때, 나머..

article thumbnail
[BOJ 1328] 고층 빌딩 ★
PS 문제들 2022. 9. 12. 13:07

문제 링크질문은 언제나 환영입니다.3가지 풀이법이 나오네요. 글에는 없는 자신만의 풀이법이 존재하신다면 알려주세요!두 가지 풀이법은 O(n3)짜리 풀이이고, 한 가지 풀이법은 O(n2)짜리입니다.풀이더보기문제에서 구해야 하는 것은 조건을 만족하는 배치의 수입니다.세세한 배치의 성질들에 대해 알아볼 방법은 떠오르지 않고, 작은 케이스부터 풀다 보면 패턴이 보이기 때문에 동적 계획법을 시도해볼 수 있습니다. 3차원 동적 계획법B(x,y,z):=x개의 빌딩 중 왼쪽에서 y개, 오른쪽에서 z개만 보이는 경우의 수위와 같이 정의하는 것은 아주 자연스럽습니다. 점화식을 도출할 때는 B(x1,)와의 관계를 우선 생각 해봅시다.새로 생긴 가장 긴 막대기를 어디다 꽂아 넣을지를 고..

article thumbnail
[Baltic OI 2013 Day 1] Palindrome-Free Numbers(무-팰린드롬 숫자) ★
PS 문제들 2022. 9. 8. 19:33

문제 링크 질문은 언제나 환영입니다. 풀이 더보기 딱히 발상이 어려운 문제라고 보기는 힘들다. 특별한 알고리즘이 있는 문제도 아니다. 그냥 열심히 풀면 풀리는 문제다. 중요한 관찰은 하나뿐이다. 동적계획법처럼 귀납적으로 무-팰린드롬을 확장시키려는 시도를 해야 한다. 이 때, 확장하는 경계로부터 2칸 정도만 고려해도 충분하다. 왜냐하면 길이가 4 이상인 팰린드롬은 이미 길이가 2 이상인 팰린드롬을 포함하고 있기 때문이다. 예를 들어, 2와 무-팰린드롬인지 알고 있는 432를 이어 붙이는 상황에서는 2432를 확인할 필요가 없는 것이다. 왜냐하면 43이 애초에 팰린드롬이 아니기 때문이다. 따라서 24243을 확인하는 것으로 충분하다. 이 관찰을 통해서 풀이를 이끌어 낼 수 있다. 무..

article thumbnail
[IZhO 2012 Day 2] Monkey and Apple-trees(원숭이와 사과 나무)
PS 문제들 2022. 6. 4. 01:20

지문 링크 / 문제 링크 더보기 이거 풀면서 lazy propagation를 짜는 방식도 바꿨다. 속도가 2배가량 향상되고, 훨씬 직관적으로 변했다. 풀이 더보기 dynamic segment tree + lazy propagation. UPD - 구조체 내부 포인터도 0으로 같이 초기화하지 않으면 컴파일 환경에 따라 UB가 발생할 수 있다! 무조건 다 초기화시키자. 그리고 인덱스로 음수가 들어갈 수 있는 경우 단순한 (s+e)/2는 예상한 대로 동작하지 않는다. 따라서 이 블로그에 있는 "코드 조각들" 글에 있는 floor 함수를 이용해서 나눗셈을 처리하자. #include using namespace std; using ii = pair; using ll = long long; #define rep(i..

article thumbnail
[COCI 12/13 #1] SNAGA(숫자의 힘)
PS 문제들 2022. 6. 1. 00:17

문제 링크 플4치고 쉬운? 문제 풀이 더보기 2 3→2 4→3→2 5→2 6→4→3→2 7→2 8→3→2 9→2 10→3→2 주어진 수를 나누지 않는 최솟값 → 어떤 수보다 미만의 모든 수가 주어진 수를 나누게 하는 최솟값 따라서 |{k|(2k)}|×(strength(2)+1)+|{k|(2k)(3k)}|×(strength(3)+1)+|{k|(2k)(3k)(4k)}|×(strength(4)+1)+ 를 구해주면 된다. lcm 단위로 커지기 때문에, 전처리할 strength(k)의 종류가 그리 많지 않다는 ..

article thumbnail
[KOI 2010 본선] 체인점
PS 문제들 2022. 5. 25. 20:13

문제 링크 이 문제를 풀기 전에 BOI의 굉장한 학생을 먼저 풀어보시는 것을 추천드립니다. 풀이 더보기 다익스트라로 A로부터의 거리, B로부터의 거리, C로부터의 거리를 구한 뒤, A로부터의 거리의 오름차순으로 B로부터의 거리를 좌표압축한 인덱스에 C로부터의 거리를 업데이트해주면 된다. #include using namespace std; using ii = pair; using ll = long long; void o_o(){ cerr c >> m; rep(i,1,m) { int x, y, z; cin >> x >> y >> z; adj[x].emplace_back(y,z); adj[y].emplace_back(x,z); } vector v(n); vector bs; ll da[N..

article thumbnail
[JOISC 2018 Day 3] Bitaro's Party ★
PS 문제들 2022. 5. 25. 18:13

문제 링크 usaco.guide에서 sqrt decomposition 예제로 제일 쉬운거로 추천되어 있었는데, 그걸 왜 곧이곧대로 믿었을까요... 풀 때 사진 참고하세요. 문제 번역 1부터 N까지 높이에 대한 내림차순으로 번호가 매겨진 N개의 마을들이 있습니다.(같은 높이의 마을은 없습니다.) M개의 운하는 서로 다른 마을을 단방향으로 연결합니다. i번째 운하(1iM)은 높은 Si에서 낮은 Ei로 흐릅니다. 운하는 거꾸로 거슬러 올라갈 수 없습니다. 비버 Bitaro의 N명의 친구들은 N개의 마을에 살고 있습니다. Bitaro는 Q번의 파티를 열며, 친구들을 초대할 것입니다. j번째 파티에는 \(Y_j..