1 3 1 2 4 2 v v 1 2 1 2 1 2 に 2手で変更できる
1 1 1 1 1 1 v v v 1 2 1 2 1 2 数字は2種類でないといけない
奇数番目と偶数番目、それぞれで数字の出現数を数えて、最も大きな数字を変更せず残すようにすると、手数は最小になる。
ただし、最頻の数字が同じ場合は、例の2つめのように別の数字にしなければいけないので、
「奇数番目の1番目と偶数番目の2番目」か「奇数番目の2番目と偶数番目の1番目」を比較して、手数が最小になる方を選ぶ。
奇/偶数番目に1種類の数字しか無かった場合、配列外参照を避けるための場合分けが少し面倒。
from collections import Counter
n = int(input())
vvv = list(map(int, input().split()))
cnt1 = Counter(vvv[0::2])
cnt2 = Counter(vvv[1::2])
mc1 = cnt1.most_common(2)
mc2 = cnt2.most_common(2)
if mc1[0][0] == mc2[0][0]:
sc1 = mc1[1][1] if len(mc1) > 1 else 0
sc2 = mc2[1][1] if len(mc2) > 1 else 0
print(min(n - mc1[0][1] - sc2, n - sc1 - mc2[0][1]))
else:
print(n - mc1[0][1] - mc2[0][1])
'U': $(x_i,y_i+d_i)$'D': $(x_i,y_i-d_i)$'R': $(x_i+d_i,y_i)$'L': $(x_i-d_i,y_i)$'UDRL' のいずれかの文字からなる-1を出力せよまず、できるできないの判定として、全ての $X_i+Y_i$ の偶奇は一致していないといけない。
つまり、座標を市松模様に塗り分けると、アームの動かし方より関節$m$ は、黒なら黒、白なら白のみにしか行けない。偶奇が混じっていたら-1。
それさえ満たしていれば可能なのかはまだ分からないが、ひとまず先に進む。
構築問題では、2通りの考え方が出来て、
なのだが、以下の当て推量より、後者で考えてみる。
よって、$X_i+Y_i$ が奇数なら$\{1,2,4,8,...,2^{31}\}$、偶数なら1で微調整するとして $\{1,1,2,4,8,...,2^{31}\}$ のアームを用意してみる。
アームのカバー範囲を考えてみる。
長さ1のアームの一端が ① にあるとき、もう一端は4方向のいずれかをカバーできる。
・ ・①・ ・
長さ2→長さ1の順に2本のアームを考えると、16点をカバーできる。これらの点は、ナナメ正方形の範囲内で漏れはない。
・
・①・
・ ・ ・
・①・②・①・
・ ・ ・
・①・
・
4→2→1の3本を考えると、64点をカバーできる。これも、ナナメ正方形内の点は網羅できている。
＼・①・②・①・／
・＼・ ・ ・／・
・①・＼・①・／・①・
・ ・ ・＼・／・ ・ ・
・①・②・①・④・①・②・①・
・ ・ ・／・＼・ ・ ・
・①・／・①・＼・①・
・／・ ・ ・＼・ （一部）
／・①・②・①・＼
同様に考えると、原点からアームの長い順に考えて、目標点がナナメに4分割した上下左右の正方形のいずれに入るか、ということを再帰的に貪欲に求めていけばよい。
これで $X_i+Y_i$ が奇数の場合は求められ、偶数の場合も、長さ1のアームでずらして考えると奇数に帰着できる。
'0'または'1'のみからなる'1'のとき、頂点数 $i$ の連結成分を切り出せるような辺が存在する'0'のとき、頂点数 $i$ の連結成分を切り出せるような辺は存在しない
$s$ の末尾は'0'でないといけない。1つの辺で分割する以上、最低1つの頂点は切り離されるので、頂点数 $n$ の連結成分にはなり得ない。
$s$ の1文字目は'1'でないといけない。木には必ず葉があるので、それに繋がる辺で分割すれば、頂点数1の連結成分は必ず作れる。
$s$ の $i$ 文字目と $n-i$ 文字目は一致してないといけない。頂点数 $n$ の木から $i$ を切り出すと、もう一方の頂点数は $n-i$ である。
以上の3点をまずチェックする。
次に、連結成分が作れる時と作れない時がどういう状況か、考える。
...... -o--o----o- ......
/ ↑ここで分割
...... --o
~~~~~~~~~~~~
あわせてK個の頂点
o
/
...... ----o----o- ......
↑ここで分割してもK+1個になり、ダメ
~~~~~~~~~~~~
K個の頂点(上の1点は含まない)
ある1点を葉としてそこから「メインの1本」「条件を満たすための調整としての葉」のいずれかを1点ずつ繋いでいくことを考える。
最終的にこんな感じになる。（数字は繋ぐ順）
1 2 3 7 9 10 13
o--o--o----o--o--o----o-- ...
/|\ | / \
o o o o o o
4 5 6 8 11 12
左から考える。
頂点3まで来て、$s$ の3文字目が0だったとする。すると、頂点数3の連結成分を作らせないために、頂点3にはあと2点、繋ぐ必要がある。
1点のみしか繋がなければ、その1辺で分割することで頂点数3の連結成分に出来てしまう。逆に2点以上繋ぐと（少なくとも頂点1から繋がる部分では）頂点数3の連結成分には分割できなくなる。
これを踏まえて、$k+1$ 点目の頂点を繋ぐときは以下のようにするとよい。
考えるのは $\frac{n+1}{2}$ 点目まででよい。それ以降は全てメインの先頭に繋げてしまえばよい。
ooo
o--o--o----o--o--o----o-o
/|\ | / \ ooo
o o o o o o
def solve(s):
if s[-1] == '1':
return False
if s[0] == '0':
return False
half = s[:len(s) // 2]
if half != s[-2:(len(s) - 3) // 2:-1]:
return False
head = 1
master = 1
buf = []
for i, c in enumerate(half):
if c == '0':
buf.append('{} {}'.format(master, i + 2))
else:
buf.append('{} {}'.format(head, i + 2))
head = master = i + 2
for i in range(len(half), len(s) - 1):
buf.append('{} {}'.format(master, i + 2))
return buf
res = solve(input())
if res == False:
print(-1)
else:
print('\n'.join(res))
'-1'を出力ある隣接する2点 $u,v$ の $D_u,D_v$ について考える。
.. -o--o, ,o--o- .. -o--o- u -- v -o--o- .. .. -o--o' `o--o- ~~~~~~~~~~~ ~~~~~~~~~~~ 頂点数 ku 頂点数 n-ku
$D_u$ と $D_v$ の差は一意に決まる。$u$ 側の部分木に属する頂点数を $k_u$ とする。
$u$ から $v$ に移ると、$k_u$ 個の頂点については距離が1ずつ増え、$(n-k_u)$ 個の頂点については1ずつ減る。よって、$D_v = D_u + k_u - (n - k_u) = D_u - (n - 2k_u)$
これを踏まえると、$k_i$ の小さい、つまり葉に近い頂点の方が $D_i$ は大きくなり、逆に中央付近の頂点が小さくなる。
$D_i$ が最小の頂点 $r$ を根として考える。
$r$ 以外の各 $i$ について、$k_i$ が確定すれば、親が一意に決定でき、木が構築できる。（$D_p = D_i - (n-2k_i)$ である $p$ が親）
$k_i$ を確定させるには、全ての子頂点について先んじて処理すれば、$k_i=(子頂点の$k$ の合計)+1$ となる。
子の$D$ は親の$D$ より確実に大きいため、$D_i$ が大きい方から処理すればよいと分かる。頂点 $i$ に処理が回ってきた時点で、既にそれより葉に近い子頂点の処理は完了し、$k_i$ は確定している。
$D_i$ が最大の頂点は確実に葉であり、葉の部分木の頂点数は明らかに1であるため、最初はそこから始める。
ただし、これはあくまで差分についてしか見ていないため、最後に $D_r$ を調べ、実際に合致しているかチェックする。真値 $D'_r$ は、構築中に計算できる。
def solve(n, ddd):
dsd = {d: i for i, d in enumerate(ddd)}
child_cnt = [1] * n # including self
child_dist = [0] * n
buf = []
srt = sorted(dsd.items(), reverse=True)
for d, i in srt[:-1]:
cc = child_cnt[i]
pd = d - (n - cc * 2)
if pd == d or pd not in dsd:
return -1
pi = dsd[pd]
buf.append((pi + 1, i + 1))
child_cnt[pi] += cc
child_dist[pi] += child_dist[i] + cc
md, mi = srt[-1]
if md != child_dist[mi]:
return -1
return buf
n = int(input())
ddd = list(map(int, (input() for _ in range(n))))
res = solve(n, ddd)
if res == -1:
print(-1)
else:
print('\n'.join('{} {}'.format(*l) for l in res))