[일반] 문제 하나만 풀어주세염

[익명(114.205)]

https://codeforces.com/contest/1688/problem/C

https://codeforces.com/blog/entry/103493

코드포스 796 div2 c번입니다.
홀수번 나오는 문자가 정답이라는데 이걸 어떻게 증면하는건지 이해가 안감....
고수들아 도와줘!

[익명(175.127)]

s에 있는 알파벳마다 각자 갯수를 세보셈. 문자를 없애거나 추가할때마다 이에 해당되는 알파벳들의 갯수 홀짝이 바뀜. 알파벳 갯수가 전부 0으로 시작했다치면 최종문자의 홀짝성과 2n번의 연산으로 인한 홀짝성이 같아야되는데 초기 문자 알파벳 하나만 다를거잖아. 그게 답임

[익명(114.205)]

으... 뭔가 잘 설명한 것 같은데 내가 빡대가리라 이해가 안되네 ㅈㅅ ㅠ "문자를 없애거나 추가할때마다 이에 해당되는 알파벳들의 갯수 홀짝이 바뀜" 이 잘 안 와닿아....

[익명(175.127)]

문자열에서 위치는 무시하고 그냥 a 갯수만 봐바. t_2i-1에서 a가 있는 갯수만큼 a가 줄어들고, t_2i에서 a가 있는 갯수만큼 a가 늘어남. 그러면 최종 문자열에서 a의 갯수==2n번의 연산 이후의 a 갯수잖아. 여기서 처음 문자열에서의 알파벳 갯수를 다 0개로 처봐 a부터 z까지. 그러면 알파벳 하나만 다를텐데 그게 답임. 이걸 한번에 요약하면 홀수번 나온 문자가 정답인거고

[익명(175.127)]

근데 t를 랜덤으로 섞어놔서 뭐가 추가이고 뭐가 삭제인지 모르잖아. 그래서 홀짝만 따지는거임 2에 대한 나머지는 더하거나 빼거나 결과는 똑같으니까

[익명(114.205)]

오 처음엔 긴가민가 했는데 이제 이해 됐다 고맙다!! 다음에도 알려줘