AtCoder Regular Contest #020 D問題 - お菓子の国の旅行

Source

AtCoder Regular Contest #020
問題文

問題概要

$N$ 個の街が一直線上にあり,街は左から $1,2,\ldots,N$ と番号が付いている.
街 $i$ と $i+1$ との間の距離 $D_i$ が与えられる.
$K$ 個の街を順番に訪れる方法で,移動距離の総和が $M$ の倍数となるような経路は何通りあるかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題.
移動中,間の街は通過するだけで,立ち寄っていないとみなす.

解法

左から順番になぞっていくDPで,状態として,(今いる場所,左から出ている使用するパスの数,使用したパスの端点の数,現在までのパスの長さ ${\rm mod}\ M$,訪れた街の数)を取る.
端点を使った回数を考慮に入れて場合の数を計算しつつ,今考えている街を,訪れずに通過する,今いる街で折り返す,今いる街を端点にする,などの場合分けをしていく.
状態数,時間計算量ともに $O(NMK^2)$.
想定解法は違う方法で公式の解説スライド http://www.slideshare.net/chokudai/arc020 を参照.$O(2^K NMK)$.

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

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
#define MD 1000000007
#define INF 1000000000

int N, M, K;
int D[200];

ll dp[110][15][4][31][12];

ll solve(int left, int path, int ends, int multi, int visited){
  int i, j, k;
  ll res = 0, tmp;

  if(dp[left][path][ends][multi][visited] >= 0) return dp[left][path][ends][multi][visited];

  if(left==N) return 0;
  if(visited==K) return 0;
  
  res += solve(left+1, path, ends, (multi + path*D[left])%M, visited);

  while(visited==K-1){
    if(ends==0) break;
    if(multi!=0) break;

    if((ends==1 && path==1) || (ends==2 && path==2)) res++;
    break;
  }

  if(path && ends<2){
    res += solve(left+1, path-1, ends+1, (multi + (path-1)*D[left])%M, visited+1);
  }

  if(ends<2 && path<12){
    res += solve(left+1, path+1, ends+1, (multi + (path+1)*D[left])%M, visited+1);
  }

  if(path >= 2){
    if(ends==1) tmp = path / 2;
    if(ends==2) tmp = path / 2;
    if(ends==0) tmp = path / 2 - 1;
    if(tmp>=0) res += tmp * solve(left+1, path-2, ends, (multi + (path-2)*D[left])%M, visited+1);
  }

  if(path < 12){
    if(ends==1) tmp = path / 2 + 1;
    if(ends==2) tmp = path / 2;
    if(ends==0) tmp = path / 2 + 1;
    res += tmp * solve(left+1, path+2, ends, (multi + (path+2)*D[left])%M, visited+1);
  }

  res += path * solve(left+1, path, ends, (multi + path*D[left])%M, visited+1);
  
  res %= MD;
  return dp[left][path][ends][multi][visited] = res;
}

int main(){
  int i,j,k,l,m;
  ll res = 0, tmp;

  scanf("%d%d%d",&N,&M,&K);
  rep(i,N-1) scanf("%d",D+i);
  D[N-1] = 0;

  rep(i,110) rep(j,15) rep(k,4) rep(l,31) rep(m,12) dp[i][j][k][l][m] = -1;

  res = solve(0, 0, 0, 0, 0);
  res = (res*2)%MD;
  printf("%d\n",(int)res);

  return 0;
}

Current time: 2017年11月19日12時17分56秒
Last modified: 2014年03月30日00時17分24秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC020 ARC_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン: