구사과

문자열 S와 T가 주어졌을 때, S의 부분 문자열 중 T가 몇번 등장하는 지를 찾는 문제를 생각해보자. 예를 들어 "koosaga" 에서 "saga" 를 찾으면 "koos" != "saga", "oosa" != "saga", "osag" != "saga", "saga" == "saga" 여서 총 한번 등장하고, "aa" 를 찾으면 "ko" != "aa", "oo" != "aa", "os" != "aa", "sa" != "aa", "ag" != "aa", "ga" != "aa" 여서 단 한번도 등장하지 않는다. N = (S의 길이), M = (T의 길이) 라 하자. S[i, j] = (i번째 문자에서 j-1번째 문자까지를 포함하는 부분 문자열) 이라고 하자. 예를 들어 "koosaga"[0, 3] = "k..

http://agc013.contest.atcoder.jp/ A. Sorted Arrays단순 구현인데 코딩이 의외로 쉽지 않았다. B. Hamiltonish Path신기한 문제. path 어디에나 붙여도 되는 줄 알고 진짜 해밀턴 경로 문젠줄 알아서 좀 해멨다. 그런 경로를 아무거나 찾으면 되는 것이니 path 끝에 붙일 수 있는 정점이 있다면 무조건 붙여보는 식으로 풀면 된다. dfs로 쉽게 구현 가능. C. Ants on a Circle부딪힐 때 서로 방향을 바꾼다고 생각하지 않고, 서로의 번호만 바꿔서 가던 길 그대로 간다고 생각하면 복잡하지 않다. 이건 워낙 유명한 유형이니까 뭐...그렇게 하면 전체 개미의 위치는 아주 쉽게 알 수 있다. 하지만 무슨 개미가 어떤 위치에 있는지는 어떻게 알까. ..

H번 문제의 풀이를 "조속한 시간" 내에 올리겠다고 공식 홈페이지에 올라왔지만, 사실 모두의 기억 속에서 잊혀져 버린 문제이다. 그래서 아무도 작업하고 있지 않았다..얼마 전에 BOJ 즐겨찾기를 보다가 기억이 나서 풀이를 작성했다. 풀이 tex 파일과 함께 첨부한다.