第二回全国統一プログラミング王決定戦予選 (NIKKEI Programming Contest 2019-2) A～E問題メモ

NIKKEI Programming Contest 2019-2

• 解説放送: 第二回全国統一プログラミング王決定戦予選 - YouTube

ぎりぎり滑り込み(?)で予選通過。C,D諦めてEさっさと見にいったのが奏功したか。

A - Sum of Two Integers

• 和が $N$ になる、異なる2つの正整数の組の個数を求めよ
• $(a,b)$ と $(b,a)$ は同じものとし、重複して数えない

ガウスさんの逸話を参考にすれば、$1+(N-1),2+(N-2),...$ で、計 $\frac{N-1}{2}$ 通りできる。

$N$ が偶数の場合は真ん中が $(\frac{N}{2},\frac{N}{2})$ となり「異なる2つの正整数」という条件に矛盾する点に注意。

B - Counting of Trees

• 頂点に $1,2,...,N$ の番号がついた $N$ 頂点の木を考える
• 数列 $D_1,D_2,...,D_N$ が与えられる
• 「全頂点について、頂点1と $i$ との距離が $D_i$ となる」ようなものが何通りあるか、$\mod{998244353}$ で求めよ

$D_i$ は、頂点1を根としたときの、各頂点の深さとも言い換えられる。

    ①    深さ 0
    /\
  ②  ④       1
  /\  ｜
 ③⑤ ⑥       2

まず、成り立たない条件を探す。以下に当てはまらなければ0通り。

• $D_1$ は必ず0で無いといけないし、この他に0があってはいけない
• $D_i = x$ の頂点が存在するには、必ず $x-1$ の頂点が存在する必要がある

これさえ満たせば、とりあえず作ることはできる。後は数え方。

$D_i = x$ である頂点 $i$ の親は、$D_p = x-1$ でさえあればどの頂点につないでもよい。

なので、$D_i = x$ である頂点の個数を $c_x$ とすると、頂点 $i$ の親の選択肢は $c_{D_i-1}$ 通りある。

$i$ がどの頂点に繋いだかは独立しており、他の頂点の選び方に影響しないので、これを全頂点について単純に掛け合わせればよい。

どうせ頂点の個数を数えるので、同じ $D_i$ を持つものは冪乗でまとめて計算してしまえる。

C - Swaps

• 長さ $N$ の2つの整数列 $A_1,...,A_N$ と $B_1,...,B_N$ がある
• 以下の操作を繰り返し行う
  • 異なる任意の2つの $A$ の要素を入れ替える
• $N−2$ 回以下（0回でもよい）の操作で、全ての $i (1 \le i \le N)$ に対して $A_i \le B_i$ となるようにできるか判定せよ
• $2 \le N \le 10^5$
• $1 \le A_i,B_i \le 10^9$

「最小手数はいくらか？」ではなく「○回以下でできるか？」を聞かれている。 こういう問題で大事なのは、つい「効率のいい入れ替え方は？」など最適化する方向に思考を巡らせてしまうのをぐっと我慢し、 ○回以下でできるかの判定に注力すること。前者は難しくても、後者は（まだ）簡単だったりする。

全要素を好きな位置に入れ替えることが出来るなら、$A_i$ と $B_i$ の小さい方から順に対応させていけばよい。 これで無理なら、どう入れ替えようとNoである。

A: 3  1  2  6  3  4   →   1  2  3  3  4  6
B: 2  2  8  3  4  2   →   2  2  2  3  4  8
                                 ^ 無理

以下、並べ替えた後の順序で $A_i \le B_i$ は成り立つとする。

$A$ の目指すべき状態をわかりやすくするため、$B$ を昇順にソートし、それに従って $A$ も並べ直し、$i$ も振り直すとする。 こうすると、$A$ も昇順になるように目指して入れ替えればよい。

A: 3  1  2  6  3  4   →   1  3  4  6  3  2
B: 2  2  8  3  4  3   →   2  2  3  3  4  8

問題は回数制限があることだが、全 $N$ 要素を好きな位置に入れ替えるために必要な回数は？と考えると、最大 $N-1$ 回の入れ替えでできる。 先頭から順に目的の位置に収めていった場合、$N-1$ 要素目を収めた時点で、残りの1要素は勝手に収まっていると考えるとよい。

