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))