전체적으로 쉬웠던 Round다.
상하좌우로 움직여야하는 명령 string이 들어왔을 때, 명령 중 아무거나 제거했을 때 목적지에 도달할 수 있는지 판단하는 문제다.
상의 개수, 하의 개수, 좌의 개수, 우의 개수를 전부 더하면 명령을 적절히 제거했을 때 움직일 수 있는 boundary가 나오므로 그 boundary내에 목적지가 있는지 판단하면 된다.
산이 일렬로 있는데, index 0 산에서 돌을 오른쪽으로 굴린다. 만약 높이가 더 높은 산을 만나서 돌이 멈추게 될 경우, 멈춘 그 산의 높이는 1 증가한다. k번째 돌을 굴렸을 때 그 돌이 멈추는 산의 index를 출력해야하는데, 더 높은 산을 만나지 못 해서 산 끝까지 가게 되면 -1을 출력하는 문제다.
$k$가 $10^9$로 매우 크게 주어져 있어서 돌을 하나씩 굴리지말고, 똑같은 위치의 산에 계속 쌓이는 경우를 check해서 그 만큼 한번에 빼주는 식으로 짰었는데, wa받았다. 애초에 불가능한 풀이다.
$k$가 매우 커도, 산의 높이인 $h_i$가 100으로 매우 작다. $k$는 최대 $99 * 100 = 9900$개 쌓일 수 있으므로, 그냥 naive하게 하나하나 굴려줘도 시간내에 풀리게 된다.
현재 펜스의 색 $a_i$가 주어지고, 원하는 펜스의 색$b_i$가 주어진다. 이 때, 시공업자를 불러서 펜스의 색을 칠하는데, 한 명의 시공업자는 정확히 한 번의 페인트 칠 만할 수 있고, $c_i$색으로만 바꿀 수 있다. 정확히 한 번 페인트칠을 해야하기 때문에 안 하고 가는 경우는 없다. 시공업자는 입력 순서대로 방문하게 될 때, 페인트 칠이 가능한지 여부를 판단하고, 간능하면 페인트한 펜스의 번호를 순서대로 출력하는 문제다.
greedy하게 생각해보면 case가 3가지가 있다.
[case1] 현재 $c_i$색으로 칠 할 차례일 때, 만약 원하는 색 $b_i$중에 $c_i$와 같은 색이 있으면, queue에 있는 모든 색을 $b_i$색의 펜스에 칠하고, 마지막으로 $c_i$색으로 칠한다.
[case2] 현재 $c_i$색으로 칠 할 차례일 때, 원하는 색 $b_i$중에 $c_i$와 같은색이 없는 반면, 현재 칠해져 있는 펜스의 색 $a_i$중에 $c_i$와 같은 색이 있으면 queue에 있는 모든 색을 $a_i$색의 펜스에 칠하고, 마지막으로 $c_i$색으로 칠한다.
[case3] 위 두 경우에 모두 해당 되지 않는다면 queue에 넣는다.
모든 페인트 $c_i$를 순회를 마쳤는데 queue가 비어져있지 않거나, 모든 색이 적절하게 색칠되어있지 않으면 불가능한거고, 반대의 경우 가능하고, 색칠한 순서대로 출력해주면 된다.
색을 칠 하게 될 때 기존의 색을 덧칠해줘도 된다는 점에서 착안해서 buffer쓰듯이 queue에 넣어두고 비워주는 식으로 짯는데, 애초에 뒤에서부터 순회하게 하면 불가능한 경우 판별도 쉽고, queue도 필요없게 된다.
그것 보다도 O(1)로 색칠 가능한 펜스를 찾아오기 위해서 $a, b, c$배열 뿐만아니라 여러 배열을 써야하는 구현문제에 가까워서 코드포스에 익숙하지않거나 한번 꼬이게 되면 시간이 오래 걸리게 될 문제다.
3개의 배열, 1개의 set배열, 2개의 vector배열을 써가면서 풀었는데 적어도 2개 이상은 덜어낼 수 있을 것 같다.
진짜 코드포스 서버는 전설이다...
wa받은 건 할 말이 없지만 제출하고 약 30분 기다려서 체점받았다. 진짜 너무한다..
no self-loop complete directed graph가 주어지는데, 각 간선은 'a'혹은 'b'로 labeling된 간선들이고, 이 graph위에서 $m$번 움직이려고 한다. 지나간 경로가 pelindrome이 되는지 판단하고, 지나간 vertex들을 출력하는 문제이다.
내가 생각한 case는 아래와 같다.
[case1] 두 vertex사이의 두 간선(in, out)의 labeling이 모두 'a'이거나 'b'인경우, 두 vertex들만 왔다 갔다 하면 되므로 yes
[case2] $m$이 홀 수인 경우, 그냥 두 아무 vertex사이끼리 왔다 갔다 하면 pelindrome이 된다. yes
[case3] $m$이 짝 수인 경우, 모든 vertex에서 out하는 edge들의 labeling이 모두 'a'이거나 'b'인 경우, no다.
[case4] $m$이 짝 수인 경우 중에 위 경우를 제외하고는 모두 yes다.
$m$이 짝 수인 경우 위와 같이 생각한 이유는
이런 경우를 생각 했다.
case1에 의해 $v_i$에서 $v_j$로 가는 간선이 a이면 $v_j$에서 $v_i$로 가는 간선은 무조건 b이게 되고, 반대도 마찬가지가 되므로, 한 vertex에서 out하는 edge의 labeling을 보고, a와 b 모두 있으면 다른 vertex들은 고려하지않고, 위 그림과 같이 세 vertex사이에서 놀면 된다.
m/2번은 $10$에서 $1$로, 나머지 m/2번은 $10$에서 $2$로 왔다 갔다 하게 될 경우 yes이고, 나머지 경우는 없다고 판단했다.
하지만, 위 case에서 예외가 발생하게 되는데, 바로 $m$이 2일때 이다.
이런 graph에서 $m$이 2일때를 생각해보면, 위에서 정의한 case에 의해 10에서 시작하여, 1과 2로 각각 m/2번 왔다 갔다 해야하는데, m/2가 1이므로 돌아올 수가 없고, 돌아오게 될 경우 pelindrome이 아니다.
위 grpah에서는 10에서 출발하면 pelindrome을 만들 수 없고, 2에서 출발해야 'aa'로 pelindrome을 만들 수 있다.
시험기간이라 아직 풀지는 않았지만, $m$이 2인 case만 2개짜리 경로를 전부 찾아보면 될듯 하다.
