APC 001

AtCoder Petrozavodsk Contest 001 - AtCoder

B - Two Arrays

2つの同要素数の数列がある
以下の操作を繰り返し行い、2つの配列を同じに出来るか判定せよ
- 任意の $i,j$ を選び、$a_i$ に2、$b_j$ に1を加算する

思考

1回の操作毎に、Aの合計がBの合計より1ずつ大きくなっていくので、最初からAの合計の方が大きければ無理なのは分かる。

それ以外で無理なのは？

入力例2では、Bの合計の方が大きいのに、正解はNoとなっている。実際にやってみる。

5
3 1 4 1 5
2 7 1 8 2

3 vs 2: Bへの操作が1回必要
1 vs 7: Aへの操作が3回必要（差し引き Aへの操作が2回）
4 vs 1: Bへの操作が3回必要（差し引き Bへの操作が1回）
1 vs 8: Aへの操作が4回、Bへの操作が1回必要（差し引き Aへの操作が2回）
5 vs 2: Bへの操作が3回必要（差し引き Bへの操作が1回）

ここで、最終状態の差し引きが0、またはAへの操作が残っていた場合は残りを消費することで帳尻あわせが可能

しかし、Bへの操作が残っていた場合、全体の合計から、これ以上操作することは出来ない。これで判定できる。

C - Vacant Seat

二分探索

D - Forest

森をつないで1つの木にする
頂点にコストが決められていて、辺を追加するコストは両端点のコストの合計
1度使った頂点は使えない。
追加する辺のコストを最小にせよ

解法

まず、追加する辺の数は $N-M-1$ 本。（最終的に木にした時の辺の数が $N-1$ 本、現在が $M$ 本）

そのために必要な頂点が $2(N-M-1)$ 個なので、これが $N$ より大きい場合、不可能。逆にこれさえ満たしていれば大丈夫。

各木を他と繋ぐためには、相手はどうあれ、必ず木の中の1頂点から辺を伸ばす必要がある。それは各木の最小コスト点を選べばよい。

各木から伸ばした辺の相手を考える。
より具体的に、いま、2個の連結済みの木(AとBとする)に新しい木(Cとする)を繋ごうとしている時、Cを繋ぐ辺の相手となるA,B側の頂点を考える。

すると、下図で、A,Bは2つの木を●によって繋いだ後の状態（●はA,Bそれぞれでコスト最小の点）。そこにCを繋ごうと思ったら、Cのコスト最小点と、A,Bの●以外でコスト最小点を繋ぐのがよい。

    A       B       C
    ○      ○      ○
    /\      /\      /\
   ○○    ○○    ○○
   / /\    /
  ○○●--●

これを、「A～Cを繋いだ木に、Dを繋ぐと……」と次々考えていくと、結局は「各木の中でコスト最小の点の合計」＋「それ以外の点から、全体が $2(N-M-1)$ になるまでコストが小さい方から選んだ点の合計」が答えとなる。

反省

1本の辺のコストを、2頂点で別々に考えるのは思い至らなかった。

E - Antennas on Tree

木がある
木の1頂点が指定された時、「自身からその頂点までの距離」を教えてくれる観測所を任意の頂点に設置する
どの頂点が選ばれても一意に特定できるようにしたい
最小の観測所数はいくつか

解法

特定できないのはどういう場合か。

……
  ＼
   ●
  ／|＼
 ○ ○ ○
 １ ２ ３

たとえばこんな部分木を考えると、●より上側の頂点(●含む)にいくら観測所があろうと、●の下側に観測所が無いと、○はどれも同じ距離になる。

ならばということで１に観測所を作っても、２と３はまだ区別できない。１と２に観測所を作ると、３を区別できるようになる。

つまり、「全ての頂点に対して、その子の部分木のうち、観測所が含まれなくてよいのは1つまで」と条件を読み替えられる。

ただ、その考えだけだと、こんな時に上手くいかない。

    １
   ／＼
  ２  ３
     ／＼
    ４  ５
       ／＼
      ６  ７

６か７のどちらかに観測所を1つ作るだけで「全ての頂点に対して、その子の部分木のうち、観測所が含まれなくてよいのは1つまで」という条件は満たされるが、たとえば１と４の距離が同じになってしまう。

