これは何
この記事は、TTC003の各問題の考え方と回答、想定されるAC解の実行ステップ数をまとめたものです。
いくつかの回答例が示されていますが、この他にも様々な回答が考えられます。
A - 桜並木(200)
想定されるAC解の実行ステップ数:$\Theta(1),\Theta(\frac{N}{k})$1など
いわゆる植木算で解く問題です。 $N$ が $k$ で割り切れるため、端の部分の例外を考えなくて良いです。
整数での割り算はint(N/k)やN//kが考えられますが、精度を考えると//を使う方が望ましいでしょう。
道路の両側に木があるため、2をかけることを忘れないようにしましょう。
整数を文字列として扱う場合はstr()関数やf-stringなどを利用できます。
実装例1:strを使ったもの
N=1
k=1
print(str(2 * (N // k + 1)) + '本')
また、植木算で足す端の2本を別で足すという方法もあります。
実装例2:f-stringを使ったもの
N=1
k=1
print(f'{2*N//k+2}本')
B - dを言ったらだめ！(300)
想定されるAC解の実行ステップ数: $\Theta(1),\Theta(\frac{d}{k})$など
正式な名前は知らないけどみんな遊び方を知ってる遊びの代表格(要出典)に関する問題です。
最終的に$d-1$を言えばいいので、$d-1$から$k+1$ずつ減らしていくと、言うべき数が全て求まります。
例えば一般的な$d=30,k=3$のルールですと、$29$から$4$ずつ減らしていくことになるので、
必勝側が言うべき数は$29,25,21,17,13,9,5,1$の順で求まります。
この中で最小の$1$を先攻が言えるので先攻が必勝です。
先攻は初手で$k$までしか言えないため、言うべき最小の数が$k+1$になるときだけ後攻が必勝です。
ここまでのことから、$d-1$から$k+1$ずつ減らしていって$k+1$以下になった時、$k+1$かどうかで場合分けを行うことで解けます。
実装例1:while文を利用した求め方
k = 3
d = 6
i=d-1
while i>k+1:
i-=k+1
if i==k+1:
print('後攻')
else:
print('先攻')
また、 $k+1$ から更に $k+1$ を引くと$0$になることから、 $d-1$ が $k+1$ で割り切れるかどうかで場合分けを行っても良いです。
300点問題なので、どちらで解いても間に合うような制約にしました。
実装例2:d-1がk+1で割り切れるかで場合分けする例
k = 3
d = 6
if (d-1)%(k+1)==0:
print('後攻')
else:
print('先攻')
他にも、$d$を$k+1$で割ったあまりが$1$かどうかで判定すると短く書けます。
また、k+1を-~kと書くことで括弧がいらなくなり短くかけます。
また、k=d=5などと書くと$k$に$d$が代入されWA2となるので注意してください。
実装例3:短縮した例
k=3
d=6
print('先後'[d%-~k==1]+'攻')
C - 多項式の値(400)
想定されるAC解の実行ステップ数: $\Theta(N),\Theta(N\log N)$など
ここから、(程度は難易度によりますが)計算を効率化していかないといけない問題になります。
**を用いて累乗してからあまりを取るとTLE3してしまいますが、
pow()関数は第3引数を指定することであまりの計算をしてくれます。累乗しながらあまりを取るため高速です。
N-i-1の部分で詰まるかもしれませんが、入力例などを見れば大丈夫だと思います。
実装例1:pow関数を用いたもの
N=3
A=[1,2,3]
x=2
ans=0
for i in range(N):
ans+=A[i]*pow(x,N-i-1,10**9+7)
print(ans%(10**9+7))
また、ホーナー法という、$x$で順にくくりだすことによるより高速なアルゴリズムもあります。
入力例でいうと、$x^2+2x+3=(((0)x+1)x+2)x+3$とすることで、$0$に$x$をかけて係数を足すという操作だけで求まります。
実装例2:ホーナー法を用いたもの
A=[]
x=0
N=0
a=0
for i in A:a=a*x+i
print(a%(10**9+7))
400点問題なので、どちらの方式でも解けるようにしました。
D - 再帰っぽい関数(500)
想定されるAC解の実行ステップ数: $\Theta(n)$など
定義のとおりに再帰的に実装してしまうと計算量が多すぎてTLEとなります。
この関数が組み合わせCを用いて$_n C_r$と表せると気づけるかにかかっています。
気づけたら$_n C_r$の定義から$\dfrac{n!}{r!(n-r)!}$をそのまま計算するだけです。
階乗はmath.factorial()を使います。｢メモ化｣という、$0$からある数$a$までの階乗を事前に記録しておく方法がありますが、
その方法を使わなくても間に合う制約になっています。
実装例1:定義どおりに実装した
n=0
r=0
from math import factorial as f
print((f(n)//f(r)//f(n-r))%(10**9+7))
9/7(火)にTOYPROでのPythonのバージョンが3.9にアップデートされたため、math.comb()が使えるようになりました。
$math.comb(n,r)={_n C_r}$なので代入すればACできます。$10^9+7$で割ったあまりを答えることに注意してください。
実装例2:math.comb()を用いたもの
n=0
r=0
import math
print(math.comb(n,r)%(10**9+7))
E - 割り算の筆算(600)
想定されるAC解の実行ステップ数: $\Theta(\sqrt{m}),\Theta(m)$など
愚直に筆算のあまりの部分をリストに記録し、(余り) in (リスト)とするとTLEしてしまいます。
また、setのほうが速いですが、それでも探索に時間がかかるためTLEします。
$\Theta(m \log m)$では間に合わない、少々きつめの制約となっています。
詳しい証明は省きますが、分母と分子で約分した後分母から2,5の素因数を無くした時1なら有限小数、それ以外は無限小数になります。
この時分数はすでに約分されているので、分子の値によらずループの桁数は同じです。なので、分子を1として計算することで、
割ったあまり=1とすることで高速に判定できます。
2,5の素因数がないことで、循環節が必ず小数第1位から始まるため、循環したかの判定を$O(1)$で行うことができます。
実装例1:解説通りの実装
n=1
m=49
from math import gcd
m//=gcd(n,m)# 分母を約分、分子は1としていいので処理しない
while m%2<1:m//=2#2で割れるだけ割る
while m%5<1:m//=5#5で割れるだけ割る
if m==1:print(0)#2,5以外の素因数を持たないなら
else:
n=1#分子を1として考える
i=0#ループ数=循環の桁数をカウント
while 1:#最低1回は実行するのでここに条件を入れてはならない
n=10*n%m#割り算の筆算を再現。0をおろしてmの倍数を引いたあまり
i+=1#カウントを1増やす
if n==1:#ループしたなら
print(i)#ループまでに要した桁数を出力
exit()#ループから脱出するためにexit()関数を使った。breakも可
追記(9/14):実装例1でTLEする件
実装例1でTLEするという報告をいただきました。調査したところ、TOYPROの実行速度が時間帯や負荷などによって変動することが原因でした。
この問題は以下のように$\Theta(\sqrt{m})$で解くこともできますが、この場合700～800点が妥当となるでしょう。
以下、こちらの問題を参考とした解説になります。
約分した後2,5で割れるだけ割るというところまでは実装例1と同じですが、オイラーの定理というものがあり、
これによるとオイラーのφ関数を用いて、$10^{\phi(m)}\equiv1(\mod m)$となることから、$\phi(m)$の全ての約数$K$について
$10^{K}\equiv1 (\mod m)$かどうか判定し、そのうち最小の$K$を出力すればよいです。
$\phi(m)$はエラトステネスの篩と似た手法で、1～mの数のリストを作り、mを割り切るものの倍数を消していけば良いです。
約数の全列挙については、一旦素因数分解した後、素数ごとに何乗するかを決定すれば十分高速です。
以上を踏まえて、次のような実装例となります。
実装例2 高速化した例
n = 3
m = 8
def euler_phy(n):#オイラーのφ関数
a=[1]*(n-1)#1～n-1までの数のリストを用意(2以上のnにおいてnは自身と互いに素でないので入れない)
i=1#最初のインデックスを1とすることで1の倍数=全自然数を消すことを防げる
while (i+1)**2<=n:#√nまで繰り返せば大丈夫です
if n%(i+1)==0:#インデックスiが表す数i+1で割り切れるなら
for j in range(i,n-1,i+1):a[j]=0#その倍数を消去(delより高速です)
i=a.index(1,i+1)#次に判定する数を求める
return sum(a)#1であるものの個数なので、a.count(1)でも可
def prime_factor(k):#素因数分解
i=2#割る数
a=[]#素因数のリスト
while i*i<=k:#√kまで繰り返します
if k%i:i+=1+i%2#k%iが非ゼロ=iで割り切れないなら次の割る数を求める
else:#割り切れるなら
a+=[i]#素因数にiを追加
k//=i#kをiで割る
if k>1:return a+[k]#kがiより大きい素因数を持っていた場合k>1です
else:return a#kが1なら素因数としてkを追加する必要はありません
def search(List,num=1):#約数について全探索(Listが素因数リスト、numは再帰で使う)
if len(List):#リストの長さが正ならば
a=List.count(List[0])#素因数List[0]の個数
return sum([search(List[a:],num*List[0]**i)for i in range(a+1)],[])
#List[a:]でList[0]以外の全素因数が求まる
#sum()の第2変数は初期値なので、これによりリストを結合
#ifの内部でreturnされない=ifの条件を満たさない時ここに来るので｢else:｣は不要
if pow(10,num,m)==1:return[num]#numで条件を満たす時、numは(最小とは限らない)答えなのでそれをreturn
return[]#上のifが成立していないので、numは条件を満たしていない->numはreturnしない
from math import gcd
m//=gcd(n,m)
while m%2<1:m//=2
while m%5<1:m//=5
if m==1:print(0)#ここの5行は実装例1と同じ
else:
print(min(search(prime_factor(euler_phy(m)))))#Kのうち最小のものを出力
F - あみだくじの繰り返し(700)
想定されるAC解の実行ステップ数: $\Theta(N\log N),\Theta(N^2)$など
出力すべき数は最大で$10^{35}$を超えるため、全探索していたら間に合いません。
どんなあみだくじも有限回繰り返せば一切入れ替わらないあみだくじと同じものになるという問題です。
難しく書こうと思えば大学数学まで必要ですが、TOYPROは小学5年生から始めるサイトなので大まかに書きます。
まずはあみだくじ1個分でどのように入れ替わるのかを調べます。
すると、以下のように周期的に値を入れ替える部分が存在します。
例えば、(左から)1番目が2番目に、2番目が3番目に、3番目が1番目に、4番目が5番目に、5番目が4番目に入れ替わるようなあみだくじがあったとしましょう。これは、1,2,3番目と4,5番目がそれぞれ順番に入れ替わっていると捉えることが出来ます。
すると、1,2,3番目の部分は3回の周期で元通りになり、4,5番目の部分は2回の周期で元通りになることが想像できます(実際そうなります)。
3の倍数でも2の倍数でもある｢最小の｣数なので、これらの周期の最小公倍数を答えればいいとわかります。
ループがある要素を全て高速に見つけ出す事ができれば、Eまで解けている方なら問題ないかなと思います。
ある一つの要素をあみだくじを繰り返し通過させてループを検知し、そのループ中に通った全ての箇所を探索箇所から削除すると間に合います。
実装例1:解説通りの実装
N=10#あみだくじの縦線の本数
A=[0,1,2,3,4,5,6,7,8]#入れ替える場所の位置と順番
B=[*range(N)]#各縦線の番号を記録(初期値)
for i in A:
B[i],B[i+1]=B[i+1],B[i]#実際に入れ替えて入れ替わり方を調べる
b={*range(N)}#探索すべき開始地点
ans=1#全く入れ替わらないなら1回でOKなので、初期値は1
from math import lcm#最小公倍数を使えるように
from random import sample#次に調べるべき数をランダムに決定するために
while b!=set():#調べるべき要素がまだある間
d=sample(b,1)[0]#sampleの出力はlistなので[0]で最初の要素を取り出す
e=d#あみだくじ通過前の数を記録
f=0#ループの数
while 1:#ループしたらbreakでループを抜けるのでここに条件を書かない
b-={d}#すでに探索済みの地点の削除
d=B[d]#次の位置を求める
f+=1#ループの数
if e==d:#あみだくじ通過前と一致したら(ループしたら)
ans=lcm(ans,f)#ansとfの最小公倍数を求める
break#次のノードへ
print(ans)
他にも、Union Findというアルゴリズムでグループ分けをすることもできます。
下の実装例は後処理に改善の余地ありですが、あくまでも例なので悪しからず。
実装例2 Union Findを用いたもの
N=10
A=[0,1,2,3,4,5,6,7,8]
B=[*range(N)]
for i in A:
B[i],B[i+1]=B[i+1],B[i]#この行までは実装例1と同じ
d=list(range(N))
e=[0]*N
def find(n):
global d
if n!=d[n]:
d[n]=find(d[n])
return d[n]
def join(a,b):
a,b=find(a),find(b)
global d,e
if e[a]<e[b]:
d[a]=d[b]
else:
d[b]=d[a]
e[a]+=(e[a]==e[b])
for i,j in enumerate(B):
join(i,j)#ループの入力と出力同士をつなぎます
ans=1
from math import lcm
for i in set(d):#グループの数だけ
f=d.count(i)#各グループの要素数との最大公約数を取る
ans=lcm(ans,f)
print(ans)
G - リスト圧縮!(1000)
想定されるAC解の実行ステップ数: $\Theta(\log(int(S)))$
リスト全列挙では最大の入力($S>10^{480}$)に間に合いません。
自然数と有限自然数列は見た感じ有限自然数列の方が圧倒的に多そうですが、実は同じ数だけあるという問題です。
実はこの問題では自然数とリストが実は1対1に結び付けられています。
アルゴリズムの流れは、
S→int(S)→(リストの長さと同じ長さの中でのRank)→目的のリスト
と求めるのが自然でしょう。
最後の変形はこの問題と同じように解けば良いです。
1000点問題はトイプロの順位に大きく影響するため、ここでは実装例をあえて載せません。
つよい人に解いてもらうのを楽しみにしています。
おわりに
今回の問題は、｢数学の新たな学び｣を意識して、教科書通りだけではちょっと難しい問題を作ったつもりです。
解いていて新たな発見があったり、解説を見て｢そうだったのか!｣といった学びがあったら良いな―と思います。
これらの問題の方針を2秒で理解できるレベルのつよつよさんには物足りなかったかもしれませんが、
すでにある程度学んでいないと解けないはずですので、すでに学びを得ているという意味では問題ないと思います。