結果

A,B,C,DはAC。

A - Fifty-Fifty

値が二つ、2回ずつ出てくればよいねということでDictionaryに放り込みました。Keyが出てくるたびにValueを+1。

最終的に要素数が2、各要素数の数が2になったらYes*1。

ループで回して条件判定をしました。
$p_{i-1} \lt p_{i} \leq p_{i+1}$ または $p_{i-1} \geq p_{i} \gt p_{i+1}$ 。 *2
最初は条件1つしか考えてなかったけど入力例1で2ついると気づきました。親切設計な入力例。

整数 $K$ の選び方は何通りあるでしょうか。

から並び順とか関係してる？組み合わせいる？と一瞬思いましたが、関係ありませんね。
単に「昇順(or降順)に並ぶ数列をちょうど真ん中で分けれる閾値は何個？」という話です。ソートしてやって真ん中の二つ( $N/2-1,\,N/2$ )の差分を取りました。

高橋君がちょうど $i$ 回操作をする必要がある、というのは青いボールの塊が $i$ 個ある、ということです。
つまり青いボールの間に赤いボールを入れて $i$ 個に分割する。
※解説のように赤いボールの間に青いボールを入れて分割と考えた方がはるかに楽。

ここから先は高校数学のお時間ですね久しぶり過ぎて顔も忘れた。

青いボールの間を $i-1$ 個選んで赤いボールを1個ずつ入れます
端について場合分けをします
1.端を使わない
2.端を片方使う(左端と右端の2通り)
3.両端を使う
各ケースにおいて残りの青いボールを自由に振り分けます(1の場合は $i-1$ 個の箱に $N-K-(i-1)$ 個のボールを振り分ける、と考える)
それぞれ足し合わせます
1の場合は ${}_{K-1}C_{i-1}\,\, {}_{i-1}H_{N-K-(i-1)}$
2の場合は $2{}_{K-1}C_{i-1}\,\, {}_{i}H_{N-K-i}$
3の場合は ${}_{K-1}C_{i-1}\,\, {}_{i+1}H_{N-K-(i+1)}$

※赤ボール間の $i-1$ 個に1個ずつボールを入れた後は場合分け要りませんね…。 ${}_{K-1}C_{i-1}\,\, {}_{i+1}H_{N-K-(i-1)}$

赤いボールの間に青いボールを入れて分割する場合、赤いボールの間+両端から $i$ 個選び以下略( ${}_{N-K+1}C_{i}\,\, {}_{i}H_{K-i}$ )だけで良いのでとても楽です。

組み合わせを高速で計算する方法を使わないと時間厳しいかも？

振り分けの方法公式あるよなーと思ったのでコンテスト中にググりました。重複組み合わせ( ${}_{n}H_{r}$ )なんてやったっけ？考え方だけ覚えて済ませてたような気がするようなしないような。

3の場合を考え忘れてて終了10分前くらいに気づき、ACｷﾞﾘｷﾞﾘでした。変なテンションになってたーのしー

解説見ながら。

ポイント

あるパスでS-T間の距離が3の倍数でなくとも、別のパスや閉路で調整できれば距離が3の倍数になるかもしれない(閉路や違うパスを通っても調整できないなら到達できない)。

頂点ごとに距離を3つ保存する(mod3 が0、1、2)。 Sからbfsを行う。通ったことがあるかどうかの判定は距離ごとにおこなう(1回目に訪れたときの距離が1の場合、次に訪れたときの距離2なら訪れる。4(1)なら訪れない)。

解説見ながら。

ポイント

漸化式を考える。 $f(n,m)$ をn要素で末尾がnのものとすると $f(n+1,m)=\sum_{i=1}^{i \leq N/K} f(n,i)$
計算量が多いので効率化する。 $\sum$ を累積和。 $i \leq N/K$ が同じになるものをまとめる(N=10ならi=4,5(10/i=2)、i=6,7,8,9,10(10/i=1)は同じ)