Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

ARC 005 D - 連射王高橋君 (We have nothing to do with him) (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #005
問題文

問題概要

0123456789+=のボタンのある電卓がある.
壊れているボタンが与えられる.ただし01+=は壊れていない.
最終的に表示させたい数 (10^18以下) を表示するまでに押さなくてはいけないボタンの回数の最小値化したい.
そのような方法を1つ出力する問題.

解法

数字をそのまま打てるならそうする.
そうでなければ,DP + 経路復元する.
まず,使える数字を使ってk (200以下ぐらい) を作る最小個数の組み合わせは最初にDPで計算しておく.
後は,各桁ごとにDPしていく.下の桁から見ていく.
何個の数字の和で作るかは全探索する.
状態は,どの桁を見ているか,繰り上がりはいくらあるか,前の桁で使った数の数(足し合わせるものの中でその桁が存在する数).

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)

int dp[200], pat[200][200];
int ok[20], ok_size;

int n;
char in[1000];
int dp2[20][20][20][20];

int res_mx;
char res_str[100][100];

int calc(int dig, int kuria, int bef_us, int mx_us){
  int i, j, dd, tar;
  int mx;
  int bf, bf_st, bf_ed;
  int next_k;
  int res = 20000, tmp;

  if(dp2[dig][kuria][bef_us][mx_us] >= 0) return dp2[dig][kuria][bef_us][mx_us];
  if(dig==n && kuria==0) return mx_us;
  if(dig==n) return res;

  dd = in[n-1-dig];
  
  bf_st = 0;
  bf_ed = bef_us;
  if(dig==0) bf_ed = 15;
  REP(bf,bf_st,bf_ed+1){
    mx = mx_us;
    if(dig==0) mx = bf;
    
    rep(next_k,18){
      tar = dd - kuria + 10*next_k;
      if(tar < 0 || tar >= 200) continue;
      if(dp[tar] > bf) continue;
      tmp = calc(dig+1, next_k, bf, mx) + bf;
      if(res > tmp) res = tmp;
    }
  }

/*  printf("%d %d %d %d: %d\n",dig,kuria,bef_us,mx_us,res);*/
  return dp2[dig][kuria][bef_us][mx_us] = res;
}

void solve(int dig, int kuria, int bef_us, int mx_us){
  int i, j, dd, tar;
  int mx;
  int bf, bf_st, bf_ed;
  int next_k;
  int res, tmp;

  res = calc(dig, kuria, bef_us, mx_us);
  if(dig==n) return;

  dd = in[n-1-dig];
  
  bf_st = 0;
  bf_ed = bef_us;
  if(dig==0) bf_ed = 18;
  REP(bf,bf_st,bf_ed+1){
    mx = mx_us;
    if(dig==0) mx = bf;
    
    rep(next_k,11){
      tar = dd - kuria + 10*next_k;
      if(tar < 0 || tar >= 100) continue;
      if(dp[tar] > bf) continue;
      tmp = calc(dig+1, next_k, bf, mx) + bf;
      if(res == tmp){
        if(dig==0) res_mx = mx;
        rep(i,bf) res_str[i][88-dig] = pat[tar][i]+'0';
        solve(dig+1, next_k, bf, mx);
        return;
      }
    }
  }

}

int main(){
  int i,j,k,l,m;

  scanf("%s",in);
  ok_size = strlen(in);
  rep(i,ok_size) ok[i] = in[i]-'0';

  scanf("%s",in);
  n = strlen(in);
  rep(i,n) in[i] -= '0';

  rep(i,n){
    rep(j,ok_size) if(in[i]==ok[j]) break;
    if(j==ok_size) break;
  }
  if(i==n){ rep(i,n) putchar('0'+in[i]); puts(""); return 0; }

  dp[0] = 0;
  rep(k,200) pat[0][k] = 0;
  REP(i,1,200){
    dp[i] = 220;
    rep(j,ok_size){
      k = i - ok[j];
      if(k < 0) continue;
      if(dp[i] > dp[k] + 1){
        dp[i] = dp[k] + 1;
        rep(l,dp[k]) pat[i][l] = pat[k][l];
        pat[i][dp[i]-1] = ok[j];
      }
    }
    REP(k,dp[i],200) pat[i][k] = 0;
  }

/*  rep(i,20) printf("%d %d\n",i,dp[i]);*/

  rep(i,20) rep(j,20) rep(k,20) rep(l,20) dp2[i][j][k][l] = -1;
  k = calc(0,0,0,0);
/*  printf("%d\n",k);*/

  rep(i,100) rep(j,100) res_str[i][j] = '\0';
  solve(0,0,0,0);
  rep(i,res_mx){
    if(i) putchar('+');
    rep(j,100) if(res_str[i][j]!='\0') putchar(res_str[i][j]);
  }
  puts("=");

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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