ABC351 C Merge the ballsを理解し忘れないようにする

https://atcoder.jp/contests/abc351/tasks/abc351_c

問題概要

N個のボールがあり、ボールの大きさは$2^{A \times i}$である。
以下の操作をN回行い、i個目のボールを列の一番右に付け加えた後、次の手順を繰り返します。

1. 列にあるボールが 1つ以下ならば操作を終了する。
2. 列にあるボールのうち右から 1 番目のものと 2 番目のものの大きさが 異なる ならば操作を終了する。
3. 列にあるボールのうち右から 1 番目のものと 2 番目のものの大きさが 等しい ならば、2 つのボールを取り除き、「取り除かれた 2 つのボールの大きさの和」の大きさのボール 1 つを列の一番右に付け加える。その後、1. に戻り、手順を繰り返す。
   最後の操作が終わった後のボールの数を出力する

現状

そのまま操作をN回やろうとするとAiは最大$10^9$が入るので、$2^{10 \times 9}$でlong longの制約を超えてしまう

解説見た

$2^a + 2^a = 2^a+1$であることを利用してaの数のみ管理すればいい。
末尾と末尾-1の値が同じ場合に2つを取り除いて末尾の値+1を配列に入れる。

具体例があった方が分かりやすいので入力例を見る

4
2 1 1 3

• 空配列を用意
• 2を入れる[2]
• 1を入れる[2,1]
• 1を入れる[2,1,1]
• 末尾２つが同じなので取り除いて1+1=2を入れる[2,2]
• 末尾２つが同じなので取り除いて2+1=3を入れる[3]
• 配列の個数は1

$2^{A \times i}$で考えても答えは同じだが、Aiは最大$10^9$が入るので、$2^{10 \times 9}$でlong longの制約を超えてしまう。よって、上記のAiのみで管理する考え方が必要になる。

• 空配列を用意
• $2^2=4$を入れる [4]
• $2^1 = 2$を入れる [4,2]
• $2^1 = 2$を入れる [4,2,2]
• 末尾２つが同じなので取り除いて$2^2=4$を入れる [4,4]
• 末尾２つが同じなので取り除いて$2^2+2^2=2^3=8$を入れる [8]
• 配列の個数は1

提出コード

https://atcoder.jp/contests/abc351/submissions/57105139

参考元

解説放送

補足

• $a^n$のnのことをべき乗(指数)という
  • https://www.try-it.jp/chapters-323/sections-366/lessons-371/
• 指数同士の計算は指数が同じでなければ計算できない。
  • $2^a + 2^a = 2^a+1$
  • https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1238214412
• $2^a + 2^a = 2^a+1$になる理由
  • $2^a*2$と同じだから
  • $a = 3$の場合、$2^3+2^3 = 2^3*2 = 16$