AGC 024

A - Fairness

• 整数 $A,B,C$ がある
• $K$ 回、以下の置き換えを行う
  • $A=B+C$
  • $B=A+C$
  • $C=A+B$
• $K$ 回の置き換え後の $A-B$ の値を求めよ
• ただし、答えの絶対値が $10^{18}$ を超える場合は'Unfair'を出力せよ

A=5, B=7, C=9
1回目 A=16 B=14 C=12
2回目 A=26 B=28 C=30
3回目 A=58 B=56 C=54

各回の操作後の $A,B,C$ の値は、$xA+yB+zC$ で表せる。ここで、その値を $(x,y,z)$ で表すと、

0回目 A=(1,0,0) B=(0,1,0) C=(0,0,1)   A-B=( 1,-1, 0)
1回目 A=(0,1,1) B=(1,0,1) C=(1,1,0)   A-B=(-1, 1, 0)
2回目 A=(2,1,1) B=(1,2,1) C=(1,1,2)   A-B=( 1,-1, 0)
3回目 A=(2,3,3) B=(3,2,3) C=(3,3,2)   A-B=(-1, 1, 0)
4回目 A=(6,5,5) B=(5,6,5) C=(5,5,6)   A-B=( 1,-1, 0)
...

で、結局 $K$ 回の操作後の $A-B$ の値は、$A,B$ の初期値を $A_0,B_0$ として、

• $K=$ 奇数: $B_0-A_0$
• $K=$ 偶数: $A_0-B_0$

となる。ちなみに、$A_0,B_0 \le 10^9$ なので、答えの絶対値は $10^{18}$ を超えない。

B - Backfront

• $1$ ～ $N$ の整数を並び替えて出来る数列 $P=(P_1,P_2,...,P_N)$
• 以下の操作を繰り返して、昇順の $(1,2,...,N)$ に並び替える
  • $P$の要素を1つ選び、先頭または末尾の好きな方に移動する
• 最小の操作回数を求めよ

   2 5 3 6 4 1
→ 1 2 5 3 6 4 (1を先頭に移動)
→ 1 2 3 6 4 5 (5を末尾に移動)
→ 1 2 3 4 5 6 (6を末尾に移動)

3回で並び替えられた。

まず、1ずつ増加して昇順に並んでいる最長部分列を探す。

2 5 3 6 4 1  →  2 _ 3 _ 4 _

そしたら、その部分は動かさず、それ以外の要素を適切な順で先頭または末尾に移動するのが最良となる。

┌───────┐
↓              │
  2  5  3  6  4  1
     │    │      ↑
     └──┴───┘

なので、回数を求めるだけなら $N-(最長部分列の長さ)$ を求めればよい。

C - Sequence Growing Easy

• 長さ $N$ の数列 $X=(X_1,X_2,...,X_N)$ があり、最初は全ての要素が $0$
• 長さ $N$ の数列 $A$ がある
• $X$ に以下の操作を繰り返すことで、$A$ と同じにする
  • $X_{i+1}$ を、$X_i+1$ で置き換える（$1 \le i \le N-1$）
• 同じに出来る場合、操作回数を出力せよ
• 出来ない場合、$-1$ を出力せよ

A = { 0 1 2 3 3 4 2}
↓
X   { 0 0 0 0 0 0 0}
    { 0 0 1 0 0 1 0}  (i=2,5に操作を適用)
    { 0 0 1 2 0 1 2}  (i=3,6に操作を適用)
    { 0 0 1 2 3 1 2}  (i=4に操作を適用)
    { 0 1 2 3 3 1 2}  (i=1→2→3の順に操作を適用)
    { 0 1 2 3 3 4 2}  (i=5に操作を適用)

9回で同じに出来た。

まず、無理なケース。

• $X_1$ は変えられないため、$A_1$ が0以外なら無理
• $A_{i+1}$ が、$A_i$ より2以上大きいような $i$ があれば無理

それ以外は可能。