(例) 5 4 1 3 2  を、入れ替えによって昇順に並べ直す
1 4 5 3 2
1 2 5 3 4
1 2 3 5 4
1 2 3 4 5

$N-2$ 回ということはそれより1回だけ減らせばよい。制約としてだいぶゆるい感じがしてくる。

試してみると、$N-1$ 回より少ない回数で入れ替えられる初期状態も存在する。

(例) 5 1 4 3 2  を並べ直す
1 5 4 3 2
1 2 4 3 5
1 2 3 4 5

これは何故かというと、(1,2,5) と (3,4) でそれぞれ入れ替えるべき要素が閉じているから。 5要素の入れ替えには最大4回かかるが、「3要素の入れ替えには最大2回」「2要素の入れ替えには最大1回」に分割できれば、合わせても最大3回である。

この、入れ替えるべき要素の閉じたサイクルを、「巡回置換」というらしい。

なので、置換の対応関係を、互いに素な2つの巡回置換に分割できればYes、どうしてもできなければNoである。

で、それを判定するのだが、この条件が、仮に発想は出来てもそれで網羅しているかの確信が掴みづらい。 条件は、主に2パターンに分けられる。

1. 上記の例のように、2つ以上の巡回置換に分割できる
2. 厳密にソート順で対応させていかなくても、1箇所でも「$(A_i,B_i)(A_j,B_j)$ は $(A_i,B_j)(A_j,B_i)$ と対応させてもよい」箇所が存在する

説明のため、$A_{i,j}$ を「元の数列では $i$ 番目、ソート後（＝目指すべき位置）は $j$ 番目である $A$ の要素」とする。

1番目は、UnionFind木などを使い、各 $A_{i,j}$ につき $i$ と $j$ を統合していき、最終的なグループ数で判定できる。

2番目は、ソートした $A$ と $B$ を比較する。 $A_{i,j} \le B_{j-1}$ ならば、$A_{\_,j-1},A_{i,j}$ の2要素の最終的な目標位置を入れ替えることができる。 少なくともどちらかは2つ以上の巡回置換に分割できる。

A: 1  2  3  4  6  8     (※ソート後)
B: 1  2  4  5  7  8

A: 1  2  3  ④  6  8
B: 1  2  ④  5  7  8    B3は、A4以上なので...

A: 1  2  4⇔3  6  8
B: 1  2  4  5  7  8       ...と、対応づけて"も"よい

D - Shortest Path on a Line

• $N$ 個の頂点 $1～N$ が1列に並んでいる
• はじめ、辺は無い
• 以下の操作を $M$ 回おこない、辺を追加する
  • $i$ 回目の操作では、$L_i,R_i,C_i$ が与えられる
  • $L_i \le a \lt b \le R_i$ にある全2頂点間に、コスト $C_i$ の辺を追加する
• 頂点1から$N$ までの最短コストを求めよ
• $2 \le N \le 10^5$
• $1 \le M \le 10^5$
• $1 \le C_i \le 10^9$

$i$ 番目の操作で張られた辺を使うなら、常に $R_i$ まで行ってしまって問題ない。 途中からよりコストの低い辺に乗り換えられるとしても、同じコストで同じ頂点に行ける辺が $R_i$ からも出ている。

しかし、それを愚直に張っていくと辺数が $O(N^2)$ になるので、何かうまいことやる必要がある。

ある頂点に着いたら、そこから出る最もコストの低い辺を使う？ でも、わずかにコストが高い辺でもっと遠くまで行けたら、その方が得な場合もある。 使う辺の組合せの問題なので、貪欲は無理そう。

$DP[m][k]=m$ 番目の操作まで考えて、頂点1から $k$ に到達できる最小コスト、とする。 （$m$ については1つ前の状態さえあれば十分なので、以下、単に $DP[k]$ と表記する）

問題の性質から、$DP[1] \le DP[2] \le ... \le DP[N]$ である。 遠くの頂点に行けるなら、その通過点から同じコストの辺がより近い頂点にも出ているはずだから。

$i$ 番目の操作で張られた辺を使うとすると、以下でコストを更新できるのだが、

