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: 2024年04月27日08時31分15秒
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)

ログイン：