AOJ 0268 - Kongo Type (Part 1)
今回はこの問題を取り上げます。
まずはショートコーディングではなく、普通に解いてみることにします。
この問題では割と珍しいことに、16進数で入力されます。まずはこの入力部ですが、scanfには%xというフォーマットがあるので、これを使えば一発で終わります。基数変換などは不要です。
さて、それぞれの入力に対し、符号部・整数部・小数部それぞれ出力する必要があります。このうち符号部の処理は入力の32ビット目*1を見ればいいだけなので、簡単です。では、整数部および小数部はどのようにすればよいでしょうか。
整数部は、問題文で与えられているようにを愚直に計算しても、もちろん求めることはできます。ただし、ループを回すことになるため、面倒くさいです。実はこの問題では、入力の8～31ビット目を取り出し、これらを7ビット右シフトするだけで、整数部を求めることができます。これなら実装も楽ですし、何より短く書けます。短く書けます*2。
一旦以上をまとめると、概ね以下のような流れになります。
#include <cstdio> using namespace std; int main(){ unsigned q, s; for(scanf("%u", &q); q--; ){ scanf("%x", &s); //16進入力 int x = (s & 0x7fffffffu) >> 7; //整数部 int y = ...; //小数部(後述) if(s >> 31) putchar('-'); //符号出力 printf(...); //整数部および小数部出力(後述) } }
さて、今度は小数部の計算です。とはいえ、小数というのはどうにも扱いづらいので、出来る限り整数のまま扱いたいものです。そこで、小数部にを掛けてみることにします。そうすると、1～7ビット目の重みは次のようになります。
| ビット | 本来の重み | |
|---|---|---|
| 1 | 0.0078125 | 78125 |
| 2 | 0.015625 | 156250 |
| 3 | 0.03125 | 312500 |
| 4 | 0.0625 | 625000 |
| 5 | 0.125 | 1250000 |
| 6 | 0.25 | 2500000 |
| 7 | 0.5 | 5000000 |
このように、を掛けることで重みは全て整数となり、何となく扱いやすそうな気がします。というわけで、小数部に
を掛けたものを求めてみることにしましょう。
なので、
と変形できます。整数部の処理と同様に考えれば、入力の下位7ビットを取り出し、それに
を掛ければ、小数部を整数として求めることができることが分かります。あとは、桁数が7に満たない場合には適当に0を頭に付け足すことで、とりあえず正確な値を出力することはできます。未完成ですが、とりあえず今の段階でのコードは次のようになります。
#include <cstdio> using namespace std; int main(){ unsigned q, s; for(scanf("%u", &q); q--; ){ scanf("%x", &s); //16進入力 int x = (s & 0x7fffffffu) >> 7; //整数部 int y = (s & 0x7fu) * 78125; //小数部 if(s >> 31) putchar('-'); //符号出力 printf("%d.%07d\n", x, y); //整数部、小数点、小数部を出力(未完成) } }
printfには便利な書式があり、%07dと書けば、整数を7桁以上(足りない桁は0で埋める)で出力してくれます。これを実行すれば分かりますが、とりあえず「正確な値」は出力されます。ただし、例えば入力00000f08に対する出力は30.0625000となり*3、「ある桁以下がすべて 0 の場合、その桁以下は省略するものとする」という条件を満たしていません。次はこれをなんとかする必要があります。
例えばその例の場合、小数部は整数625000として得られます。正しい出力と比較すれば、明らかに末尾の0を削れば良いことが分かります。ただし、そのまま10で割ってしまうと桁数が減ってしまうため、このままでは左側に要らない0が増えてしまいます*4。そこで、10で割ると同時に、全体の桁数も減らす必要があります。この桁数をdとして、とりあえず求めることにしましょう。そうすると、次のようなコードになります。
#include <cstdio> using namespace std; int main(){ unsigned q, s; for(scanf("%u", &q); q--; ){ scanf("%x", &s); //16進入力 int x = (s & 0x7fffffffu) >> 7; //整数部 int y = (s & 0x7fu) * 78125; //小数部 int d = 7; //最初は7桁とする while(d > 1 && y % 10 == 0){ y /= 10; //末尾に0があるなら(すなわち10で割り切れるなら)、10で割る --d; //桁数も1つ減らす。1桁になったらループを抜ける。 } if(s >> 31) putchar('-'); //符号出力 printf(...); //整数部、小数点、小数部を出力(未完成) } }
最後に、小数部の出力を考えます。これまたprintfには便利な書式があり、%0*dと書けば、任意の桁数で整数を出力(足りない桁は0で埋める)してくれます*5。そこでこれを使えば、最終的にコードは次のようになります。
#include <cstdio> using namespace std; int main(){ unsigned q, s; for(scanf("%u", &q); q--; ){ scanf("%x", &s); int x = (s & 0x7fffffffu) >> 7; int y = (s & 0x7fu) * 78125; int d = 7; while(d > 1 && y % 10 == 0){ y /= 10; --d; } if(s >> 31) putchar('-'); //符号出力 printf("%d.%0*d\n", x, d, y); //整数部x, 小数部y(桁数d) } }
以上で、普通に書いたコードの完成です。このままでも割と短いです。
次回はこれを短縮していきます*6。基本的な方針はほとんど同じです。
