AtCoder Beginner Contest 178 「C - Ubiquity」をC#で解いたら
C問題を解くが目標になっているため、勉強しています。
その過程で作ったAtCoderのC問題のコード、コメント多めで載せてみます。
順位表の解答が早い順で見れば、コードの解答は分かりますが、何をやっているのかいまいちわからないときがあります。
そんな時、コメント沢山ついているコードがあればいいなと思うことがあるため、誰かのためになれば良いなと思います。
問題は、C - Ubiquityからご確認ください。
コード
ベン図を書いて整理すると、求め方はシンプルになります。(こんなの数学の問題では…?) DP (動的計画法)でも求められるようですが今回はシンプルな方で書きます。
今回は、Modした結果を出力するということで桁数の大きな値を扱うためいくつか注意が必要です。
答えを求めるのに単純にMath.Pow
を使うと、桁が大きくなりすぎてしまうため掛け算をするたびにModしないといけませんので、独自の関数を作りました。
また、Modを適宜することで、値によっては結果が負の数になったりするため、Modを足して調整したりします。
桁数の大きい値を扱うのは慣れが必要だなあと思います。
using System; using System.Linq; namespace Atcoder178 { class Program { const long Mod = 1000000007; static void Main(string[] args) { // n: 整数の長さ var n = long.Parse(Console.ReadLine()); // a. 0-9のn桁の整数の組み合わせ(全体): 10^n // b. 全体に条件「0を含まない」を追加: 9^n // c. 全体に条件「9を含まない」を追加: 9^n // d. 全体に条件「0、9を含まない」を追加: 8^n // 全体に「0を1つ以上、9を1以上含む」を追加: // a - b - c + d var ans = powMod(10, n); ans -= powMod(9, n) * 2 % Mod; // 大きくなるためModする ans += powMod(8, n); // Modしている関係でadが小さくbcが大きくなり、 // 答えが0以下になる場合があるため // Modを足して一旦正の値にする ans += Mod; // Modを足して大きくなっている場合があるためModする ans %= Mod; Console.WriteLine(ans); // これだとnの桁数が大きいとNaNになってしまう //var ans = Math.Pow(10, n) % Mod; //ans -= Math.Pow(9, n) % Mod * 2; //ans += Math.Pow(8, n); } private static long powMod(long x, long y) { var ans = 1L; for(var i = 0L; i < y; i++) { ans *= x; ans %= Mod; } return ans; } } }