これ電波の出力に勾配法使えるんじゃね 使う頂点集合 $Z$ を焼きなまし $Z$ をターミナルとした最小(最小ではない)シュタイナー木 $T$ を構成 $T$ に含まれる頂点の出力を決める$C(v) := T$ の中で $v$ が最も近い頂点となる家の数 $(v \in T)$ $C(v)$ が大きい方から $2|T| / 5$ 個までの頂点の集合を $V$ とする 各家を $V$ の中で最も近い頂点に割り当てる $P = 0$ の頂点を省いてシュタイナー木を求め直す

0 から順にバブルソートをやると、それぞれ最大30stepsで、合計13950 大体E=0になるかな 登るときに数字が高い方を選ぶ←下から埋めていったほうが良いですランダムにすると乱択ができる 距離を最小にするようなルート11229500(500位)マジ？終わりだ… 残り2時間しかないってマジ？ 同じ段は順番を入れ替えて良いからこれが乱択要素？ これ同じ段の隣接swapで焼けるんじゃね？

最もコスパが良い経路を探す 評価関数書くか〜 nターン後の収益を評価する 今の蟻/ビーコンとの距離を評価しないとめっちゃ動く(それはそう) 一番効率の良いMST決める MSTを均すマッチング 蟻コントロール terminal が少ない方からやれば時間で打ち切れる 自分のベースから敵のベースまでパス伸ばせばベース潰せる笑

最終パラ: 618742362.47 破壊と再生はできるのに焼けないらしいです(ミクさんたすけて～～) 36, 144 87, 235 84, 1687: assign_number 高速化 124, 2220: iikanji sort 高速化 69, 195: RandomSet

S が既知だとして最適解を見る seed=0000 最適解 Cost = 65814 真ん中通ればいいらしいけど，わからん... 700以下くらいでぜんぶ繋げそう？ ちょっと遠くを見ると勾配がわかる n 個置きに50くらいで掘って惚れた場所を繋げる？(10, 20, 40, 80)で詳しく調べる 各家を焼きなましで水に割り当てて最小シュタイナー木

どう考えてもまともな貪欲が必要だけど，グラフを分割するのがめんどくさすぎる 絶対スコアが低いほうが良い相対スコアが出て？？？になってたらそういうコンテストだった カス 最終解 u→vへの最短パスを取り除く * 最短パスと同じ辺数の迂回路？閉路ができるとだめ 次数分辺を生やすとだめ 隣の道を同じ日に取るとスコアが下がりやすい 最初に道を作ってから割り振る←やってない縦の道と横の道 外周から剥いでいく

基本的には勾配降下法 複数の矢印が同じ点を指してることが分かれば、直線が交差するところを調べる あるいはにぶたん 時間を使う方法が思い浮かばないねえ 交点の平均が点に収束したりする？ PSOみたいな感じか？

bit を作る部分2 次数を埋め込む ネットワークで正則グラフじゃないグラフ出てきた気がするが忘れた クリーク埋め込んで反転後に次数列がどうなるか観察する クリークでダメなら正則グラフ頑張って書く 頂点swapは出力を並び替えるだけでグラフの形は変わらないらしい 正則グラフじゃなくても次数が埋め込めればいいね エラー後に分布が離れてる次数列を埋め込む

1手目だけUCB1のモンテカルロ法で自ターンをシミュレートするのが良さそう(ドローの部分がランダムなので) 自ターンだけのISMCTSでもいいけど とりあえず評価関数を作る必要がある 結果が確定的なアクションのノードまで展開するするMCTSがしたかったが、弱すぎた(プレイアウトのアクションはif文AIで決定的に行ってdrawはランダム) 結局やったのはif文によるルールベースでした！！！ 探索

$N!$ で正解を列挙し，それぞれの正解について通常の8パズルのソルバーを走らせる 8(11) puzzle は A* でできる $(N^2 - 1)!$ だった Ω＼ζ°)ﾁｰﾝ IDDFS ピースは16種類しかない それぞれの枚数を管理してdfsかDPで列挙(N=6ならDPで列挙できそう)

グラフには結構依存関係があるはずで、順番よりタスクを誰に割り振るかの方が大事 正規化されてるので能力が異常な人間は存在しない →嘘で、最大3倍違う 大体1000日目までにタスクを終わらせる タスクを割り当てれば時間が決まってほぼPERTに落ちる(ほんま？)→順番も決める必要がある 真値を使って101177 上位やばすぎ Valさんつえー ビーム打ってそう

