AOJ 2556 : Integer in Integer

数え上げ

Integer in Integer | Aizu Online Judge

今年の書き初めです。

何故これを選んだかはとある宣言を見ると分かります。

問題概要

  • 数列[A,B]の中にCはいくつ含まれるでしょう。
  • 例えば [333,334] , C = 33 なら
    { 333,334 } 下線と太文字を数えて3つ。
  • A,B,Cが結構でかい 0<=A<=B<=10^10000, C=10^500

解法

  • Cの出てくる位置を決め打ちして数え上げる。
  • Cの位置をずらしていくだけなのでO(log10(B) * log10(C)) 
  • [A,B] の数 = [0,B] - [0,A-1] なので [0,X]を求める関数を作ると楽といういつものテク。
  • 例えば X = 99111, C = 619 のとき
    • 61911
    • 96191
    • 99619
  • のように下線部を決め打ちしたのに各いくつあるか考える。
  • そうすると入れ替わった部分とCを比較して
    Cの方が大きい…下線部の左の部分*10^右の桁数
    　　　　同じ…下線部の左の部分と右をくっつけた数+1
    　　　　小さい…下線部の左の部分+*10^右の桁数
  • C=0のとき少しかってが違うのでその場合のみ特殊処理。
  • 左の数が必ず1以上の時数えるようにする。
ソースコード

感想

ホントは1月1日にAcceptするつもりだった。

解法すぐ思いついたけど、実装→バグ量産→バグ取りが長すぎる実装力の訓練が必要。