2018-05-30から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個の関係だ…