AGC032B

B - Balanced Neighbors

• 
• 考えたこと
  • 3なら1,3,2
  • 4なら？
    • どう考えたらいいのか？
    • 合計値はSN
    • これを別の数え方すると、位数Xで値がYならXYを周囲に分配する
    • つまり位数をDiとすれば
      • ${\sum }_{i}i{D}_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^{\prime }(x)={\sum }_{i}i-x-(N+1-x)={\sum }_{i}i-(N+1)$となってxによらず定数
  • 奇数の時が問題
  • 
  • 1~N-1に関してxとN-xを繋げば$f^{\prime }(x)={\sum }_{i}i-x-(N-x)={\sum }_{i}i-N$となってxによらず定数
  • Nに関しては$f(x)={\sum }_{i}i-x={\sum }_{i}i-N$ なのでやはり同じ値 公式解説
• 連結なグラフの補グラフ
  • だいぶ悩んでからたどり着いたけど、すぐ補グラフに注目してればよかった

問題分割

• 一つ構築せよ問題
• 小さい制約の問題
• 連結なグラフ

AGC032