原案: bin、改変: Hec、解説: qLethon(@pu__Ne) 何回操作を行っても全体のORをとった値は変わりません。したがって，「ORをとった値が全体のORになる集合」の要素の個数の最小値を$N$から引いた値が答えの上界になります。要素の個数が最小の集合$S$に含まれる数以外を$0$にすることはできるので、$N - |S|$が答えになります。 $|S|$の求め方 数列$B$を$B_i = |{j \mid A_j = i\ (1 \le j \le N)}|$と定めます。 このとき、 $$C_1 = B \ C_{i, j} = \sum_{j = k | l} C_{i - 1,\ k}C_{1,\ l}$$ とすると、$C_{i, X} > 0$となる最小の$i$が$|S|$になります。($X$は全体のOR)

原案: hec, 解説: qLethon(@pu__Ne) $\mod p$ での原子根のうち1つを $g$ とする．$g$ は原始根の定義から周期 $p - 1$ である． $m \mid p - 1$ ($m$は$p - 1$の約数)，$\phi := g^{\frac{p - 1}{m}}$とすると，$\phi^k \pmod{p}$ は周期 $m$ となる． このとき，$m \gt 2n$ が素数ならば，$A_i = (\phi^{i \times 0}\ %\ p, \phi^{i \times 1}\ %\ p, ..., \phi^{i \times (m - 1)}\ %\ p)$ とすると，$A_1, A_2, A_3, ..., A_n$ は条件を満たす． 周期 $m$ の例: 数列$(1, 2, 3, 1, 2, 3,...)$は周期$3$, $\mod{5}$で，$(2^0, 2^1, 2^2, 2^3,...)$は周期$4$ 証明 1. $N$ 個の数列は全て異なる

まずは$H_{i, p},\ V_{j, p}$を求める $i$が揃う確率は$1/30$、$j$についても同様 →900回必要 無理では 同じ場所を何度も行き来すれば大体求まる M = 2のときは境界を二分探索できるが、とりあえずM = 1として重みを初期化したあとに重み付き線形和の推定で良いかも

これは競技中の私用のメモであって参加記ではないです。なのでここに書いてあることは試して採用しなかったこと、そもそも試さなかったことなどが大量に書いてあります。私の最終的な手法は18ターンまで貪欲 + 18ターン目からDUCTになりました。(303位) 前半ビーム + 後半DUCT とりあえずDUCTを実装する DUCTの最初の部分の対称な操作を取り除くとかなり読めそう 状態をまとめる？ とにかく回数回ってなさすぎ！なんとかしてくれ 囲碁とか打てる手多いだろどうやってんの？

st = 0.001967014705966971; et = 1.973203715145631e-05; 一度でも接触したことのあるやつを動かす？ pushで途中までしか押せなくても押す いや押しとる やるべきこと 初期解の改善 近傍の改善

if (a * b <= c)の代わりにif (a <= c / b)とするやつです． 次の2つを証明します． $ab \le c$と$a \le \lfloor{\frac{c}{b}}\rfloor$は同値である $ab \lt c$と$a \lt \lfloor{\frac{c}{b}}\rfloor$は同値でない ただし，$a, b, c$は非負整数，$b \gt 0$とします． 1. $ab \le c$と$a \le \lfloor{\frac{c}{b}}\rfloor$は同値である

writer: qLethon, tester: ferin 解法 2: $n$を$4$で割って余った後半部分のXORを取る 2以外: $n$を$P$で割って余った後半部分のXORを取る 証明 2は$n, n + 1, n + 2, n + 3$のXORを取ると0になるのは有名．

@square10011さんと@noshi91さんに教えてもらったので，メモ Z/pZでの原始根を効率的に見つけるアルゴリズム、存在しないのか…？ — 真紅色に染まるぷーん (@pu__Ne) March 5, 2020 方針 $2 \le k \lt p$をランダムに選んで，原始根がどうかを判定する． p - 1を素因数分解 $O(\sqrt{p})$ p - 1の素因数$a_i$すべてに対して$k^{\frac{p - 1}{a_i}} \not\equiv 1 \pmod{p}$ならkは原始根 素因数の数を$d$とすると$O(d\log p)$ 原始根の数は$\phi(p - 1)$で，これはそんなに小さくならないから全体で$O(d\log p) + O(\sqrt{p}) = O(\sqrt{p})$