スポンサーサイト

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

Atcoder Beginner Contest #007 問題D 困った→なるほど

a,bの入力が求められて,aからbまでのすうじのうちで4,9を含まない数字の個数を求めるという問題

はじめに私が書いたコード
http://abc007.contest.atcoder.jp/submissions/162504
(ほんとはここにコード貼りたかったけどSyntaxHighLighterの設定してないからリンク)

これだと巨大な数値がよみこめないし,よみこめたとしてもとても時間がかかる.そこで数値を割ってみていく+数学の”カードを並べる問題”の考え方を足せばいいらしい

たとえば174382までで何個の数が4,9を含まないのか調べると。。。

1の位をみる→2なので2,1,0がいける.3個いけるの追加.3個ok
10の位をみる→8なので82,81,7a,6a・・・5a,3a,2a,1a,0a(a!=4,9)が可能.82,81の2個はすでにカウント済み.7から0の8個のうち4はダメだから除く.(8-1)*(10-2)=56個追加.59個ok
100の位をみる→3だから382,381・・300,288,・・3xyはすでにかぞえているので2xyと1xyと0xyだけだから(3-0)*(10-2)*(10-2)=192個追加.251個ok
1000の位をみる→4・・・なんだいままでのはだめだったのか(4xxは全部だめ)いけるやつを0個にリセット
3xyz-0xyzいけるから(4-0)*(10-2)*(10-2)*(10-2)=2048個追加
10000の位をみる→7だから(7-1)*(10-2)*(10-2)*(10-2)*(10-2)=24576個追加26624個ok
100000の位をみる→1だから(1-0)*(10-2)*(10-2)*(10-2)*(10-2)*(10-2)=32768個追加59392個ok

174382-59392=114990個おk

これがこのコード.cnt(x)は1からxまでのうち4,9含まない数字の数をかえすからcnt(b)-cnt(a)を出力すればいい.

long long cnt(long long x){
long long res = 0;
long long tmp = x;
long long b = 1;
while(x){
int t = x%10;
x /= 10;
if(t == 4 || t == 9) res = 0;
res += (t-(t>4))*b;
b *= 8;
}
return tmp-res;
}
スポンサーサイト
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

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