atcoder.jp 今回はダブリングと呼ばれる手法を使って解いて見ます。 drken1215.hatenablog.com 上のブログでも解説されているようにnext[i][v]を定義します。 next[i][v]: vから$2^{i}$ステップで到達できる場所 まずは$i=0$の場合を考えてnext[0][v]を初期…

atcoder.jp 幾何分布の期待値に対応しているようです。 幾何分布の期待値の計算は以下を参照して下さい。 幾何分布の確率関数からの期待値と分散の導出 | AVILEN AI Trend k回目で初めて成功する期待値を求めてNまで合計すれば計算できます。 コードは以下に…

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を用いた実装をしてみました。 こちらを参…

「ABC 164 D - Multiple of 2019」をC++で実装しようとした。 butch416.hatenablog.com 数年ぶりにC++を触ることになる。 intの範囲とかをもう少し勉強する必要がある。 ・参考ページ： 【C言語入門】整数(int、long int、short int)の使い方 | 侍エンジニア…

問題文 1から9までの数字のみからなる文字列Sが与えられます。 次のような条件を満たす整数の組$(i, j)(1\le i \le j \le |S|)$の総数を求めてください。 条件：$S$の$i$文字目から$j$文字目までを$10$進法の整数としてみると、この整数は$2019$の倍数である…