yukicoder No.48 ロボットの操縦 解説

問題文

解説

まず、いったん次の問題について考えよう。

太郎君はロボットを遠隔で操縦している。
このロボットは現在$(0,0)$の座標に立っていて北の方向を向いている。
太郎君はいまこのロボットを$(X,Y)$の座標に移動させたいと思っている。
ロボットに出来る命令は、$1$回につき以下のうちいずれかの命令を選んで指示することができる。
・向いている方向に $K$距離だけ前進する。$K$は、$1\leqq K\leqq L$ の範囲で、命令のたびに指定することができる。
また、好きな回数だけ向いている向きを変えることができる。
このとき、あり得る最小の操作回数を求めよ。

まず、$x$座標と$y$座標はそれぞれ独立である。よって、それぞれを一次元のように考えると、No.46 はじめのn歩と同じような問題になる(はじめのn歩)。この問題でも、できるだけ$K$を$L$に近づけて歩かせるのがいいだろう。

では、本題に戻る。
回転回数に関して、じつは高々2回で完結する。
$0\leqq Y$なら、先に$Y$を動かしてから$X$が0かどうかによって回転すればよい。このとき、回転回数は$0$または$1$。
$0> Y$なら、先に$X$を動かしてから$Y$を動かせばよい。この時、回転回数は$2$回。
では、回転回数はどのように求まるか。これは、次のように求まる。
・$Y\geqq 0$&$X=0$なら回転回数は$0$。
・$Y\geqq 0$&$X!=0$なら回転回数は$1$。
・$Y<0$なら回転回数は$2$。
よって、回転回数及び移動回数の総和を求めれば完結する。
$X=10^9,Y=10^9,l=1$のとき答えが32bit型に収まらないので、long long型を使おう。

C++での解答例

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
//upfloorは移動回数を正確に求める関数
ll upfloor(ll x, ll m) {
  ll r=(x%m+m)%m;
  return (x-r)/m+(bool)(x%m);
}

int main() {
  ll x,y,l;cin>>x>>y>>l;
  ll idou=upfloor(abs(x),l)+upfloor(abs(y),l);
  ll kai;
  if(y>=0&&x==0)kai=0;
  else if(y>=0)kai=1;
  else kai=2;
  cout<<idou+kai<<endl;
}