Codeforces 643 Div. 2 D - Game With Array
ぱっと思いつく解法が答えなのだけれど、その解法が本当に正しいのかうまく証明できなかった（本番では見切りで投げたら通った）。
まず、すべての要素の値を$ 2以上にできれば、$ K = 1は必ず達成できないことがわかる。したがってPetyaが勝つための必要条件は$ S \ge 2Nで、このとき配列を$ \{2, 2, \ldots, 2, S - 2(N-1)\}とすればPetyaは勝てる。以下に、この条件が十分条件であること、すなわち$ S \lt 2NであるときにPetyaが勝てないことを背理法で示す。
総和が$ Sで長さ$ Nとなる配列$ \{a_i\}があり、a) $ S \lt 2Nかつ b) どの連続する部分列をとってもその総和が$ Kにも$ S - Kにもならないような$ Kが存在する、とする。ここで$ \{ a_i \}の累積和を$ \{s_i\}とし、さらにつぎのような長さ$ 2NKの数列$ \{s'_i\}を考える。この数列は単調増加かつ最終項が$ s_{N-1} + (2K - 1)S \lt s_N + (2K - 1)S = 2SKであることに注意。
$ \{s'_i\} = 0, s_1, s_2, \ldots, s_N, s_1 + S, s_2 + S, \ldots, s_N + S, s_1 + 2S, \ldots, s_N + 2S, \ldots, s_1 + (2K - 1)S, \ldots, s_{N-1} + (2K - 1)S
この$ s'_iの任意の$ 2要素を選び、その差のリストを作ったとすると、そこには$ \{a_i\}の任意の連続する部分列の総和もしくはその総和を$ Sから引いたものがすべて含まれていることがわかる。これは$ \{a_i\}が循環する数列を考え、その任意の区間の総和をとっていると考えれば分かりやすい。もちろん、$ \{a_i\}の連続する部分列の総和もしくはその総和を$ Sから引いたもの以外もこのリストに含まれることはあり得る。
さて、この$ s'_iの要素がつぎのようなペアのリストのどこに現れるか考えよう。なお$ s'_iが単調増加かつ最終項が$ 2SK未満であることから、$ s'_iのすべての相異なる要素$ 2NK個がどこかに現れる。また、任意の$ s'_iの$ 2要素の差が$ Kになることはあり得ない（なぜなら、もしそうであれば仮定 b) に反する）ことから、$ s'_iの要素があるペアの両方に現れることはない。したがって、このペアの数は$ 2NK以上でなければならない。ペアの数は$ SK個なので、すなわち$ SK \ge 2NKであり、$ S \ge 2Nが成り立つ。しかし、これは a) の仮定 $ S \lt 2Nに矛盾する。
$ (0, K), (1, K+1), \ldots, (K - 1, 2K - 1), (2K, 3K), (2K+1, 3K+1), \ldots, (2SK - K - 1, 2SK - 1)
code:java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int S = scanner.nextInt();
if (S >= N * 2) {
System.out.println("YES");
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N - 1; i++) sb.append(2).append(' ');
sb.append(S - (N - 1) * 2);
System.out.println(sb.toString());
System.out.println(1);
} else {
System.out.println("NO");
}
}
}