SRM 546

0点、そろそろ黄色残留の危機ですね…と言うか以前できてた事もできなくなってる。
もっとちゃんと取り組まないとダメってことなんだろうなあ。

Level	ProblemName	Status	Point
Easy	KleofasTail	ChallengeSucceeded	0.0
Medium	FavouriteDigits	Opened	0.0
Hard	----	Unopened	0.0

Easy KleofasTail

問題

偶数ならば2で割る、奇数ならば1を引くという操作で、任意の数を0にするような手順を考える。
例えば7からスタートすると、7->6->3->2->1->0である。
A以上B以下の数で、0に仮定でKを経由するものの個数を答えよ。
A=6,B=8,K=3の時
6は6->3->1->0
7は7->6->3->1->0
8は8->4->2->1->0
といった手順を踏むので、3を経由するのは2つ、よって2を返す、みたいな話。

考えたこと

Kが偶数だったとする。
すると、その前の数字はK+1である可能性がある。
Kの前は2K
K+1の前は2K+2がありえて、更にその前まで遡ると、2K+1,2K+3があり得る。
何が言いたいのかというと
Kが偶数の時
[K, K+1]], [2K,2K+3] [4K,4K+7]...
の値がKを経由するという事。
後はこれらの範囲とA,Bの重なりを場合分けゴリゴリして求めれば良い。
Kが奇数の場合はKがA以上B以下であるのを判定しつつ、残りは2Kを経由する数を求めれば良い。
……場合分け抜け発生してた、おｈ……
案の定チャレンジされてしょんぼり。

反省会

そもそもA以上B以下の個数とか、0以上B以下の個数-0以上A-1以下の個数が定石だろが
なぜ愚直にA以上B以下の判定とか考えたのか。馬鹿なのか。馬鹿なんだな。
あと、Kが1以下ならB-A+1を返す、なんてやっていたのも間違いだった。
Aが0の場合を全く考えていない。多分このケースでチャレンジされたんだろう。
同じようなひといないかなーと慌てて探したけれど、そんな馬鹿は私だけでした／(^o^)＼

コード (Practiceにて通過確認）

  long long countGoodSequences(long long K, long long A, long long B) {
    long long result=0;
    if( K < 1 ) return B-A+1;
    if( K % 2 != 0 ){
      if( A <= K && K <= B ) result++;
      K*= 2;
    }
    long long offset = 2;
    while( true ){
      //cout << K << endl;
      if( K > B ) break;
      if( A <= K && K+offset-1 <= B ) result += offset;
      else if( K+offset-1 < A ){
        //donothing
      }
      else if( K < A ){
        if( K+offset-1 <= B ) result += K+offset-A;
        else{
          result += B-A+1;
        }
      }
      //added after the coding phase
      else{
        result += B-K+1;
      }
      K *= 2;
      offset *= 2;
    }

    return result;
  }

Medium　FavouriteDigits

問題

N以上の値で、digit1(0以上9以下)がcount1回以上、digit2(0以上9以下)がcount2回以上現れる値を返せ

考えたこと

桁上りと0が一番左に来るケースをどう処理したらいいのか。
digit1がK回、digit2がN回現れるi桁の値で、i桁目までがNよりも大きいもの/小さいものの最小値を
dp[K ][N ][i ][0 or 1(Nより大きいor not) ]とかいうdpにしようと思ったけど、あっという間に頭がこんがらがった。