POH7 水着問題の解答例
Paizaの通常問題は外部で回答を公開することが禁止されていますが、POHはその限りではないそうです。
応募期間が終了したので、自分の提出したコードと考え方を貼ってみます。使用言語はC#。
※もちろんこれがベストな解法か全く自信はありません。
どなたかこれよりイカす解き方した人がいたら、是非コメント下さい。
特に、後ろのゼロを省くには10作らないように工夫するよりも、
愚直に計算するたびに10で割ったほうが良かった気がします。
問題文 - POH7水着(PaizaランクA相当)
問題の要点
「ある数Nを与えます。N!を求めて、その下位9桁を出力して下さい。ただし右側の0は除きます。」という一見掛け算するだけで終わりそうな簡単な問題。…に見せかけて、正攻法で計算すると変数がオーバーフローする。
POH7のBランク相当問題は2問とも「解けるけど面倒くさい」といった感じだったが、この問題はシンプルさの中にトラップが含まれている良問＆難問。
愚直に掛けていくとどうなるか
とりあえずこれを見て欲しい。
1!=1
2!=2
3!=6
4!=24
5!=120
6!=720
7!=5040
8!=40320
9!=362880
10!=3628800
11!=39916800
12!=479001600
------★ C# int型(32bit)が表すことのできる最大値 2147483647★---------------------------
------★ C# uint型(符号なし32bit)が表すことのできる最大値 4294967295★------------------
13!=6227020800
14!=87178291200
15!=1307674368000
16!=20922789888000
17!=355687428096000
18!=6402373705728000
19!=121645100408832000
20!=2432902008176640000
------★ C# long型(64bit)が表すことのできる最大値 9223372036854775807★-----------------
------★ C# long型(64bit)が表すことのできる最大値 18446744073709551615★----------------
21!=51090942171709440000
22!=1124000727777607680000
23!=25852016738884976640000
24!=620448401733239439360000
25!=15511210043330985984000000
26!=403291461126605635584000000
27!=10888869450418352160768000000
------★ C# decimal型(128bit)が表すことのできる最大値 79228162514264337593543950335★---
28!=304888344611713860501504000000
29!=8841761993739701954543616000000
30!=265252859812191058636308480000000
はい、たかだか28!を計算しただけでもうC#の変数が表すことのできる最大数を超えてしまう。
求める階乗Nが 1 ≦ N ≦ 1000000 となっていることを考えると、とても耐えられない。
考え方
問題文に出てくる
- 求める数字は9桁だけで良い
- 後ろのゼロを取っ払う
という条件は、解法のヒントにもなっている。この2つを駆使しながら階乗の計算をすることで、限られた桁数の中で変数のオーバーフローを防ぎながら計算を続けることができる。
求める数字は9桁だけで良い
左側を削って9桁以下にするというのがひとつ目のヒント。掛け算するたびに1000000000で割った余りを求め、その値を次の計算に使用することでオーバーフローを防ぐことができる。
もう少し般化して説明すると、「ある数の左側を削ってK桁にする」というのは、ある数を10^Kで割った余りを求めればOK。
例えば、12345という5桁の数字の左側を削って3桁にすると345となるが、これは10^3 = 1000で割った余り… 12345/1000 = 12あまり345 といった具合。
後ろのゼロを取っ払う
ふたつ目のヒントを使うと、右側を削って9桁を作った時に、後ろ9桁の右側からゼロが押し寄せてくる問題を回避する事ができる。これを達成するには後ろにつくゼロが何から成り立っているかを考えれば良い。
上記の階乗の計算結果リストで、末尾にゼロが増えるタイミングを良く観察してみよう。
一回目は5!のとき、二回目は10!のときだ。それぞれの階乗を丁寧に書きなおすと…
5! = 5 x 4 x 3 x 2 x 1
10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1
ふむ。5 x 2が一つ現れるたび、もしくは10が一つ現れるたびに後ろにゼロが増えるようだ。
三回目は15!のとき。 ここからが厄介な話になってくる。
15! = 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1
まってくれ、5 x 2も10も新たに出現していないじゃないか、と一瞬思うかもしれないが、
この式はすべてが掛け算なので因数分解することができる。12= 2 x 2 x 3、15 = 5 x 3なので、
12と15の因数になっている2と5が組み合わさって10を作っているというカラクリだ。
10の方も同じ理屈で、20や30は10を(もっと言えば2と5を)因数に持つので末尾にゼロが増える。
よって、2と5の組み合わせを因数として発見した場合、それらを計算から省いてあげれば末尾に0が付くことはなくなる。
コード
というような考え方をコードに落とすとこんな感じになったデス。
コードでは、2と5は最初の計算ではぶき、最後にまとめて計算してます。
かなり丁寧目に書いたのでifブロックが結構行取ってる…
static void Main(string[] args) { // Get N int N = int.Parse(Console.ReadLine().Trim()); long result = 1; // 結果出力用 int count2 = 0, count5 = 0; // 2と5の出現回数カウンタ readonly static int LIMIT = 1000000000; //後ろのゼロを削る用 // メインルーチン bool partial = false; for (int i = 1; i <= N; i++) { // 因数に2か5が含まれている場合、カウンタを更新し、partialフラグを立てる。 int div = 1; if (i % 2 == 0) { count2 += Count(i, 2); partial = true; } if (i % 5 == 0) { count5 += Count(i, 5); partial = true; } if(partial == true) 因数に2か5が含まれている場合、それらを除いた数にする。 { div = CalcDiv(i); } // 掛け算。partialフラグが立っていれば2と5を覗いた数を掛ける。それ以外ならiを直接掛ける。 result = partial ? result*div : result*i ; result = result % LIMIT; // 一回計算するたびに、ガッツリ0を削る。 partial = false; // 次のループのためにリセット } // メインルーチンでスキップした2と5の掛け算 // 2と5の組み合わせを作り、余った2を全て掛ける // 5は余らない(5が1回出現するまでに必ず2回以上2が出現するので、5が余ることは絶対にない) for (int i = 0; i < (count2 - count5); i++) { result *= 2; result = result % LIMIT; // 一回計算するたびに、ガッツリ0を削る。 } Console.WriteLine(result); // var debugInput = Console.ReadLine().Trim(); // for debug } private static int CalcDiv(int i) { while(i % 2 == 0) { i /= 2; } while(i % 5 == 0) { i /= 5; } return i; } private static int Count(int i, int target) { int counter = 0; while (i % target == 0) { counter++; i /= target; } return counter; }
一応、GitHubにもコード上げました。 github.com
あとがき
杏ちゃん可愛いよ杏ちゃん・・・
