AtCoder Beginner Contest 162 D～F問題メモ

AtCoder Beginner Contest 162

D - RGB Triplets

• R,G,Bの3種の文字からなる長さ $N$ の文字列 $S$ が与えられる
• 以下の条件を全て満たすindexの組 $(i,j,k)$ の個数を求めよ
  • (1) $i \lt j \lt k$
  • (2) $(S_i,S_j,S_k)$ は全て異なる（R,G,Bが1つずつ）
  • (3) $j-i \neq k-j$ （間隔が異なる）
• $1 \le N \le 4000$

まず、条件(3)が無ければ、答えは $S$ に含まれる（Rの個数）×（Gの個数）×（Bの個数）で求められる。

また、条件(3)の候補となるindexの組はたかだか $O(|S|^2)$ しかないので、全て調べられる。

間隔が同じ $i,j,k$ について、条件(1)(2)を満たしているものがあれば、答えから引けばよい。

E - Sum of gcd of Tuples (Hard)

• 各項が $1～K$ のいずれかの整数である長さ $N$ の数列は、$K^N$ 個ある
• 全てについて最大公約数を求め、その総和を求めよ
• $2 \le N \le 10^5$
• $1 \le K \le 10^5$

こういうの苦手……に加え、実際の計算量と直感的な計算量が合わない。

数列のGCDが1以外の値（$g$ とする）を取るというのは、以下の2つを共に満たしているときである。

• 全ての項が $g$ の倍数
• 全ての項を $g$ で割ると、その数列のGCDは1

さらに全ての項を $g$ で割った時、そこに存在しうる数字は、$1～\dfrac{K}{g}$ のいずれかである。（切り捨て）

ということは、$K$ について以下のような関数を定義すれば、何となく再帰的に求められそう。

$f(k) =$ 各項が $1～k$ の長さ $N$ の数列で、GCDが1になるものの個数

答えは、$f(\dfrac{K}{1})+2f(\dfrac{K}{2})+3f(\dfrac{K}{3})+...+Kf(\dfrac{K}{K})$ となる。

また、個数の帳尻を合わせると $k^N = f(\dfrac{k}{1})+f(\dfrac{k}{2})+f(\dfrac{k}{3})+...+f(\dfrac{k}{k})$ となる。

つまり、$f(k) = k^N - f(\dfrac{k}{2}) - f(\dfrac{k}{3}) - ... - f(\dfrac{k}{k})$ で求められる。

ただし、$f(1)=1$ とする。

さて、$\dfrac{k}{2},...,\dfrac{k}{k}$ だが、$k$ が大きくなるにつれ同じ値が相当数含まれる。特に、$\dfrac{k}{k/2}$ 以降に関しては必ず1となる。

K=14
割る数   1   2   3   4   5   6   7   8   9  10  11  12  13  14
        14   7   4   3   2   2   2   1   1   1   1   1   1   1

なので、一度求めた $f(k)$ についてはメモ化しておくことで、$f(k)$ を再帰的に求めていっても、そこまで大した計算量にならないで済む。

具体的には、最大ケース $N=10^5,K=10^5$ で、下記get()が呼ばれるのが390754回、さらにその中でcntに存在せずに具体的な計算に進むのが630回。

F - Select Half

• 長さ $N$ の整数列 $A_1,...,A_N$ が与えられる
• この中から、ちょうど $\dfrac{N}{2}$（切り捨て）個の整数を、どの2個も連続しないように選ぶ
• 選んだ要素の和としてあり得る最大値を求めよ
• $2 \le N \le 2 \times 10^5$
• $|A_i| \le 10^9$

偶数の時は簡単。

先頭から1つおきに取っていき、どこかで2つ間を空け、そこからまた1つおきに取っていく、という方法しかない。（先頭、末尾の長さが0の場合も含める）

3  1  4  1  5  9  2  6
~     ~        ~     ~

「先頭から1つおき」「末尾から1つおき」に取ったときの累積和を求めておき、切り替える箇所を全探索すればよい。

              3  1  4  1  5  9  2  6
先頭から  0   3     7    12    14
末尾から        17    16    15     6   0
          ↓
          0   3   7  12  14
       + 17  16  15   6   0
       --------------------
         17  19  22  18  14   →  最大値は22

奇数の時が困る。

たとえば $N=11$ なら5個だけ選べばよいので、間を2つ空けてよい場所が2つ（または間を3つ空けてよい場所が1つ）ある。

3  1  4  1  5  9  2  6  5  3  5
~     ~        ~     ~        ~

間を空ける場所全探索は、$O(N^2)$ かかるので厳しそう。DPで解けないか考える。

ここで、問題の条件は「取らない数を最小化する」ことでも達成できる。よって、問題を以下のように言い換える。

• $A_1,...,A_N$ から、$\dfrac{N}{2}$（切り上げ）個取った総和を最小化する
• 2つ以上連続して取らないことはできない
• 直前に取った状態で連続して取ることができるのは、2回まで
• 初期状態は「直前に取った状態」であるとする

こうすると、以下のDPで求めることができる。2つ以上連続で取らないことが無いので、2つ前までの状態があればよく、多少、遷移もわかりやすくなる。

• $DP[i][j] = A_i$ まで考えて、$A_i$ は取り、あと連続して取ることができる残り回数が $j$ 回の時の総和の最小値
• 初期条件（$i$ は0-indexとして）
  • $DP[-2] = [INF, INF, INF]$
  • $DP[-1] = [INF, INF, 0]$

INFは、その条件が不可能なことを示す。

• 遷移
  • $DP[i][2] = \min(INF, DP[i-2][2] + A_i)$
  • $DP[i][1] = \min(INF, DP[i-2][1] + A_i, DP[i-1][2] + A_i)$
  • $DP[i][0] = \min(INF, DP[i-2][0] + A_i, DP[i-1][1] + A_i)$

各遷移、INFの次は1個空けて取る操作、その次は連続して取る操作を示す。

最終的に、$DP[N-1][1]$ または $DP[N-2][0]$ の小さい方が答えとなる。（$DP[N-2][2]$ は取る数が足りてない）

           3  1  4  1  5  9  2  6  5  3  5
j 0  -  -  -  4  -  5  - 14  - 15  - 17  -   ←┬ 17,19の小さい方が答え
  1  -  -  3  -  5  -  7  -  9  - 14  - 19   ←┘
  2  -  0  -  1  -  2  - 11  - 17  - 20  -
  
各遷移のイメージ
           x  →  min(x,y)+Ai
           -  y ↗

元の問題の答えは、$A_1～A_N$ の総和から、言い換えた問題の答えを引くことで求められる。