きままにものづくり

日々の気付いたことなんかを書いてます。

SRM570 Div1 Easy

問題

無限に広い平面を考える。命令セットaが与えられ、T回命令セットを実行した時の原点からのマンハッタン距離を求めよ。

解法

  1. aの総和から、方向の周期fを求める。
  2. 周期fの回数だけaを実行し、マンハッタン距離の変化量を計算する。
  3. Tを周期fで割り、上で求めた変化量をかける。
  4. T%f回だけaを実行し、上で求めた値と足し合わせる。

計算量

O(N)
N : aの要素数

コード

広告を非表示にする