n번째로 작은 팰린드롬 수를 찾는 놀라운 방법

https://atcoder.jp/contests/abc363/tasks/abc363_d D - Palindromic NumberAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  n이 최대 10^18까지라서 보통의 방법으로는 찾을 수 없다는 것이 느껴진다 그래서 일단 가능한 팰린드롬 수를 차례대로 나열해본다 0,1,2,3,4,5,6,7,8,9 >>> 10개 11,22,33,44,55,66,77,88,99 >>> 9개 101, 111, 121, 131, 141, ... ,191202,212,222,232,..., 292303..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 7. 23.
• textsms

돌 무더기에서 팰린드롬(palindrome)인 정수 개수만큼 가져갈 때 이기는 방법

31648번: Palindrome Game (acmicpc.net)   돌 무더기에 s개의 돌이 있는데, A,B가 양의 정수 x개만큼 돌을 가져간다. 여기서 x는 palindrome이어야 한다.  palindrome은 앞에서 읽어도 뒤에서 읽어도 같은 수이다. 예를 들어 1, 121, 9009는 palindrome이다. 앞에 0을 붙이는 것은 허용하지 않는다. 예를 들어 990은 palindrome이 아니다. s가 주어질때, 최선을 다해 게임하는 둘에 대해 선공이 이기는지 후공이 이기는지 판단 -----------------------------------------------------------------------------------------------------------------------..

• format_list_bulleted 게임이론
• · 2024. 5. 6.
• textsms

manacher 응용문제로 이해력 높이기 - 회문인 부분문자열의 개수를 찾는법

1. 문제 16163번: #15164번_제보 (acmicpc.net) 16163번: #15164번_제보 www.acmicpc.net 2. 풀이 연속인 부분문자열에서 회문의 개수를 구하는 문제 manacher 알고리즘을 수행하면서, 나타나는 회문의 개수를 세면 될 것이다... 그런데 회문의 개수를 어떻게 세야할까 예를 들어 ABCBA에 대해서.. manacher 알고리즘을 수행하기 위해 #을 붙여가지고 #A#B#C#B#A#으로 바꾸고 나서.. 각 index에 대해서 양쪽으로 확대해나가 회문인지 찾아나갈텐데 A배열은 각 위치에서 가장 긴 회문의 반지름 길이를 나타내는 것으로, 가장 긴 회문의 반지름 길이를 알고 있다면, 이는 그보다 작은 회문도 포함하고 있는거니까, 이 값을 이용한다면 해당 지점에서 회문의 ..

• format_list_bulleted 문자열 알고리즘
• · 2023. 5. 4.
• textsms