各商品をスタート地点として見てBFSっぽいことをする。はじめにキューへすべての始点入れておくだけ。 int N, M, K, S; vi G[100005]; int dis[100005][102]; vi pos[102]; void bfs(int kind) { queue<pii> Q; each(p, pos[kind]) { Q.push({ p,0 }); dis[p][kin</pii>…

転倒数の偶奇は操作回数のそれと等しい。 とおく。 l番目の要素とr番目の要素を交換したとする。 l番目とr番目の間にz個の要素があるとする。 また、そのうち、もとのl番目より大きい要素をgL個, 小さい要素をlL(=z-gL)個とする。 まずl番目と間z個の関係だ…

排他的論理和が総和以下っぽい。詳しく説明する。 とする。 まずが成り立つ。更にも成り立つ。 部分文字列の左端lを固定してみる。このときr=lならば明らかに条件を満たす。 A[l]⊕A[l+1]⊕...⊕A[r] < A[l]+A[l+1]+...+A[r] が成り立つと仮定する。このとき、…

取り出したQ個の要素の最小値miについてmi>=A[i]が成り立つとする。 このとき、Aのmi未満の要素は使えないので*の記号で表すと {A[0], A[1]}, *, {A[3]} , *, *, {A[6], A[7], A[8]}, *, {A[10]} のように*でAの要素がいくつかのグループに分けられる。この…

出入り口に使う面の組、行の組（列の組）ごとに操作回数を考える。具体的には頭の中でサイコロを回転させつつ展開図に操作回数や行または列の対応を書き込んでいく。すると上のような図を得る。あとは最小値を計算するだけ。 // faceA, faceB, rowA, rowB, c…

int N, K, D; cin >> N >> K >> D; vi A(N); // とりあえずソートしておく rep(a, N)cin >> A[a]; sort(all(A)); vi in(N+1), out(N+1); // 小さい方から0個をすべて使って箱詰めできている in[0] = 1; out[0] = 1; ll cur = 0; rep(a, N) { cur += in[a]; /…

構成のベースは以下の２通り。 適切な最大の高さxは二分探索で求める。この通りに構成したときに、余りが出る場合があるが、x以下のすべての高さが存在するので、余りをrとするとceil(r/x)個だけ同じ高さの横に挿入すればいい。 // Hが大きすぎても無意味な…

int N, K, L; cin >> N >> K >> L; int M = N*K; vi A(M); rep(a, M)cin >> A[a]; sort(A.rbegin(), A.rend()); // 必ずできる一番小さい樽の大きさで制限 ll lim = (ll)A.back() + L; ll re = 0; // 使ってない板の数、作った樽の数 int cnt = 0, taru = 0;…

起こす人uから起こされる人vへ辺(u, v)を張るようなグラフを考える。このグラフは閉路があってややこしい。とりあえず強連結成分分解してみよう。各強連結成分において誰か一人でも起きれば、その強連結成分内において全員が必ず起きる。よって強連結成分S内…

N=32とする。1<=v<w<=31としてを満たすすべての辺(v, w)の辺を貼ると1から2<=x<=31までの経路の和は2x-2通りである。これは経路数をf(x)と表すと f(x) = f(1) + f(2) +...+ f(x-2) + f(x-1) = (f(1)+f(2)+...+f(x-2)) + f(x-1) = f(x-1) + f(x-1) = 2f(x-1)であるため。よってKを2進数として各桁をみてk(>=0)ビット目が立っていたら頂点k+2から頂点Nに辺を張ればよい。 int K, N = 32; cin >> K; vector<pii> E; for (int w =…</pii></w<=31としてを満たすすべての辺(v,>

/** 2以外の素数はすべて奇数 x*x<=Kであるような最大のxを考える。 a+bが奇数であるような偶数aをx個と奇数bもx個使って 素数がx*x個作れる。 K' = K-x*x としてK'に対しても同様に繰り返していけばいい。 以前に使った偶数、奇数に対しては素数を作らない…

http://codeforces.com/blog/entry/59484?#comment-431237 これを見てそのとおりに書いた。 using P = array<int, 7>; static bitset<2001> vis[10][10][10][10][10]; int N; cin >> N; vi A(N), B(N); rep(a, N)cin >> A[a] >> B[a]; queue<P> Q; Q.push({ 0,0,0,0,1,0</p></int,>…

ll p, q, b; cin >> p >> q >> b; ll g = gcd(p, q); // とりあえず約分 q /= g; // 分母をb^kの形にできればOK // そのためには分母qをgcd(b, q)で割り続けて // bと互いに素な素因数をもつかどうか判定する string re = "Finite"; while (q > 1) { ll h = …

/** 実験すると各引数が二項係数と同じ個数だけxorに使われることがわかる。例えば f(1, 2, 4, 8) = (1)⊕(2⊕2⊕2)⊕(4⊕4⊕4)⊕(8) であり、各引数はC(3, 0), C(3, 1), C(3, 2), C(3, 3) 回だけ使われている。 xorは同じ整数同士で打ち消し合うので二項係数の偶奇…

/** Flowrisa から Beetopiaへのパスの辺を 取り除いたグラフを考えよう。このグラフは少なくとも2つの部分木からなり、 1つはFlowrisaを含み、もうひとつはBeetopiaを含む。 もとのグラフにおいてFlowrisaを含む部分木からBeetopiaを含む部分木 への経路だ…

const string ALPHA = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; string NAME[3] = { "Kuro", "Shiro", "Katie" }; int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); ll N; // 0<=N<=10^9 cin >>…

公式解説みて書いた void dfs(int u, int p, int d, vector<vi> &H, vi &dist, vi &score) { dist[u] = d + score[u]; each(v, H[u])if (v != p) { dfs(v, u, dist[u], H, dist, score); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fix</vi>…

(x[j], y[j])を辺とするようなグラフを考える。このグラフの各連結成分内では要素は各辺を介したスワップによって自由に配置できる。よって頂点iを含む連結成分にp[i]が含まれるかを調べればいい。連結成分の識別にはUnion Find木を使うと便利。 int N, M; v…

priority queueに(s[i,i], i), 1<=i<=Nを挿入していく。あとは先頭の要素をとってきて右端を1個伸ばしたものをpriority queueに挿入していく。ダイクストラ法で辺によって隣接する頂点を追加するのに似ている。s[l, r] <= s[l, r+1]なのでs[l, r]が取り出さ…

隣接要素同士の交換しかできないのだから、もし白または黒のみであれば、最小の操作回数は転倒数に等しい。 この問題では、白と黒の２色の並び方ごとに操作回数が異なる。しかし、白と黒の並びが定まれば、操作回数は一意に定まる。なぜなら、各並び方につい…

よい盤面である条件は、1<=i<=Nについてi行目とi列目が等しいことと同値。例えばN=4については、以下が等しければよい。 更にこの図から、任意の自然数の組(A, B)について(A+x, B+x) (xは自然数) も(A,B)と比較対象が同じであることがわかる。たとえば、(A, …