目次
AtCoder Regular Contest 103
C - /\/\/\/
問題
- 数列 $a_1,a_2,...,a_N$ がある
- 長さ $N$ は偶数である
- これを $\{1,2,1,2,...\}$ のように、丁度2つの数字の繰り返しであるような数列にしたい
- 1つの数字を別の数字に変更するのを1手として、最小手数を求めよ
例
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])
D - Robot Arms
問題
- ロボットアームを構築する
- ロボットアームは $m$ 本の腕が $m+1$ 個の関節で繋がれた構造
- 関節にアームで繋がれた順に $0,1,...,m$ と番号を付けると、関節0は原点$(0,0)$に固定
- 各アームは$x$軸または$y$軸に平行に伸ばす
- つまり、$i$ 本目のアームの長さが $d_i$、その一方の関節 $i$ が$(x_i, y_i)$にある場合、もう一方の関節は以下のいずれかになる
'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)$
- 原点の反対側の端をぴったり合わせたい目標が $N$ 点あり、$i$ 番目の目標は$(X_i,Y_i)$
- いずれの目標にも、関節 $m$ を合わせられるようなロボットアームを構築せよ
- アームの本数 $m$
- 各アームの長さ $d_1,d_2,...,d_m$
- 各目標に合わせるためのアームの配置 $s_1,s_2,...,s_N$
- $s_i$ は長さ $m$ の文字列で、
'UDRL' のいずれかの文字からなる
- 出来ない場合は
-1を出力せよ - $1 \le N \le 1000$
- $-10^9 \le X_i,Y_i \le 10^9$
- $1 \le m \le 40$
解法
可能性判定
まず、できるできないの判定として、全ての $X_i+Y_i$ の偶奇は一致していないといけない。
つまり、座標を市松模様に塗り分けると、アームの動かし方より関節$m$ は、黒なら黒、白なら白のみにしか行けない。偶奇が混じっていたら-1。
それさえ満たしていれば可能なのかはまだ分からないが、ひとまず先に進む。
アームの本数と長さ
構築問題では、2通りの考え方が出来て、
- 与えられた条件から出発して、ぴったり合うように作る
- どんな条件が来ても対応できるアームの本数と長さが存在するのでそれを見つける
なのだが、以下の当て推量より、後者で考えてみる。
- 「組み合わせの合計によって満遍なくどんな数にも対応」には2のべき乗がよく使われる
- 座標の範囲が $10^9 \simeq 2^{30}$ で、微調整に何本か使うとして、アームの本数の制約＝40の「ねらい」が何となく感じられる
よって、$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のアームでずらして考えると奇数に帰着できる。
E - Tr/ee
問題
- 長さ $n$ の文字列 $s$ が与えられる
- $s$ は
'0'または'1'のみからなる - 以下の条件を満たす頂点数 $n$ の木を構築せよ
- 木の任意の辺を1つだけ選び、そこで分割して連結成分を切り出すことを考えた時、
- $s$ の $i$ 文字目が
'1'のとき、頂点数 $i$ の連結成分を切り出せるような辺が存在する - $s$ の $i$ 文字目が
'0'のとき、頂点数 $i$ の連結成分を切り出せるような辺は存在しない
- $2 \le n \le 10^5$
解法
$s$ の末尾は'0'でないといけない。1つの辺で分割する以上、最低1つの頂点は切り離されるので、頂点数 $n$ の連結成分にはなり得ない。
$s$ の1文字目は'1'でないといけない。木には必ず葉があるので、それに繋がる辺で分割すれば、頂点数1の連結成分は必ず作れる。
$s$ の $i$ 文字目と $n-i$ 文字目は一致してないといけない。頂点数 $n$ の木から $i$ を切り出すと、もう一方の頂点数は $n-i$ である。
以上の3点をまずチェックする。
次に、連結成分が作れる時と作れない時がどういう状況か、考える。
頂点数Kが作れる場合
...... -o--o----o- ......
/ ↑ここで分割
...... --o
~~~~~~~~~~~~
あわせてK個の頂点
頂点数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$ 点目の頂点を繋ぐときは以下のようにするとよい。
- $s[k]=1$なら、メインの1本を伸ばし、自身がメインの先頭となる
- $s[k]=0$なら、枝葉として、メインの現時点の先頭に繋げる
考えるのは $\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))
F - Distance Sums
問題
- 長さ $N$ の数列 $D_1,D_2,...,D_N$
- $D_i$ の値はすべて異なる
- 以下の条件を満たす $N$ 頂点の木を構築する
- 各頂点には $1,2,...,N$ の番号
- 各辺の長さは1
- 各頂点 $i$ に対して、$i$ から他の頂点までの距離の和は $D_i$
- 存在しなければ
'-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_i$ が大きい順に、頂点 $i$ の親を確定させていく
- $k_i$ が確定しているため、親の $D_p$ が計算でき、$p$ が特定できる
- $D_p$ である頂点 $p$ が存在しない場合は、構築は不可能である
ただし、これはあくまで差分についてしか見ていないため、最後に $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))