• 頂点 $L_i+1$ へは、$DP[L_i]+C_i$ で到達可
• 頂点 $L_i+2$ へは、$\min(DP[L_i],DP[L_i+1])+C_i$ で到達可
• 頂点 $L_i+3$ へは、$\min(DP[L_i],DP[L_i+1],DP[L_i+2])+C_i$ で到達可
• …

さっきの不等式から、これは結局全て $DP[L_i]+C_i$ であることがわかる。

よって、区間更新、1点取得のセグメント木を使えば、$L_i$ の小さい方から

• 区間 $[L_i+1,R_i]$ を $DP[L_i] + C_i$ で、それぞれ現在の値と比較して小さければ更新

を繰り返せばDPを更新していける。しかし、上書き更新で無く、1つ1つ要素比較して区間更新しなければならない。

一般にセグメント木でこのような区間更新は（できなくはないらしいが）難しいが、 今回はDPは昇順にソートされているという保証があるので、セグメント木上で二分探索が出来るよう実装しておくと、 現在の値より更新すべき $DP[L_i]+C_i$ が小さくなる境界を検索すれば、そこから $R_i$ までの上書き更新で問題ない。

シンプルな、1点更新・区間取得のセグメント木でも実装できる方法がある。 先ほどのは「配るDP」、これは「貰うDP」に発想が近く、

• $DP[R_i]$ を、$\min(DP[L_i]～DP[R_i-1]) + C_i$ と比較して小さければ更新

とすればよい。

E - Non-triangular Triplets

• 初項 $K$、公差 1、長さ $3N$ の等差数列がある
• $(a_1,b_1,c_1),...,(a_N,b_N,c_N)$ の3つずつ $N$ 個の組に分ける
• 全ての組が以下の条件を満たすような分け方があるか判定し、あるなら一例を示せ
  • $a_i + b_i \le c_i$
• $1 \le N \le 10^5$
• $1 \le K \le 10^9$

とりあえず、大きい方から $N$ 個を $c$ にしてよさそう。 もし、それから外れても条件を満たせる分け方があったとしても、入れ替えても必ず条件を満たす。

N=3  K=1
1 2 3 4 5 6 7 8 9

(2 7 9) (1 5 6) (3 4 8) が条件を満たすなら（7がbに含まれ、6がcに含まれる）
(2 6 9) (1 5 7) (3 4 8) も条件を満たす

また、総和は変わらないので（$a,b$ の総和）$\gt$（$c$ の総和）なら、全ての組が条件を満たすのは不可能である。

で、後は何か適当に実験を書き殴っていく。なるべく、$a+b$ の結果が1ずつ増えていくような組合せになるのが望ましい。と、以下のような手順でいい感じになる。

$N$ が奇数の場合、$a$ として $1～N$ まで並べて、$b$ として続く $N$ 個を $\frac{N+1}{2}$ 番目から順に並べると、結果が1ずつ増えていく。

N=5 K=1
a   b   a+b
1   9   10
2  10   12
3   6    9
4   7   11
5   8   13

$N$ が偶数の場合は、1個飛びの数字が2個ずつできてしまうのだが、まぁまぁ無駄なく連番に対応させることができる。

N=6 K=1
a   b   a+b
1  10   11  <= 11
2  11   13  <= 13
3  12   15  <= 15
4   7   11  <= 12
5   8   13  <= 14
6   9   15  <= 16

もっと効率の良い組合せがあるか？だが、1箇所を小さくしても他で大きくなれば意味が無く、 重要なのは「連番の最初の数字は何か」（上記例では11）ということである。

この状態で双方の和を取ると、$a+b$ の総和 $=$ 連番の総和 $- \frac{N}{2}$ となっている。

ここから連番の最初を10にしようとすると、連番の総和は $N$ 減ることになる。 もともと $a+b$ の総和$\le$連番の総和 とするには、連番の方に $\frac{N}{2}$ しか余裕がないのだから $N$ 減らすことは不可能で、 結局11が連番の最初として取れる最小値ということになる。

よって、$a$ と $b$ を半分ずらして組み合わせる方法で可能なら可能、不可能なら不可能であることが示せたので、その通りに実装すればよい。