第2回 ドワンゴからの挑戦状 本選 A問題 - 通勤

Source

第2回 ドワンゴからの挑戦状 本選オープンコンテスト
問題文オープンコンテスト

問題概要

ニワンゴ君が,$N$ メートル離れたオフィスに移動する.
その際,最初に $\ell=1$ として,以下のどちらかのステップを繰り返す.

  1. 前に向かって $\ell$ メートル飛ぶ
  2. $\ell$ の値をニコ数倍する

ただし,ニコ数とは,
\begin{align*}
& 2, 25, 252, 2525, 25252, 252525, \ldots, \\
& 5, 52, 525, 5252, 52525, 525252, \ldots
\end{align*}である.
ちょうど $N$ メートル前に進むための飛ぶ回数(上のステップ1.の回数)の最小値を求める問題.

解法

$\ell=1$ から $\ell=x$ にする操作を行うとすると,残りは $x$ の倍数しか進めなくなるので,残りが $x$ の倍数になるまでは $\ell=1$ の段階で飛ぶ必要がある.
また,逆に,$\ell = 1$ の段階でそれ以上飛ぶことは損にしかならない(それ以上追加で飛ぶ場合は,$x$ の倍数回飛ぶことになり,それは $\ell=x$ となってから飛んだ方が得).
よって,入力 $N$ に対する答えは $f(N)$ と書くと,ニコ数 $x$ に対して,
\begin{align*}
f(n) = \min_x \left( f( \left\lfloor n/x \right\rfloor ) + (n\ \mathrm{mod}\ x)\right)
\end{align*}が成り立つ.
これを再帰的に計算していった時,計算しなければいけない $f(n)$ の数はそんなに多くなく,適当にメモ化してやれば通る.
実際に,$10^{18}$ 以下のニコ数の積で書ける整数は数十万個程度らしく,状態数もその程度.

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

template<class S, class T> inline void chmin(S &a, T b){if(a>b)a=b;}

char memarr[77000000]; void *mem = memarr;

template<class T>
struct ullHash{
  ull *key; T *val; unsigned memory, size, mask;

  void clear(){memset(val,0,size*sizeof(T));}
  void clear(int sz){size=1;while(size<sz)size*=2;mask=size-1;clear();}
  void init(int mem, int sz){memory=mem;size=1;while(size<sz)size*=2;mask=size-1;if(memory<size)memory=size;key=(ull*)malloc(memory*sizeof(ull));val=(T*)malloc(memory*sizeof(T));if(size)clear();}
  int function(ull a){return (((a*123456789789ULL)>>32)*987654321321ULL)&mask;}
  T get(ull a){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;if(key[i]!=a) return 0;return val[i];}
  void set(ull a, T v){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;key[i]=a;val[i]=v;}
  T increase(ull a, T v = 1){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;key[i]=a;return val[i]+=v;}
};

ll N;
ll arr[10000]; int sz;
ullHash<int> hs;

ll solve(ll n){
  int i, res = 100;
  ll tmp;

  if(n==0) return 0;
  tmp = hs.get(n) - 1;
  if(tmp >= 0) return tmp;

  rep(i,sz){
    tmp = solve(n/arr[i]) + n%arr[i];
    chmin(res, tmp);
  }

  hs.set(n, res+1);
  return res;
}

int main(){
  int res, loop;
  ll now; double dn;

  hs.init(500000,500000);

  now = dn = 2;
  for(loop=0;;loop++){
    arr[sz++] = now;
    if(loop%2==0) now = now * 10 + 5, dn = dn * 10 + 5;
    else          now = now * 10 + 2, dn = dn * 10 + 2;
    if(dn > 2e18) break;
  }

  now = dn = 5;
  for(loop=1;;loop++){
    arr[sz++] = now;
    if(loop%2==0) now = now * 10 + 5, dn = dn * 10 + 5;
    else          now = now * 10 + 2, dn = dn * 10 + 2;
    if(dn > 1e18) break;
  }

  reader(&N);
  res = solve(N);
  writerLn(res);

  return 0;
}

Current time: 2017年07月24日15時50分44秒
Last modified: 2016年02月15日04時41分23秒 (by laycrs)
Tags: Competitive_Programming AtCoder dwango2016-finals
トップページに戻る

Logged in as: unknown user (not login)

ログイン: