AtCoder Regular Contest 103

AtCoder Regular Contest 103/ Beginner Contest 111 解説放送 - YouTube

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

            

        
      

−目次