AGC032B
https://gyazo.com/e76108ab5d4311843730df54423d5dc2
https://gyazo.com/3f912a7e570eb817ebab2122ec066518
考えたこと
3なら1,3,2
4なら？
どう考えたらいいのか？
合計値はSN
これを別の数え方すると、位数Xで値がYならXYを周囲に分配する
つまり位数をDiとすれば
$ \sum_i iD_i = SN
すべての位数が1の時、左辺は10で右辺は4S
辺を一本追加すると2箇所の位数が増える
16を目指すなら2と4を繋げばいい
1,2,4,3
これは1と3が足りない
これを繋げば4増えてちょうど良い
5なら？
SはNより大きい
そうでない時、Nにつながる頂点はその時点でNになるのでさらに辺を待つことができず、連結の条件に反する
例外は、Nをハブとするネットワークで、N以外の和もNの時。これは3の時にしか成り立たない
位数1の頂点は存在しない
→A
サイクルになるのは4の時だけ
a,b,c,d,eにおいてa+c=c+eが満たせないので。
A: ということは「どこに辺があるか」より「どこにないか」だな
3の時、1-2
4の時、1-4, 2,3
5の時、完全グラフなら和は14〜10
1-4, 2-3を繋げば全部10になる
6の時、20〜15
1-5,2-4,あ、3が余った
そもそも15は6の倍数ではない
12にそろえるなら15は-3
うーん、簡単ではない
時間をおいて再度考えたもの
完全グラフを考える
この時、各頂点の隣接する頂点の番号の和は $ f(x)=\sum_i i - x
Nが偶数の時、xとN+1-xを繋げば$ f'(x)=\sum_i i - x - (N + 1 - x) = \sum_i i - (N + 1)となってxによらず定数
奇数の時が問題
https://gyazo.com/e76108ab5d4311843730df54423d5dc2
1~N-1に関してxとN-xを繋げば$ f'(x)=\sum_i i - x - (N - x) = \sum_i i - Nとなってxによらず定数
Nに関しては$ f(x) = \sum_i i - x = \sum_i i - N なのでやはり同じ値
公式解説
だいぶ悩んでからたどり着いたけど、すぐ補グラフに注目してればよかった
問題分割