Number Sequence(0)

http://acm.pku.cn/JudgeOnline/problem?id=1019
そんなわけで、http://d.hatena.ne.jp/fkm/20060507/p1より1019番にチャレンジしようと思ったのだけど、なんか難しい。ロベールさんがかなり昔にさらっと通してらっしゃるのだけど、どんなアルゴリズムなのか想像もつかない。とりあえずごにょごにょと頑張ってみて一応通ったが、ややインチキ臭い。というのもインプットによっては間違いの場合があるからだ。テストケースに助けられて通ったものの、これはちょっと頑張って考えないといけないような気がする・・・。
ちなみに問題はどんなものかというと、

11212312341234512345612345671234567812345678912345678910123...

というかんじで数字が無数に並んでいるとき、インプットnに対してn番目の整数を答える問題。一見単なる群数列に見えるのだが、答えるのは1〜9の一桁の整数。つまり、1,2,3,4,5,6,7,8,9,10,11,12,13という区切りではなく、1,2,3,4,5,6,7,8,9,1,0,1,1,1,2,1,3,というように、2桁以上になるところは一桁ずつ区切らなければならないので、例えばn=56の時の出力は10ではなく1、n=57の時は11ではなくて0でなければならない。しかもインプットの値が馬鹿デカイようで、単純すぎるとTLEになるし、unsigned intじゃないとサイズオーバーになっちゃう。unsignedなんて8バイトも使いたくないよー(T-T)

っちゅうわけで、私が考えたアルゴリズムを説明していくので「もっとカシコーな方法があるYO」という場合は誰か教えてくんさい。

つづく。