Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #96 DIV1 D問題 - Constants in the language of Shakespeare (この記事を編集する[管理者用])

Source

Codeforces Beta Round #96 DIV1 D問題 (2000pt)
Problem description

問題概要

2進数で10^6桁以下の正整数nが与えられる.
最初は0で,任意のkに対して,2^kを加えるか,2^kを引くかを行うことができる.
nにするまでの最小手数と,その手順を1個求める問題.

解法

ad-hoc.
2進数表示で,上の桁から見ていく.
1が1個しか連続していないなら,その桁を足せば良い.
1が2個以上連続しているなら,その上の桁を足して,最後の桁を引いたほうが良い.
ただし,この時,1が連続している間に,0が1個だけ含まれているなら,それは,1と見なして後から引いたほうが良い.
などとやれば良い.
下から見ていって,今いる場所,繰り上がりが必要な状態か否かを状態として,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)

char in[1100000];
int fg[1100000], res[1100000], res_size;

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

  scanf("%s",in);
  n = strlen(in);

  res_size = 0;
  rep(i,n) if(in[i]=='1'){
    if(i+1==n || in[i+1]=='0'){
      res[res_size] = n-i-1;
      fg[res_size] = 1;
      res_size++;
      continue;
    }

    res[res_size] = n-i;
    fg[res_size] = 1;
    res_size++;
    
    for(j=i+1;j<=n;j++){
      if(j==n || (in[j]=='0' && (j+1==n || in[j+1]=='0'))){
        res[res_size] = n-j;
        fg[res_size] = -1;
        res_size++;
        i = j; break;
      }

      if(in[j]=='0'){
        res[res_size] = n-j-1;
        fg[res_size] = -1;
        res_size++;
      }
    }
  }

  printf("%d\n",res_size);
  rep(i,res_size){
    if(fg[i]==1) putchar('+'); else putchar('-');
    printf("2^%d\n",res[i]);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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