$A_i$ と $A_{i+1}$ を比べた時、$A_i+1=A_{i+1}$ なら、$X_{i+1}$ は $X_i$ を目標の値にしてから1回の操作で $A_{i+1}$ にできる。

逆にそうで無い場合、その値を作るために0 1 2 3 … と“1から積み上げて”いかないといけない。$A_i=v$ だった場合、$v$ 回かかる。

“1から積み上げる”必要のある値だけを末尾から作ることを考えると、自然と $X$ は $A$ と同じにできる。

A = { 0 1 2 3 3 4 2}
            ~   ~ ~  ←1から積み上げる必要のある数字
X   { 0 0 0 0 0 1 2}  2回の操作で1,2を作る（2が残る）
    { 0 0 1 2 3 4 2}  4回の操作で1～4を作る（3,4が残る）
    { 0 1 2 3 3 4 2}  3回の操作で1,2,3を作る

D - Isomorphism Freak

• $N$ 頂点の木 $G$ がある
• $G$ には木であることを保ったまま任意に頂点と辺を追加してもよい。追加後の木を $T$ とする
• $T$ の頂点を何色かで塗り分ける
• 同じ色で塗った頂点同士は、その頂点を根とした時の木が同型になっていないといけない
• 塗り分けるために必要な最小の色数と、その中で葉となる頂点が最小となる場合の個数を求めよ

木が同型とは、こんな木があったとして、

    ○
   ／＼
  ●  ●
  /\  /\
 ○○○○

●の頂点を根としたら、どちらも

    ●
  ／｜＼
○  ○  ○
        ｜
        ○
        /\
       ○○

という形になる。

過不足のないように説明しようとすると本家の問題文にあるような難しい書き方になるが、要はこの頂点のつながり方が同じならよい。

$T$ がどのような木なら、根とした時に同型となる頂点をうまく増やし、色数を減らせるだろうか。

ある中心となる頂点または辺を1つ決めて、そこに繋がる部分木が同じであれば、中心からの距離が等しい頂点同士は、同じ色に出来そう。部分木の途中で枝分かれがあったら、その枝分かれ以下も各木でみんな等しくする。

      ○       ←中心となる頂点
    ／｜＼
  ○  ○  ○   ←同じ色に出来る
  /\  /\  /\
 ○○○○○○  ←同じ色に出来る

           ↓中心となる辺
     ○─────○       ←同じ色に出来る
   ／｜＼      ／｜＼
 ○  ○  ○  ○  ○  ○   ←同じ色に出来る
 /\  /\  /\  /\  /\  /\
○○○○○○○○○○○○  ←同じ色に出来る

逆に中心からの距離が異なる頂点同士は、根とした時の木の深さが必ず異なるため、同型にならない＝同じ色に出来ない。

よって、中心はなるべく深さが浅くなるような頂点または辺を選ぶべき。つまり、木の直径を求め、その真ん中を採用すればよい。中心さえ決めれば、部分木が同じになるように頂点を追加するのは何とでもなる。

• 直径の頂点数が偶数なら、真ん中の2つを結ぶ辺を中心とする。
• 直径の頂点数が奇数なら、真ん中の頂点か、またはそこから伸びる辺を中心とする。（葉の数が最小となるものを全探索する）

最小の色数は、直径の頂点数の半分(切り上げ)となる。

次に、葉の個数を求める。

中心となる頂点や辺を決めたら、$G$ に存在する各頂点の子の数を調べ、各深さで最大のものを取得する。

G
   ○─────○       ←3
  ／＼       ／｜＼
 ○  ○    ○  ○  ○   ←2
 /\  ｜    ｜      /\
○○ ○    ○     ○○  ←(0)

この場合、$T$ の葉の個数は、$3 \times 2 \times 2$(中心が辺の場合、部分木が2つあるので2倍)で、12個となる。

G に頂点を追加した結果
     ○─────○
   ／｜＼      ／｜＼
 ○  ○  ○  ○  ○  ○
 /\  /\  /\  /\  /\  /\
○○○○○○○○○○○○  ←12個