competitive

以下の最適化問題が与えられたとする。 $$ \begin{array}{lll} \text{maximize} & f(x)\\ \text{subject to} & g_i(x) \leq 0 & \text{for } i = 1,...

SCIPに整数性のあるLPを解かせてみる。公式のPySCIPOptを使う。 from itertools import combinations from pyscipopt import Model, quicksum, SCIP_PARAMSETTING n...

問題 : $n$個のジョブを1つの機械で任意順に処理する。同時に取り組めるジョブは1つであり、1つのジョブに着手したら途中で他のジョブに切り替えることはできない。ジョブ$i$を始めてから完了するまでの時間は$p_i \ (> 0)$であり、ジョブ$i$を始める...

問題: 関数$f: \{0, 1, ..., N-1\} \rightarrow \{0, 1, ..., N-1\}$が与えられる。$f$によって定まるfunctional graph上の閉路の情報を$O(N)$で得たい。具体的には、次の配列を作りたい: $\...

問題 $F(M) =$長さ$N$の順列で、すべてのサイクルの長さが$M$の約数であるようなものの数 $f(m)=$長さ$N$の順列で、サイクルの長さのLCMが$m$であるようなものの数 とするとき、求める数は$N$の分割のLCMとして得られるようなすべての$...

問題 AC $h_i$が互いに異なる場合は$(2N-1)!! = (2N)! / 2^N N!$通りという有名事実がある（後述）。以下、$p_i = (2i-1)!!$とする。 身長$h$の人が$a_h$人いるとする。$i$人の同じ身長を持つ人から$j$ペ...

問題 $2(s_1+n_1+u_1+k_1+e_1)+\Delta s + \Delta n + \Delta u + \Delta k + \Delta e \le N$で各変数は非負という条件下で$\Delta s\Delta n\Delta u\Delt...