competitive
2024年2月23日金曜日
SCIPにLPの基底解を出させるのは難しい
›
SCIPに整数性のあるLPを解かせてみる。公式のPySCIPOptを使う。 from itertools import combinations from pyscipopt import Model, quicksum, SCIP_PARAMSETTING n...
2024年1月27日土曜日
リリース時刻付きジョブスケジューリングの定式化
›
問題 : $n$個のジョブを1つの機械で任意順に処理する。同時に取り組めるジョブは1つであり、1つのジョブに着手したら途中で他のジョブに切り替えることはできない。ジョブ$i$を始めてから完了するまでの時間は$p_i \ (> 0)$であり、ジョブ$i$を始める...
2024年1月18日木曜日
functional graphの閉路の情報を得る
›
問題: 関数$f: \{0, 1, ..., N-1\} \rightarrow \{0, 1, ..., N-1\}$が与えられる。$f$によって定まるfunctional graph上の閉路の情報を$O(N)$で得たい。具体的には、次の配列を作りたい: $\...
2021年11月16日火曜日
ABC 226 F - Score of Permutations
›
問題 $F(M) =$長さ$N$の順列で、すべてのサイクルの長さが$M$の約数であるようなものの数 $f(m)=$長さ$N$の順列で、サイクルの長さのLCMが$m$であるようなものの数 とするとき、求める数は$N$の分割のLCMとして得られるようなすべての$...
2021年11月9日火曜日
ACL Beginner Contest F - Heights and Pairs
›
問題 AC $h_i$が互いに異なる場合は$(2N-1)!! = (2N)! / 2^N N!$通りという有名事実がある(後述)。以下、$p_i = (2i-1)!!$とする。 身長$h$の人が$a_h$人いるとする。$i$人の同じ身長を持つ人から$j$ペ...
2021年11月7日日曜日
エイシング プログラミングコンテスト 2020 F - Two Snuke
›
問題 $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...
2021年10月30日土曜日
HackerEarth - Connected Permutations
›
問題 AC 求める数を$a_n$とする。長さ$n$の順列を先頭$k$要素が$1, 2, ..., k$の順列であるような最小の$k$で分類して数えると、それぞれ$a_k(n-k)!$通りある。長さ$n$の順列から長さ$n+1$の順列を作ることを考えると、$n...
›
ホーム
ウェブ バージョンを表示