AOJ 1320 City Merger

AOJ

問題文(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1320)AOJ2022(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2022)とほとんど同じ問題。他の都市名の部分文字列になっている都市名を予め取り除いてからbitDPをする。 #inclu…

AOJ 2534 Dictionary

AOJ

問題文(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2534)まず、与えられた文字列の組(string_i, string_j)(i このグラフの構築段階で(i,j)に辺があるのに(j,i)にも辺が張られているば矛盾しているのでfalseを返す。また、'@'は最小であるは…

Codeforces Round #341 (Div. 2) D. Rat Kwesh and Cheese

問題文はこちら(Problem - D - Codeforces)まず\( (x^y)^z = (x^z)^y \)であることから\(a_4, a_8, a_{12}\)が候補から外れる。 単純に与えられた式を計算するとオーバーフローしてしまうため、対数をとって比較していく。ただし、\(x (i) x,y,zが全て1より…

焼きなまし法でThomson問題の解を探索する

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

SRM 667 Div1 Easy Order Of Operations

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

Richardson補外とか丸め誤差について

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

AOJ 2333 My friends are small

まず、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) …

SRM 664 Div1 Easy Bear Plays

組(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) が答えとなる。 …

Codeforces Round #304 (Div. 2) E Soldier and Traveling

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

Codeforces Round #304 (Div. 2) D Soldier and Number Game

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

高速メビウス変換について

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

ネットワークフロー

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

SRM 657 Div1 Easy Problem Sets

二分探索するだけ。 #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>…

ARC 37 C問題 億マス計算

制約からして二分探索なんだろうとは思ったが本番では解けなかった。 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回実行されても終了しない場合、負の…

SRM 656 Div1 Easy RandomPancakeStack

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

AOJ 1056 Ben Toh

AOJ

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

scipyの特殊関数

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

AOJ 1163 Cards

AOJ

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>…

ABC 31 D 多重ループ

を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>…

AOJ 2587 Broken Cipher Generator

AOJ

以下の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>…

AOJ 2021 Princess in Danger

AOJ

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>…

SRM 655 div1 easy BichromePainting

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

AOJ 1296 Repeated Substitution with Sed

AOJ

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>…

AOJ 1315 Gift from the Goddess of Programming

AOJ

区間[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>…