Thomson問題 Thomson問題とは、三次元単位球の表面にN個の電荷の等しい粒子を配置するとき、クーロンポテンシャル\( U = \sum_{i wikiをThomson problem - Wikipedia, the free encyclopedia。N=5のときにて三方両錐形が解になったり、N=8で立方体が解になら…

どのメモリを使用したかをbitで管理する。 n個の指示を完了するためには、goal := s[0] | s[1] | ... | s[n-1] でbitの立っているメモリを少なくとも一回は使わなければならない。 逆に、goalで立っているbitに対応するメモリを全て実行したならば全ての指示…

『数値計算の常識』(伊理正夫・藤野和建著)を読んでいろいろ試したくなったので、取り敢えず簡単にできるものをやってみる。定積分\( I = \int_{a}^{b} f(x) dx\)をN等分した台形\(I_N\)で近似するとき、 \( I_{1} = \frac{1}{2}(b - a)(f(a) + f(b)) \) \( …

まず、wを昇順でソートする。 dp[i][j] = #{w[i]以降のみを使って和がjとなる組} sum[i] = w[i]までの和 とするとき、次の3つの場合を考えれば良い。(i) w[0]を使わない (ii) w[0]からw[i]までを使い、w[i+1]を使わない(0 (iii) 全て使う(i)の場合, (i=1,j) …

組(X,Y)(X f(X) = 2X or S - 2Xこれをmod S で見ると、f(X) ≡ 2X or -2X であるから、f^K (X) ≡ 2^K * X or -2^K * Xf^K (X) ≡ -2^K * X は個数がS - 2^K * X の場合に対応するから、X = min(A,B)として、min(2^K * X, S - 2^K * X) (mod S) が答えとなる。 …

sourceとsinkを追加し流量制限にa[i],b[i]を与えることで二部グラフのフローになることは本番中に気づいたが、YESだった場合に経路復元する方法が分からなかった。考えてみると、逆辺のcapはその辺に流したフローの量であるから、ここから容易に復元すること…

dp[i]をi以下の各自然数について素因数分解したときの素因数の個数の総和とすると、dp[a]-dp[b]が答えとなる。よって、前処理で素因数分解をしておけばいい。エラトステネスの篩をするときにsieve[i]にiの素因数のひとつ(最小や最大のものに固定することもで…

高速メビウス変換について自分が勉強した内容をまとめておく。証明はいい感じのサイトを参照のこと。 (http://d.hatena.ne.jp/simezi_tan/20130522/1369203086)集合に関する関数f,gについて次式が成り立つとき、g(S)が計算できているならば、任意のSについて…

練習会でフロー関連の発表をした。内容は↓のとおり。 今までフローを避けてきたので、まとまった勉強をする良い機会となった。しかし、一般マッチングや最大マッチングと最小点カバーにおける関係などはまだ理解できてないので、もう少し蟻本を睨む必要があ…

二分探索するだけ。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) #define ll long long class ProblemSets { public: bool judge(ll E,ll EM,ll M,ll MH,ll H,ll num){ ll x=max(0ll,num-E); ll y=max(0ll,num-H); if(x>E</bits/stdc++.h>…

制約からして二分探索なんだろうとは思ったが本番では解けなかった。 a,bを最初にソートしておき、付値関数C(x)として次のものを考える。C(x): a[i]*b[j]a[i]*b[pos]x のとき、a[i]x なるpos'について pos>pos' が成り立つ。従ってC(x)はO(N)で計算できる。 …

蟻本等の内容を復習していく。 Bellman-Ford法 頂点sから頂点iまでの仮の最短距離をd[i]とする 0: d[s]=0, d[i(≠s)]=INF とする 1: u,v∈V に対してd[v]=min(d[v],d[u]+w(u,v))で更新。更新できなくなったら終了 step1がV回実行されても終了しない場合、負の…

dp(i,j):i番目の操作でj番目のパンケーキを置く確率 class RandomPancakeStack { public: int N; double memo[300][300]; double dp(int i,int j){ if(memo[i][j]>1e-9) return memo[i][j]; if(i==0) return memo[i][j]=1.0/N; double res=0; for(int k=j+1;k

n日までに得る弁当の総数の期待値を計算すればいいわけだが、漸化式がうまく作れない && 他の人のコードを読んでも自明のようにdpしていてよく分からない、というツラさがあったので、この問題の漸化式が私のように漸化式が思いつかなかった人のために愚直に…

量子力学の教科書を読んでいて、球Bessel関数とかLaguerreの陪多項式がある微分方程式の解だと言われてもいまいちピンと来なかったので適当に実装してmatplotlibでグラフを書いてみようと思っていたところ、scipyに特殊関数のmoduleがあることを知った。Spec…

Ford-Fulkerson法を最近勉強したのでやっと解けるようになった。二部グラフの最大マッチングのサイズを求めるという典型題中の典型題。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) //Ford-Fulkerson's algorithm struct </bits/stdc++.h>…

をmod 1e9+7 での逆元を使いながら計算すれば良い。最初 #define MOD 1000000007 としていたが、これだとMODはint型と判断されオーバーフローを起こしてしまってつらかった。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) </bits/stdc++.h>…

以下のBNFに従ってparserを書く。 ・<Cipher>:=(<String>)+ ・<String>:='[' + <Cipher> + ']' | <Letter> ・<Letter>:=('+'|'-')* + <Alphabet>但し、'?'を含むの要素は'A'と同一視する。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) string expr_string(); char expr_letter(); int</bits/stdc++.h></alphabet></letter></letter></cipher></string></string></cipher>…

i番目の町にいて残り時間がjである状態を(i,j)としてこれらの状態間を移動にかかる時間ないしは経過時間をコストとする辺でつなぎ、グラフを作る。あとはDijkstra #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) #define INF</bits/stdc++.h>…

左端から順に塗りつぶして考えていくと、テストケースにうまくいかないものがあり、そこから手が出なかった。 最終状態からk*kの正方形領域内に'B'と'W'の一方のみが存在するものがあれば、その領域を'?'で塗りつぶす。以下これを繰り返して最終的にn*n全体…

string:size_typeとかstring:nposとかよく知らなかったので調べながら書いた。BFSで調べていくが、文字列の長さで枝刈りするだけではTLEしたので、setで既に生成された文字列をメモした。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(i</bits/stdc++.h>…

区間[a,b]と[c,d]の共通部分の長さはmax(0,min(b,d)-max(a,c))であることに注意して全探索する。最初、配列を小さく取り過ぎてREした。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) typedef pair<int,int> P; int blessedTime(int </int,int></bits/stdc++.h>…