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

programming_algorithm/contest_history/atcoder/2018/0929_arc103.txt · 最終更新: 2018/10/13 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0