K - Stones / atcoder.jp

문제링크 : https://atcoder.jp/contests/dp/tasks/dp_k
문제해설 : https://jinpyo.kim/EducationalDP-solution
Submission 첫버전 : https://atcoder.jp/contests/dp/submissions/9509087
Submission 속도최적화 : https://atcoder.jp/contests/dp/submissions/9543565
Java Source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/K%20-%20Stones/src/Main.java

K - Stones 문제입니다. 문제 설명이 약간 모호할 수도 있는대, Sample input 1을 가지고 문제를 정확히 이해하고 풀이를 시작해보겠습니다.

Sample Input 1

2 4
2 3

2개의 종류의 돌이 있습니다. 2와 3, 첫번째 시도에서 타로가 3을 선택합니다.
그러면, 4 - 3 = 1, 남은 돌의 숫자는 1입니다.
따라서, 지로가 2와 3중 어떤 것을 선택하더라도, 1 - 2 = -1, 1 - 3 = -2 와 같이 항상 음수가 나오기 때문에, 타로가 게임에서 이깁니다. 문제 설명에서, 'players play optimally'라고 했으므로, 타로는 첫번째 시도에서 2를 선택하지 않습니다.
만약에 2를 선택하게 되면, 지로가 2를 선택하게 되고, 항상 (0 - 2( or 3)) < 0 이 되기 때문에, 타로가 게임에서 지게 됩니다.

여기서는 d_{i}를 i 돌이 남아있을 때, 타로가 게임을 시작하게 되면, 게임을 이기는지, 지는지의 여부에 따라서 이김(true), 짐(false)로 놓고 식을 전개해 보겠습니다. 아래 _Sample Input 3_을 가지고 점화식(Recurrence relation)을 만들어 보겠습니다.

Sample Input 3

2 7
2 3

\begin{aligned}
d_{1} = F \\
(1 \leq x \leq N) 일 때, 항상 (1 - a_{x}) < 0 이기 \: 때문에 \: F 입니다.
\end{aligned}

d_{2} 부터는 2가지 선택이 있을 수 있지만, 플레이어는 항상 자신이 이기기 위한 선택을 해야 합니다. 따라서, 지는 선택인 3는 할 수 없고, 이기는 선택인 2을 해야 합니다. 2 - 2를 하면, 0이 나오고, 지로가 어떤 선택을 하든 -2 또는 -3 이 되기 때문에, 타로의 승리입니다.
\begin{aligned}
d_{2} = T \\
2 - 2 = 0 이기 \: 때문에 \: T 입니다.
\end{aligned}

\begin{aligned}
d_{3} = T \\
3 - 3 = 0 이기 \: 때문에 \: T 입니다.
\end{aligned}

d_{4} 부터는 기존에 계산한 d_{1} 부터 d_{3}을 사용해서 승리/패배를 알 수 있습니다.
\begin{aligned}
d_{4} = T \\
4 - 3 = 1 이구요 \: d_{4} = !d_{4-3} = !d_1 입니다.
\end{aligned}
d_{1} 은 F 이지만, 이 패배는 지로의 패배입니다. 따라서, 타로의 입장에서는 승리(T)가 됩니다.

d_{5}는 2와 3 어떤 수를 선택해도 모두 F 입니다.
\begin{aligned}
d_{5} = F \\
d_{5} = !d_{5-3} = !d_2 = !T = F \\
d_{5} = !d_{5-2} = !d_3 = !T = F \\
\end{aligned}

d_{6}는 2와 3 어떤 수를 선택해도 모두 F 입니다.
\begin{aligned}
d_{6} = F \\
d_{6} = !d_{6-3} = !d_3 = !T = F \\
d_{6} = !d_{6-2} = !d_4 = !T = F \\
\end{aligned}

d_{7}는 3을 선택하면 F가 되고, 2를 선택 하면 T가 됩니다. 따라서, 타로는 2를 선택하고, 게임에서 이김니다.
\begin{aligned}
d_{7} = T \\
d_{7} = !d_{7-3} = !d_4 = !T = F \\
d_{7} = !d_{7-2} = !d_5 = !F = T \\
\end{aligned}
a_x 의 개수가 늘어남에 따라서, 위에서 2개의 결과를 비교하여, T인 경우를 선택 했듯이, 이후 구현시에 T를 찾을 때 까지, a_1부터 a_n 까지 T인 경우를 찾아야 합니다.
여기가 구현할 때, 최적화가 필요한 부분입니다. 모든 a_n을 계산할 필요는 없구요, T인 경우를 한번만 찾으면, 더 게임에서 이기는 경우를 찾을 필요는 없습니다.

위의 식들로 부터 점화식을 만들어 보겠습니다.
i 가 모든 a_x 보다 작은 경우 d_{i}는 F
\begin{aligned}
i < a_x \: 1\leq x \leq N \\
d_{i} = F \\
\end{aligned}

i 가 어떤 a_x 와 같은 경우 임의의 x에 대해서 i - a_x = 0 임으로 T
\begin{aligned}
i = a_x \\
d_{i} = T \\
\end{aligned}

위의 2가지 경우에 해당하지 않는 다면, 아래 식에 따라서, T or F가 결정됩니다.

\begin{aligned}
모든 !d_{i-a_x}이 F 이면 F \\
d_{i} = !d_{i-a_x} \: 1\leq x \leq N \\
\end{aligned}

\begin{aligned}
어떤 x가 !d_{i-a_x}가 \:T\:이면\:T \\
d_{i} = !d_{i-a_x} \: 1\leq x \leq N \\
\end{aligned}

위의 점화식에 따라서 구현을 하면 아래와 같습니다.

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
//        Scanner sc = new Scanner(System.in);
        Reader sc = new Reader();
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] as = new int[N];
        boolean[] Rs = new boolean[K+1];

        for(int i=0; i<N; ++i) {
            as[i] = sc.nextInt();
        }

        // Rs[0] false 임으로 Taro가 이기는 경우 입니다.
        for(int i=1; i<=K; ++i) {
            boolean bRi = false;
            for(int j=0; j<N && (bRi == false); ++j) {
                int r = i - as[j];
                if(r < 0) {
                    bRi = false;
                }
                else {
                    bRi = !Rs[r];
                }
            }
            Rs[i] = bRi;
        }

        System.out.println(Rs[K]? "First": "Second");
    }

    // https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
    static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String nextLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
}