競技プログラミング用 知識集積所
ARC207B - Balanced Neighbors 2
最終更新：
sport_programming
-
view
問題
必要知識
簡単な内容は省略
別解の場合
考え方
考察問題。
入力例を見ると、足して13になるペアの相方と自分自身以外が全て距離1か2になっている。
そこで、他のNでも同様に足してN+1になるペアを作ることで構成できないか考える。
そこで、他のNでも同様に足してN+1になるペアを作ることで構成できないか考える。
しかしその前に、Nが小さい場合の特殊処理をする。
Nが5以下である場合、あるどこかの頂点からは他の全頂点に移動できる。
5個一直線の場合以外はそういう点が2つ以上できるため和の統一は不可能で、5個一直線の場合も全部試してみれば不可能。
よって、Nが5以下の場合は-1と出力すればよい。
Nが5以下である場合、あるどこかの頂点からは他の全頂点に移動できる。
5個一直線の場合以外はそういう点が2つ以上できるため和の統一は不可能で、5個一直線の場合も全部試してみれば不可能。
よって、Nが5以下の場合は-1と出力すればよい。
以下は、Nが6以上を仮定する。
円周に偶数個の頂点を等間隔に配置し、適切な距離の関係にあるもの同士をつないでみることを考える。
向かい同士がペア相手になるようにM組を配置する。
円周に偶数個の頂点を等間隔に配置し、適切な距離の関係にあるもの同士をつないでみることを考える。
向かい同士がペア相手になるようにM組を配置する。
まずはN=2Mで、Mが奇数の場合。
この場合は、自分からの距離がMより小さい奇数になるところ同士を結んでいく。
例えばN=18の場合は、距離が1,3,5,7のところ同士を結ぶ。
すると、これらに該当するところは距離1になり、2,4,6,8は2回目に1つ隣に移動することで距離2で到達できる。
そして9は奇数2つの和で作れないため到達できない。
これはNが6以上の4で割り切れない偶数である場合全てに適用できる。
この場合は、自分からの距離がMより小さい奇数になるところ同士を結んでいく。
例えばN=18の場合は、距離が1,3,5,7のところ同士を結ぶ。
すると、これらに該当するところは距離1になり、2,4,6,8は2回目に1つ隣に移動することで距離2で到達できる。
そして9は奇数2つの和で作れないため到達できない。
これはNが6以上の4で割り切れない偶数である場合全てに適用できる。
次に、まずはN=2Mで、Mが偶数の場合。
この場合は、自分からの距離が「M/2より小さい奇数」「M/2より大きい偶数」になるところ同士を結んでいく。
例えばN=20の場合は、距離が1,3,6,8のところ同士を結ぶ。
すると、これらに該当するところは距離1になり、2,4,5,7,9は2回目に1つ隣に移動することで距離2で到達できる。
そして10は、奇数2つの和は絶対に3+3以下で、偶数2つの和は絶対に6+6以上なので、到達できない。
これはNが12以上の4の倍数である場合全てに適用できる。
（Nが8の場合は、「M/2より大きい偶数」が存在しないため失敗）
この場合は、自分からの距離が「M/2より小さい奇数」「M/2より大きい偶数」になるところ同士を結んでいく。
例えばN=20の場合は、距離が1,3,6,8のところ同士を結ぶ。
すると、これらに該当するところは距離1になり、2,4,5,7,9は2回目に1つ隣に移動することで距離2で到達できる。
そして10は、奇数2つの和は絶対に3+3以下で、偶数2つの和は絶対に6+6以上なので、到達できない。
これはNが12以上の4の倍数である場合全てに適用できる。
（Nが8の場合は、「M/2より大きい偶数」が存在しないため失敗）
そして、Nが8の場合は、入力例1をヒントに、立方体の対角線にペアを配置するだけでよい。
Nが奇数の場合は、N番の頂点だけ特別扱いをする。
N-1番までの頂点について、条件を満たすことは上に書いた方法でできる。
ここにN番の頂点から「他の全奇数に対して結ぶ」をすると、
N-1番までの頂点について、条件を満たすことは上に書いた方法でできる。
ここにN番の頂点から「他の全奇数に対して結ぶ」をすると、
- N-1番までの頂点は、足してNになる相方と自分以外全部を足すことになるのは変わらない
- N番の頂点は、自分以外全部足すことになるが、自分自身がN番である
ことから、規則を壊さずにN番の頂点追加できる。
以上により、Nが6以上の場合はすべて具体的に構成できる。
解答例
注意点
別解
二部グラフ※を使う
足して「n+1以下の最大奇数」になるペアを作り、自分と相方以外に行けるようにする方針は同じ。
実際の構成に、二部グラフ※を用いることができる。
というのは、全ての「偶数と奇数の組」（ただしペア相手を除く）を結ぶとうまくいくから。
奇数からは、距離1でペア相方以外の全偶数に、距離2で全奇数に行き着く。
偶数からは、距離1でペア相方以外の全奇数に、距離2で全偶数に行き着く。
ということで、自分とペア相手以外全ての頂点が距離1か2になっている。
ただし、これをするためにはペアが最低3組必要なので、うまくいくのはnが6以上の場合に限られる。
また、nが奇数の場合も特殊対応は不要（ペアの相方がいないなら、自分以外の全頂点に行ける）。
解答例
実際の構成に、二部グラフ※を用いることができる。
というのは、全ての「偶数と奇数の組」（ただしペア相手を除く）を結ぶとうまくいくから。
奇数からは、距離1でペア相方以外の全偶数に、距離2で全奇数に行き着く。
偶数からは、距離1でペア相方以外の全奇数に、距離2で全偶数に行き着く。
ということで、自分とペア相手以外全ての頂点が距離1か2になっている。
ただし、これをするためにはペアが最低3組必要なので、うまくいくのはnが6以上の場合に限られる。
また、nが奇数の場合も特殊対応は不要（ペアの相方がいないなら、自分以外の全頂点に行ける）。
解答例
