101 Hack June Challenge コンテストに参加しましたが、解決できなかった問題が 2 つあります。これら2つの質問にアプローチする方法について、誰かヒントを教えてください。
Q1. 割り当て問題
Calvin は学校で数学の課題を抱えており、多くの式を評価する必要があります。Calvin は、あまり時間を無駄にしないことにしました。全体的に「M」表現があります。スージーの答えを見て、Calvin は、すべての質問に対する答えが非減少シーケンスを形成することを理解しました。
彼は、すべての答えが 1 から 'N' (両端を含む) の間になると判断しました。彼は、各要素が 1 から 'N' の間である長さ 'M' のランダムな非減少シーケンスを解答用紙に記入します。
ここからが、Calvin の本当の問題の始まりです。彼は N の大きな値を選択したくありません。選択できるオプションがたくさんあるからです。また、非常に小さい N の値を選択すると、多くの答えが等しくなり、教師は疑わしくなります。
x = max1 ≤ i ≤ N (頻度 (i)) の場合、頻度 (i) は、彼が選んだ 'M' 値のシーケンスで i が発生する回数です。Calvin は、x の期待値を知りたいと考えています。彼が問題を解決するのを手伝ってください。
たとえば、M = 3 & N = 3 の場合、可能なシーケンスは次のとおりです。
1 1 1 (x = 3)
1 1 2 (x = 2)
1 1 3 (x = 2)
1 2 2 (x = 2)
1 2 3 (x = 1)
1 3 3 (x = 2)
2 2 2 (x = 3)
2 2 3 (x = 2)
2 3 3 (x = 2)
3 3 3 (x = 3)
expected value of x = 2.2
入力フォーマット
最初の行には、テスト ケースの数を表す整数 T が含まれています。T 行が続き、それぞれに対応するテスト ケースの M と N の 2 つの数値が含まれます。
制約
T ≤ 15
1 ≤ M ≤ 250
1 ≤ N ≤ 10^9
出力フォーマット
T 行を出力します。各行には、対応するテスト ケースへの回答が含まれています。最大 10^-3 の誤差が許容されます。
サンプル入力
4
1 5
3 3
2 9
9 6
サンプル出力
1.0000000000
2.2000000000
1.2000000000
4.3146853147
Q2. GCDモクテル
反乱同盟軍と銀河帝国は、エンドアの上空で壮大な戦いを繰り広げています。壮大なセットアップには、長さ「N」の各次元 (つまり、N x N… (d 回)) を持つ d 次元のボードがあります。各セル (i1、i2、…id) には gcd (i1、i2、…id) が書き込まれています。
さあ、ゲームが始まります。ランダムな整数 L が選択され、30000001 を法として各数値の L 乗を最初に合計した人がゲームに勝ちます。
反乱同盟軍が助けを必要としており、あなたに連絡しています。彼らが勝てば、100万ドルを手に入れることができます。手伝ってくれますか？
入力フォーマット
いくつかのテストケースがあります。最初の行には、テスト ケースの数 T が含まれます。次に、T 個のテスト ケースが続きます。各テスト ケースは、次の形式で提供されます。N と d は最初の行で指定されます。Q は 2 行目に与えられます。次の各 Q 行には、整数 L が含まれます。
制約
0 <= T <= 10
1 <= N <= 107
1 <= d <= 1000
0 <= L <= 100
0 <= Q <= 50
出力フォーマット
テスト ケースごとに、答えを示す Q 行を出力します。
サンプル入力
3
3 2
4
0
1
2
3
5 1
3
0
1
2
6 3
2
2
3
サンプル出力
9
12
20
42
5
15
55
421
975
これは、Web サイトの問題へのリンクです。
Q1. https://www.hackerrank.com/contests/101june13/challenges/assignment
Q2. https://www.hackerrank.com/contests/101june13/challenges/gcd-mocktail
コンテストは終了したので、Stackoverflow に助けを求めてカンニングではないと思います。