Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2119-b810e7fa
この記事にトラックバックする(FC2ブログユーザー)

September 2011 Cook-Off 3問目 - Last Digit Sum (この記事を編集する[管理者用])

Source

codechef September 2011 Cook-Off 3問目
Problem Statement

問題概要

S(N)をNを10進数表記したときに出てくる奇数+出てくる偶数*2の和とする.例は問題文を参照.
D(N)はS(N) mod 10とする.
 D(A) + D(A+1) + … + D(B)
を求める問題.
A, Bは400000000以下.

解法

D(1) + D(2) + … + D(n)を高速に求めれられれば良い.
D(k)が0になるものの数,1になるものの数,…,9になるものの数をDPで求める.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

ll dp[20][2][10];
ll arr[20];

void go(int depth, int fg){
  int i,j,k,add;
  int next_fg;

  if(dp[depth][fg][0] >= 0) return;

  rep(i,10) dp[depth][fg][i] = 0;

  if(depth==0){
    rep(i,10){
      add = i; if(i%2==0) add *= 2;
      
      if(!fg && arr[depth] < i) continue;
      dp[depth][fg][add%10]++;
    }
    return;
  }

  rep(i,10){
    add = i; if(i%2==0) add *= 2;
    
    next_fg = fg;
    if(i < arr[depth]) next_fg = 1;
    if(!next_fg && i > arr[depth]) continue;

    go(depth-1, next_fg);
    rep(k,10) dp[depth][fg][(k+add)%10] += dp[depth-1][next_fg][k];
  }
}

ll solve(int A){
  int i,j,k;
  ll res;

  if(A<=0) return 0;

  rep(i,20) rep(j,2) rep(k,10) dp[i][j][k] = -1;
  res = 0;

  rep(i,20){
    arr[i] = A%10;
    A /= 10;
  }

  go(19, 0);
  rep(i,10) res += dp[19][0][i] * i;

  return res;
}

int main(){
  int i,j,k,l,m,n;
  int A, B;
  ll res;
  int size;

  scanf("%d",&size);
  while(size--){
    scanf("%d%d",&A,&B);
    res = solve(B) - solve(A-1);
    printf("%lld\n",res);
  }


  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2119-b810e7fa
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。