400
Post/Edit Page
n個の点から任意の3点を選ぶ。選び方はnC3通りだ。点にそれぞれ1〜nのIDが振られているとして、選び方の組み合わせを(1,2,3)(1,2,4)……と昇順で並べたとき、x番目の組み合わせ(a,b,c)を定数時間で特定することはできるだろうか。つまり、どれほど長くてもいいがnに対してスケールしない計算方法で特定することは可能だろうか。▼仕事上の必要でこの問題に直面した。ループや条件分岐を使えば簡単に特定はできるが、定数時間という制限が曲者だ。手ごろなやり方で線形時間にできることはすぐにわかったが、なかなか定数時間には落とし込めない。結局、三次方程式の一般解を解く前提で、nが億の単位になればペイするであろう計算方法を発見することはできたが、「仕事上の必要」ではnはせいぜい数十程度のため、まったく割にあわないことがわかった。小さなnでも線形時間より早く答えを特定する方法があれば、教えて欲しい。
pass:
Draft