TOYPRO TTC002に参加したので解説と参加記をまた書くことにします。
今回はWriterの人が公式解説を用意してくれているので想定解はその解説をご覧ください。
1 - 円錐
半径$r$, 高さ$h$の円錐があります。円周率を3.14としたとき 体積は?(小数点以下切り捨て)
下の式を実装すればよいです。
V = \frac{πhr^2}{3}
円錐の体積は「底面積×高さ×$\frac{1}{3}$」
また、底面積は$r*r*π$であるので、上の式が導けます。
r = 3
h = 2
print(int(((r*r*3.14)*h)/3))
2 - 回転寿司
青、赤、金、それ以外の皿があってそれぞれ100円、200円、300円、不明である。 入力されたお皿の値段は？
入力されたお皿の色をif文を使って判定してあげると良いです。
color = "赤"
if color == "青":
print("100円")
elif color == "赤":
print("200円")
elif color == "金":
print("300円")
else:
print("不明")
不明に気づかずWAを出したなど...
3 - 値の範囲
整数aをbで割って切り捨てたとき答えがcになった。 bとcが与えられたとき、考えられるaの最小値と最大値は？
割り算の検算を考えると
$a÷b = c$ は $a = b \times c$に変形できます。
したがってaの最小値は$b \times c$となります。
一方最大値ですが、a割るbの答えがc+1になったときを考えるとわかりやすいです。
aの最小値が$b \times c$なのですから、a+1の最小値は$b \times (c+1)$です。
したがってaの最大値は$b \times (c + 1) - 1$です。
b = 3
c = 4
print(b*c, (b*(c+1))-1)
4 - ミーノ！
目の前に高さ$h$[m]の壁があり、壁までの距離は$d$[m]です。 ここで、$r$[m/s]の速度で走ることが可能で$c$[m/s]の速さで壁を登ることができるとき、壁を登り切るには何秒かかりますか?
それぞれにかかる時間を別々に考えてやると良いです。
壁に向かって走る時間を$A$としたとき
A = \frac{d}{r}
です。
また、壁を登る時間を$B$としたとき
B = \frac{h}{c}
です。
これを計算し、$A+B$の結果を切り下げると正解です。(切り上げじゃないんだ...)
h = 100
d = 100
r = 5
c = 3
a = d/r
b = h/c
print(int(a+b))
5 - 自転車のギア
ある自転車には前輪と後輪にギアがそれぞれついています。 前輪にはギアが$A$個取り付けられていて、ギアは配列で与えられます。 後輪のギア$B$個についても同様です。 ここで、前輪と後輪のギア比が $\frac{m}{n}$になる組み合わせはありますか？ 存在するとき"Yes"を。存在しないときは"No"を出力してください。
すべてのギアの組み合わせを試すと良いです。
すべてのギアの組み合わせはAとBをイミュータブルオブジェクトにした二重ループで実装できます。
また、ギア比が$\frac{m}{n}$になるというのは、$\frac{m}{n} = \frac{A_i}{B_i}$になる状況なのでif文を使って判定します。
m = 4
n = 6
A = [2, 3, 4, 5, 6]
B = [2, 4, 5, 7, 9]
for i in A:
for j in B:
if (m/n == i/j):
print("Yes")
exit()
print("No")
6 - CompositeNP
僕は愚直解法を通そうとして何度もTLEを量産しサーバーに多大なる負荷をかけたことをこの場を借りてお詫びします。
ある合成数Nが与えられる。 NはN以下の合成数の中で何番目か。また、N以下の素数はいくつあるか。 スペースを開けてそれぞれを答えよ。
$N$は合成数であるので、$N$以下には必ず素数があることがわかります。
したがって、$N$以下の素数を列挙して、$N$から発見した素数の数+1を引くとそれぞれの答えになります。
ここで、なぜ$N$から素数の数+1を引くと何番目の合成数かわかるかという話ですが、整数には素数と合成数と例外(要は1)しかありません。
$N$が合成数であるならばN以下の素数の数を引いてあげると$N$以下にいくつ合成数があるかわかります。
ただし、1は素数としてカウントしませんが合成数ではないのでこれを答えから引いて上げる必要があります。
$N$以下の素数を列挙する方法は色々あります。
一番簡単なのが2から$N$までループを回し、それぞれについて素数であるか否かを$O(\sqrt N)$で判定し、リストに突っ込むなりする方法が一般的です。
しかし、この問題の制約では$N$の最大値が$10^6$であることが示されています。
ここで、$N$以下の素数をすべて$O(\sqrt N)$で判定していると最大で計算量が$O(10^9)$程度になることがわかります。
(これを見落として何度もTLEを繰り返しました...わざわざTLEしてるか確認してくれてありがとうございました...)
ここで、エラトステネスの篩というアルゴリズムを考えます。
エラトステネスの篩はある整数$N$以下の素数を$O(N loglog N)$で列挙することができます。(ホントは実装上でもうちょっと定数倍がつく)
よって、素数を愚直にカウントしていくのではなくエラトステネスの篩をつかって事前に$N$以下の素数のリストを生成しておくことで、素数を得ることができました。
ここで、$N$以下の素数の数は配列の長さであることがわかります。
よって、最初の計算を行うことが可能になったのでこの問題を$O(NloglogN)$で解くことができました。
def Eratosthenes(np):
pri = [True] * (np + 1)
pri[0], pri[1] = False, False
for n in range(2, int(np ** 0.5) + 1):
if pri[n] == True:
for p in range(n * 2, np + 1, n):
pri[p] = False
return [p for p in range(np + 1) if pri[p]==True]
n = 12
l = len(Eratosthenes(n))
print(n-l-1, l)
感想
おもしろかった！
少し考える必要がある問題が多かったですが、どの問題も面白かったです。
制約なども(読んでなかったけど)今回はしっかり示してくれていたので良かったです。
ただ、最後の問題でエラトステネスの篩が要求されたのはちょっと想定外。という感じ。
余談ですが、実は友人を誘って始めさせてみようと思っていました。
結局誘わなかったんですが、誘わなくて正解だったかな...と思いました。
流石にこれが初めての競プロとコンテスト参加は比重が重すぎるかな...と。