[ABC368 C] Triple Attack

https://atcoder.jp/contests/abc368/tasks/abc368_c

3の倍数なら3で、そうでないなら1な問題。

問題を要約する

• 基本の攻撃力は1ダメージだが3ターンごとに会心の一撃3ダメージが出る
• 複数並んでいる敵を前から順に倒す
• 何ターン目ですべての敵を倒し終わるか？

自力実装 (TLE)

gets.to_i                        # => 3
HP = gets.split.collect(&:to_i)  # => [6, 2, 2]
t = 0
until HP.empty?
  t += 1
  if t.modulo(3).zero?
    HP[0] -= 3
  else
    HP[0] -= 1
  end
  if HP[0] <= 0
    HP.shift
  end
end
p t                              # => 8

入力例1は通ったが、入力例2で固まった。なんとなく 敵のHP / 会心の一撃3 とすれば、会心の一撃の回数が一度で求まり、ループ回数を減らすことができそうに思えたが、残り2回分のターンで与えらるダメージ 1 と 1 の扱いをどうすればいいのかわからなくなってしまった。

解説によると 敵のHP / 5 とすればよかったらしいのだが──

その 5 はどこから来た？

ターン毎のダメージを並べると、

ターン	1	2	3	4	5	6	7	8	9
ダメージ	1	1	3	1	1	3	1	1	3

1 1 3 の繰り返しになっている。つまり、5 は 3 ターン分の合計ダメージ量のことだった。

ということは、

• 3ターンで5ダメージ

なので、敵を瀕死状態にするには、

• (敵のHP / 5ダメージ) * 3ターン

必要だとわかる。

このあとがいまいち美しくないが、残りの HP は地道に削っていく。

ターンを一気に進める実装 (TLE)

以上を踏まえて実装したのがこれ。

gets.to_i                        # => 9
HP = gets.split.collect(&:to_i)  # => [1, 12, 123, 1234, 12345, 123456, 1234567, 12345678, 123456789]
t = 0
until HP.empty?
  q, HP[0] = HP[0].divmod(5)     # => [0, 1], [2, 2], [24, 3], [246, 4], [2469, 0], [24691, 1], [246913, 2], [2469135, 3], [24691357, 4]
  t += q * 3                     # => 0, 7, 81, 822, 8232, 82305, 823045, 8230452, 82304526
  until HP[0] <= 0
    t += 1
    if t.modulo(3).zero?
      HP[0] -= 3
    else
      HP[0] -= 1
    end
  end
  HP.shift
end
p t                              # => 82304529

入力例2も固まらなくなった。しかし提出すると TLE になる。

最終的に通った実装 (AC)

169 ms

gets.to_i                        # => 3
HP = gets.split.collect(&:to_i)  # => [6, 2, 2]
t = 0
HP.each do |hp|
  q, hp = hp.divmod(5)           # => [1, 1], [0, 2], [0, 2]
  t += q * 3                     # => 3, 4, 6
  until hp <= 0
    t += 1
    if t.modulo(3).zero?
      hp -= 3
    else
      hp -= 1
    end
  end
end
p t                              # => 8

いまいち腑に落ちないのだけど、最大20万件の配列要素を添字でアクセスしたり shift したりしたのが良くなかったようだ。Array#shift はポインタが隣にずれるだけで遅くないはずだけど、O(1) であったとしても、それらを20万回実行する時点でだめだということか。