atcoder.jp コンテスト中はコストの計算量の抑え方が分からずにsubmitできませんでした。 公式解説にもあるように生徒hを昇順にソートし、前と後ろからの累積和を予め計算しておけば$O(1)$でコストが計算できます。 累積和系のテクニックの大事さを痛感しま…

巡回セールスマン問題(TSP)です。 atcoder.jp $N$が17なのでビットDPを使えば計算量的に間に合うようです。 $S$をビット列の集合として以下のDPを作成します。 DP[S][v]: 訪問済みの集合Sの頂点vからスタートする時の距離の総和 例えば$N=5$の場合、右から順…

最近Cまでしか解けずレートが全然上がりません...。 今回のD問題も方針自体は分かったのですが、友達の数が最も多い集団を探す関数の計算量が抑えきれずTLEしてしまいました。 解説動画でも紹介されていたUnion Findを用いた実装をしてみました。 こちらを参…

というタイトルですが実際は以下の動画を見た感想になります。 【医師解説】全員にコロナウイルス検査をしても意味がない理由 実際に新型コロナウィルス(COVID-19)のデータを使って計算している訳ではないので注意して下さい。 (※内容に誤りなどがあれば遠慮…

ゼロからできるMCMCを現在読んでいます。 修士課程で量子モンテカルロ法を使った数値計算を行っていたのでMCMCについてはある程度知っているのですが初心に戻って基礎から勉強し直しています。 実は現在のお仕事でもSAを使って計算することがあり、MCMCを使…