AtCoder と試験で確かめる

8 問の総合問題

問題文を読んだら、すぐにコードを開かず、どの分野の道具を使うかを先に言ってみてください。

問 1 足し算の足し算 (分野 1)

次のコードは、n = 100 のとき total がいくつになりますか。

total = 0
for i in range(1, n + 1):
    for j in range(1, i + 1):
        total += j

内側のループは 1 から i までの和 i × (i + 1) ÷ 2 を足しています。それを i = 1 から n まで足すので、Σ で書くと Σ i(i + 1)/2 です。計算すると n(n + 1)(n + 2)/6 になり、n = 100 なら 100 × 101 × 102 ÷ 6 = 171700 です。

問 2 3 で割り続ける回数 (分野 2)

10^18 を、3 で割って切り捨てる操作を繰り返します。何回で 0 になりますか。

3 で割って切り捨てるのは、3 進数で右に 1 桁ずらすことです。だから回数は、3 進数で書いたときの桁数です。3^37 ≤ 10^18 < 3^38 なので、38 回です。log3 (10^18) = 18 ÷ log10 3 ≈ 37.7 の切り捨てに 1 を足した数とも言えます。

問1 171700 171700
問2 38
 3^37 450283905890997363
 3^38 1350851717672992089

問 1 は数えた和と式の値がどちらも 171700、問 2 は 38 回で、3^37 と 3^38 の間に 10^18 があることも確かめられました。

問 3 2 つの周期と曜日が重なる日 (分野 3、8)

今日は月曜日で、6 日ごとの掃除と 8 日ごとの点検を両方しました。次に、掃除と点検が同じ日にあって、しかもその日が月曜日になるのは何日後ですか。

掃除と点検が重なるのは、6 と 8 の最小公倍数の日ごとです。最小公倍数は 6 × 8 ÷ 最大公約数 2 = 24 なので、24 日ごとです。曜日の周期 7 と合わせると、24 と 7 の最小公倍数で、24 と 7 の最大公約数は 1 なので 168 日後です (3-1 の最大公約数と、8-1 の周期)。

問 4 2 個のサイコロの大きい方の目 (分野 4)

サイコロを 2 個振り、大きい方の目 (同じなら、その目) を得点にします。得点の期待値はいくつですか。

得点が k 以下になるのは、2 個とも k 以下のときで、確率は (k/6)²です。だから得点がちょうど k の確率は (k/6)² − ((k − 1)/6)² です。36 通りを全部数えても出せます。

問3 重なる 24
 月曜とも 168
 1 日ずつ探す 168
問4 161/36 4.472222222222222
式から 161/36

問 3 は 24 日ごとに重なり、月曜とも重なるのは 168 日後で、1 日ずつ探した答えとも合います。問 4 は 161/36 (約 4.47) です。1 個のときの 3.5 より大きくなります。

問 5 応答時間のばらつき (分野 5)

ある API の応答時間を 5 回測ると、120、80、100、140、60 ミリ秒でした。平均と標準偏差はいくつですか。

平均は 500 ÷ 5 = 100 です。平均からの差の 2 乗は 400、400、0、1600、1600 で、合計 4000 です。5 で割ると分散 800、その平方根で標準偏差は約 28.3 です。手元のデータを母集団とみなさず、標本から母集団の分散を見積もるときは、5 − 1 = 4 で割って分散 1000、標準偏差は約 31.6 です。統計検定では、どちらで割るかを問題文から読み分けます。

問 6 長さを 1 にそろえてから内積 (分野 6)

ベクトル a = (3, 0, 4) と b = (0, 5, 12) を、それぞれ長さ 1 にそろえて (各成分を長さで割って) から内積を取ると、いくつになりますか。

a の長さは √(9 + 0 + 16) = 5、b の長さは √(0 + 25 + 144) = 13 です。そろえたベクトルは (3/5, 0, 4/5) と (0, 5/13, 12/13) で、内積は 4/5 × 12/13 = 48/65 (約 0.738) です。長さ 1 にそろえてから内積を取ると、コサイン類似度と同じ値になります。埋め込みの検索で、先に長さをそろえて保存しておくのは、このためです。

問5 平均 100
 5 で割る 28.28
 4 で割る 31.62
問6 5.0 13.0 48/65 0.738

pstdev は個数 n で割る標準偏差、stdev は n − 1 で割る標準偏差です。問 6 は長さが 5 と 13 で、そろえたあとの内積は 48/65 (約 0.738) です。

問 7 勾配降下法の 3 歩 (分野 7)

f(x) = x² − 4x を小さくしたいとします。x = 0 から、学習率 0.25 の勾配降下法で 3 歩動かすと、x はいくつになりますか。

傾き (微分) は f'(x) = 2x − 4 です。1 歩は x ← x − 0.25 × (2x − 4) なので、x = 0 → 1 → 1.5 → 1.75 です。一番小さくなる x = 2 に、半分ずつ近づいていきます。

問 8 2 でも 3 でも 7 でも割り切れない数 (分野 8)

1 から 10^18 までの整数のうち、2 でも 3 でも 7 でも割り切れない数はいくつですか。

10^18 個を全部調べるループは終わらないので、式で数えます。2 か 3 か 7 で割り切れる数を、3 つの集合の包除原理で数え (8-4)、全体から引きます (8-3 の余事象)。3 つの重なり (42 の倍数) は足す側に入ります。答えは 285714285714285714 個で、全体の 1/2 × 2/3 × 6/7 = 2/7 にほぼ当たります。式が正しいかは、N = 1000 のような小さい N で全部数えた答えと照らします。

問7 1 歩 1.0
問7 2 歩 1.5
問7 3 歩 1.75
問8 285714285714285714
N=1000 286
全部数えた 286

問 7 は 1.75 です。問 8 は 285714285714285714 個で、N = 1000 では、式の 286 と全部数えた 286 が一致しました。