Paizaでお手軽なオンラインハッカソンのイベントが始まりました。
今回は着せ替えソシャゲ風の企画で、アンドロイドの杏ちゃんに着せ替えができるようです。着せ替えアイテムはコードを書いて問題に正解するとアンロックされていくようです。
突如現れたれアンドロイドの彼女の杏ちゃん。やや貧ｘなのが気になります。
なんと着せ替えに水着！
なんとアンロックするアイテムに水着がありました！大興奮です。
そしてイベントに参加の紳士の皆さんにも正直なようで大人気です！
この水着問題、今回のアイテムの中、難易度が一番高いみたいです。個人的にはメガネがやや「？」でしたが…
水着列のゴールド枠(SR枠？)は他よりやや難しくできているようです。逆に上の3段の青枠(N枠？)は消化試合感が否めません。
オジサンも杏ちゃんに水着を与えてたい！
水着！水着！
ふぅ～！
しばらく仕事でコーディングしていないエクセルマスターな業務系のSEの自分も杏ちゃんに水着をプレゼントするべく頑張ってみようと思います。
・・・
・・・・・・
・・・・・・・・・
やりました！
格闘する事30分！とうとう手に入れました！！！
(2回ほどNGを食らいましたがなんとか合格です。）
解き方
しょっぱなからネタバレをすると面白くないので
- 仕様の確認
- 考え方
- コーディング
の順に自分がどうやったのか紹介したいと思います。
(解法が数学的に正しいとか、計算回数最小だとかそういう類ではなくあくあで問題を突破できるという視点でお願いします)
仕様の確認
何はともあれ、問題を知らないと回答できないのでまず、仕様を確認します。
SEの書いた仕様書読むのは苦痛なのにこういうのは楽しいですね！！！
何やら階乗の説明から始まりました。
どうやら階乗に関する問題の様です。計算結果の数値がすぐに巨大な数になる系の予感がします。
考え方
今回コードをJavaで書いていますが、JavaにはBigDecimal型という物凄い桁の大きい数字を取り扱えるクラスがあります。
が、残念ながら今回素直に計算すると最大値の「1000000の階乗」を計算すると、恐らく計算はできるのでしょうが時間が相当かかり6秒のタイムリミットを超過してしまうと思われます。
今回Javaでコードを記述していますが、c#のBigDecimal型が使えず、JavaのBigInteger使えばいいじゃん！的な発想でJavaを選択しています。が、結局long型までしかつかってないので言語選択から間違えている感じです。別にc#で書き直せばいいだけの話ですが…
階乗のおさらい
で、ちょっとしつこいですが、30の階乗までの計算結果を掲載します。
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
21! = 51090942171709440000
22! = 1124000727777607680000
23! = 25852016738884976640000
24! = 620448401733239439360000
25! = 15511210043330985984000000
26! = 403291461126605635584000000
27! = 10888869450418352160768000000
28! = 304888344611713860501504000000
29! = 8841761993739701954543616000000
30! = 265252859812191058636308480000000
計算が進むと急激に増加するので真面目に計算しようとしてはいけません。
よく見ると途中から下位の桁にゼロが増加している傾向が見えます。
最初の仕様で「最下位の桁のゼロは無視する」とあるので
『前の値と今回の数値をかけた後に下位の桁がゼロならゼロを削除する』
とできそうです。
「5!」のケースで「5 * 24」=「120」 となった場合、ゼロを削除して「12」と扱えそうです。
また、今回上記のゼロ削除した結果が「9桁以上ならそれより上位の桁は無視する」とあるので計算した結果9桁を超えた場合、上位の桁を削除します。
「15!」のケースで「15 * 871782912」=「13076743680」 となった場合、下位ゼロを削除して「1307674368」 上位桁を削除して「307674368」と扱えそうです。
これを入力値N回分の階乗計算の途中に組み込めば問題が解けそうです。
コーディング
解説は上記考え方とコメントの通りです。
ネタバレなんで自分でコード書きたい人はご注意を・・・
補足:
9桁最大値がintを超えてしまうのでuintかlongで計算しましょう。
あと、途中で11桁で計算していますが、longにする前にintでやっていて計算が合わなくなる現象を回避しようと試みた形跡なのであまり深く考えないでください。
import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { // 入力の読み取り BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); // 計算 & 表示 System.out.println(rmOver(fact(n), 9)); } // 階乗計算しながら不要な桁を削除していく private static long fact(int b) { long _ans = 1; for(int i = 1; i <= b; i++) { // 普通の階乗計算風の処理 _ans = _ans * i; // 下の0を消す _ans = rmUnderZero(_ans); // 11桁以上を消す _ans = rmOver(_ans, 11); } return _ans; } // 下の桁のゼロは削除 private static long rmUnderZero(long i) { while(true) { if(i % 10 == 0) { i = i / 10; } else { break; } } return i; } // 指定桁以上を削除 private static long rmOver(long i, int k) { String str = Long.toString(i); int len = str.length(); if(len < k) { return i; } return Long.parseLong(str.substring(len - k, len)); } }
これで安心して水着を着せられますね。ふぅ。
