2018-05-01から1ヶ月間の記事一覧

A. Fair | Codeforces Round #485 (Div. 1)

BFS

各商品をスタート地点として見て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>…

B. Petr and Permutations | Codeforces Round #485 (Div. 1)

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

D: Xor Sum 2 - AtCoder Regular Contest 098

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

E: Range Minimum Queries - AtCoder Regular Contest 098

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

D: Dice Room | JAG Asia 2010 (AOJ 2245)

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

E. Pencils and Boxes | Educational Codeforces Round 44

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]; /…

D. Sand Fortress | Educational Codeforces Round 44

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

C. Liebig's Barrels | Educational Codeforces Round 44

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

夏合宿の朝は早い | JAG Domestic 2016

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

yukicoder #690 : E869120 and Constructing Array 4

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

yukicoder #689 : E869120 and Constructing Array 3

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

C. Elevator | Codeforces Round #483 (Div. 1)

BFS

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

A. Finite or not? | Codeforces Round #483 (Div. 1)

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

B. XOR-pyramid | Codeforces Round #483 (Div. 1)

/** 実験すると各引数が二項係数と同じ個数だけ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は同じ整数同士で打ち消し合うので二項係数の偶奇…

C. Kuro and Walking Route | Codeforces Round #482 (Div. 2)

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

B. Treasure Hunt | Codeforces Round #482 (Div. 2)

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

F - Monochrome Cat | AtCoder Regular Contest 097

公式解説みて書いた 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>…

D - Equals | AtCoder Regular Contest 097

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

C - K-th Substring | AtCoder Regular Contest 097

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

E - Sorted and Sorted | AtCoder Regular Contest 097

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

B: Find Symmetries | AtCoder Grand Contest 023

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