この場合、次数が3以上の頂点を根にすることで、何故か上手くいく。それで上手くいく理由が、いまいち分からない……

    ３
   ／|＼
  １ ４ ５
 ／    ／＼
２    ６  ７

F - XOR Tree

木がある（木の問題多いな）
各辺に、0～15（0x0000～0x1111）の値が与えられている
ある経路と数値 $x(0 \le x \le 15)$ を選び、経路を構成する全ての辺に対し、$x$ をxorして更新する、という操作を繰り返し行う
全ての辺を0にできるか。できるなら、最小操作回数は。

解法

「木の辺に対して値が与えられ、経路に対しxorする」という操作は、
「木の頂点に対して値が与えられ、任意の2点を同時にxorする」と読み替えられる。全頂点の値を0にするのがゴール。

木の頂点の値が表すのは、その頂点から出ている全辺の値のxor。すると、経路の途中の頂点は同じ値を2回xorされるので変わらない、というテクニックらしい。なるほどー。これなら、考えるのが楽になる。

まず全頂点の初期値を求め、任意の2点で同じ初期値ならババ抜きのようにその2点で打ち消し合えばよい。

残るのは、0～15の頂点が、たかだか1個ずつ。制約が15とか、いかにも全探索してくださいと言わんばかりなので、そうする。

H - Generalized Insertion Sort

2000点問題にしては、まだ「何をやればいいのか理解できる」

根付き木がある（また木か！）
頂点には0～N-1までの番号があり、0が根
- 親の頂点番号 < 子の頂点番号
各頂点には、0～N-1までの値が1つずつ割り振られている
以下の操作を25000回まで行うことで、$i$ 番目の頂点に値 $i$ が割り振られている状態にする
操作
- ある頂点 $v$ を選ぶ
- 根から $v$ までの経路上の頂点の値を“回転”させる
- つまり、その時点で根に割り振られている値を $v$ に持っていき、$v$ に入っていた値はその親へスライド。親の値はその親へ…以降、根まで繰り返す
$N \le 2000$
操作手順の一例を示せ

解法

ある頂点 $v$ に対し、そこに入る値($v$)を探して根まで持ってきて、その次の操作で $v$ に入れる、ということを繰り返すとできるのはできるが、1個ずつやると回数制約的に無理。

根まで持ってくるのに $O(N)$、それを全 $N$ 頂点に行うと、計 $O(N^2)$。これを全体で $O(N \log{N})$ に抑えられたら、25000回に間に合う。

それには、解説の用語を借りると「葉パス頂点」について一度に値を設定する方法が考えられる。

       ○
     ／｜＼
    ● ○ ●
  ／ ／｜＼
 ● ○ ● ●
   ／＼   ｜
  ●  ●  ●

「各葉から、2つ以上の子を持つ頂点が出てくる手前まで辿った経路上の頂点」を「葉パス頂点」と呼ぶ。これらに正しい値を $O(N)$ で入れ、木から切り落とす。すると残りの木からは新たに葉パス頂点が生まれる。これを根が葉パス頂点になり、正しい値が入るまで繰り返す。これは、$O(\log{N})$ 以内に収まる。

具体的な操作方針は、

根の値が、現在の葉パス頂点に入るべき値以外の場合
- とっとと葉パス頂点の値が出てくるように「葉パス頂点に入るべき値が割り振られている中で、最も深い頂点」と交換
根の値が、現在の葉パス頂点に入るべき値の場合
- 値を $i$ とする
- 頂点 $i$ の属する葉パスの末端（葉）ノードから順番に見ていく
  - 頂点 $v$ を確認中、そこに入っている値を $k$ とする
  - 頂点 $v$ が「確定済み」なら、1個上へ移る
  - 確定済みで無ければ、$i<k$ なら、1個上へ移る
  - $i>k$ なら、値 $i$ を頂点 $v$ に入れて、頂点 $i$ を確定済みにする

操作毎に、「葉パス頂点に入るべき値が割り振られている中で、最も深い頂点」が分かるよう、情報を更新する。

考察中、どの変数が「値」を指すのか「頂点」を指すのかごっちゃになって大変だった。こういうのをスッキリ整理して考えられるようになりたい。

目次