Codeforces 95 B. Lucky Numbers

問題

super lucky numberとは、各桁が4または7であり、
4の現れる回数と7の現れる回数の等しいような数を言う。

与えられた数n以上の、最小のsuper lucky numberを求めよ。

制約条件

n≦10^5

方針

なんかBなのに難しい気が……自分がこういう問題苦手なだけなのだろうか。

頭から数字を見ていき、4,7でない数字が最初に現れたら、そこが数字を替える候補である。
そこの数字を変えてダメな場合は、一桁ずつ左へ戻りながら、
そこの数字を変えてsuper lucky numberが作れるかを見る。

super lucky numberが作れるかは、
今までに出現した4の数および、7の数、現在の位置から、
残りの4の数と7の数についての方程式が立てられ、それが0以上残りの桁数以下の整数解を持つか見てやることで判定できる。

ソースコード

なんか冗長。

string in;
int n;
void run(){
  cin>>in;
  n=in.size();
  in=(n%2?"0":"00")+in;
  
  int p=n%2?1:2, four=0,seven=0;
  n=in.size();
  for(;p<n;p++){
    if(in[p]=='4')four++;
    else if(in[p]=='7')seven++;
    else break;
  }
  for(;p>=0;p--){
    if(in[p]=='4')four--;
    else if(in[p]=='7')seven--;
    
    int rest=n-p, tmp=seven-four+rest;
    if(tmp%2!=0)goto FAIL;
    tmp/=2;
    if(tmp<0||tmp>rest)goto FAIL;
    if(in[p]>='7'||in[p]>='4'&&abs(seven+1-four)>rest-1)goto FAIL;
    break;
    FAIL:;
  }
  if(in[p]>='4')in[p++]='7', seven++;
  for(;p<n;p++){
    int rest=n-p-1,tmp=seven-four+rest-1;
    if(0<=tmp&&tmp<=2*rest)in[p]='4', four++;
    else in[p]='7', seven++;
  }
  p=0; while(in[p]=='0')p++;
  cout<<in.substr(p)<<endl;
}