No.1573 Divisor Function - yukicoder

E - Stop. Otherwise... | AtCoder Regular Contest 102

包除原理とド・モルガンの法則使って求めるやつ。 包除原理 - Wikipedia 六面サイコロを考える。つまりK=6として、出目の和が7になるペアは(1, 6), (2, 5), (3, 4)の3種類。これらのペアが一つもできない場合を求めたい。すべての出目の組をUとし、それぞれ…

No.767 配られたジャパリまん - yukicoder

フレンズの数K<=20なので、O(K2 * K)みたいな計算量で解けそう。 とりあえず自明に求まるものを求めてみる。 任意のフレンズの集合に対してそのフレンズのいるところを必ず通る経路をすべて求める。フレンズの位置の集合をSとする。Sのすべての要素をa[i]<=a…

No.727 仲介人moko - yukicoder

解は Π_{0<=i

No.728 ギブ and テイク - yukicoder

i<jとする。 (i, j)が満たしたい条件は A[i]+R[i]>=A[j]かつA[i]>=A[j]-L[j] jをループで固定する。jを昇順に見ていくならば A[i]+R[i]>=A[j]を満たすiはjが増加するごとに条件がきつくなる。 なのでi<jについて A[i]+R[i]の値を優先順位度付きキューで持っておいて、 A[i']+R[i']<A[j]となるような添え字i'を取り除いていく。 あとはA[i]>=A[j]-L[j]であるが、 取り除いたあとに残っているすべてのi</jについて></jとする。>

D: Median of Medians - AtCoder Regular Contest 101 | AtCoder

中央値がxの場合=>中央値がx以上の場合 f(x) := 「x以上の値が中央値となる連続部分列の個数」とする。 ここで部分列がH(N, 2)個あるので、そのちょうど真ん中になるのが中央値。 つまり f(x) >= ceil(H(N, 2)/2) を満たす最大のxが解。fは単調増加なので二…

E. Hash Swapping | soundhound2018-summer-final-open

方針 O(Qsqrt(N))で間に合いそうなので平方分割を試す クエリは[l, r)で0-indexedとする。 f(x, i) = 106i ord(S[x][i])(0<=i

Manhattan Center (manhattan-center) | CSA

与えられた頂点のK個からなる部分集合について、最適なPの座標はx座標の中央値となる。 なので、Pの候補は与えられた頂点のx座標に限られる。 これらx座標を昇順に見ていく。(以下、x[k]<x[k+1]とする) P=x[0]としてとりあえず近いK個を集合Lに入れておく。残った頂点は集合Rに入っているとする。 x[k] -> x[k+1]と変化したとする。x[k]のときの最適な構成Lから、x[k+1]のとき</x[k+1]とする)>…

No.715 集合と二人ゲーム | yukicoder

grundy数を出力して図にしてみる。 十分大きな整数について、そのgrundy数が34周期になっていることがわかる。 int dp[201]; int g(int n) { if (dp[n] != -1)RT dp[n]; set<int> S; for (int i = 0; i < n; ++i) { int l = max(0, i - 1); int r = max(n - 2 - i</int>…

E. Intercity Travelling | Educational Codeforces #47

int n; cin >> n; vector<mint> pw(n + 1), a(n + 1); pw[0] = 1; rep(i, n) { pw[i + 1] = pw[i] * 2; int x; cin >> x; a[i + 1] = x; } mint re, b; rep(i, n) { b = b * 2 + a[i]; re += (b + a[i + 1])*pw[n - 1 - i]; } cout << re << endl;</mint>

F. Dominant Indices | Educational Codeforces #47

再帰で解く。 とりあえず、d[x]は最大の深さの分まで求めればいい。それ以降は0が続くので。 頂点xのxを除くすべての子孫についてdが計算済みとして、d[x]を計算する。d[x]のすべての子供だけを見ればd[x]が求まる。つまり、すべての子供yについてd[x][i+1] …

D. Pave the Parallelepiped | Codeforces Round #497 (Div. 2)

とりあえず最大の入力以下の自然数の約数を列挙しておく。入力中最大の自然数をMとして、M以下の各自然数について、その倍数を見ていく。調和数を考えるとの計算量とわかる。 各データセットについて、別々に処理する。 A, B, Cのうち、少なくともひとつの約…

F. Berland and the Shortest Paths | Codeforces Round #496 (Div. 3)

単一始点最短経路問題で、すべての頂点に最短で到達するのに必要な辺だけを選ぶと木になることが知られている(最短経路木)。 なので、この問題では最短経路木を列挙すればいいことがわかる。根でない頂点vに最短距離で到達した時、直前の頂点をuとする。d(x)…

E2. Median on Segments (General Case Edition) | Codeforces Round #496 (Div. 3)

f(x) を「中央値をxとする部分文字列の数」とする。f(m)が解。 とおくと を得る。 あとは、g(y)を求めるだけ。g(y)の値は、中央値がy以上の部分文字列の数を表す。 部分文字列の中央値がy以上である必要十分条件は (y以上の値の数)>=(y未満の値の数) とわか…

E1. Median on Segments (Permutations Edition) | Codeforces Round #496 (Div. 3)

数列なので中央値mはちょうど1つだけある。mの位置に注目すると、条件を満たす部分文字列は、mから左へ0以上、右へ0以上の長さだけ伸ばしたものに限られる。 部分文字列がmの左側へl, 右側へrだけ伸ばしたものであるとする。また、m以外の値はmとの大小関係…

D. Polycarp and Div 3 | Codeforces Round #496 (Div. 3)

ある非負整数が3の倍数かどうかは、各桁の値の和が3の倍数かどうかを調べればいい。なので dp[i][j] := 「もとの数字の上位i桁まで確定して、今作っている数の桁の和を3で割ったあまりがjであるときの最大の仕切りの数」 のようなDPを解く。 int dp[200005][…

B. Sonya and Exhibition | Codeforces Round #495 (Div. 2)

一人しかいない場合を考えてみる。その人が見る花壇の長さをa, その花壇に含まれるバラの数をx, ユリの数をyとおく。 x+y=aの条件でxyを最大にしたい。 を得る。 よってaが偶数の時で最大。 aが奇数のときで最大。 簡単のためとすると、x, yの値はとなる。要…

No.269 見栄っ張りの募金活動 | yukicoder

DP

愚直なDPを考えてみる。 f(i, j, k) = 「i人目まで確定して、前の人がj円払った時、合計金額がk円である場合の数」 これでは間に合わない。 とりあえず、最初の人の募金額を0~Sの範囲で総当たりして固定し見てよう。先の人も含めて、少なくともその額を支払…

AOJ1132 : Circle and Points

最適解が2点以上含む場合は、そのうちの2点を通る円でその最適解を必ず構成できる。 最適解を構成する頂点の集合をSとする。(|S|>=2)。Sの外側の点だけを拾って凸包を構成する。ただし、Sの点が一直線上に並ぶ場合は線分を構成する。これをTとおく。Sの点を…

Marked Ancestor (AOJ 2170, JAG Summer 2009)

ライブラリがあれば楽にとけるやつ。HL分解して、マークしたかどうかはBinary Indexed Treeなどを使うだけ。 vector<vi> G(N); FOR(i, 1, N) { int p; cin >> p; --p; G[p].push_back(i); } HLDecomposition hld(G); // 0ならばマークされていない。 // そうでな</vi>…

E: Or Plus Max - AtCoder Regular Contest 100

K番目の解をanswer(K)と表すことにする。 とおくと が解。 f(x)の条件の部分をもう少し緩くしてみる。 とおくと、後者の(i, j)の集合は、前者のそれを含むので が成り立つ。更に、 のときが成り立つ。したがって以下が成り立つ。 g(x)が簡単に求まるとしてan…

D: Equal Cut - AtCoder Regular Contest 100

BとCの間区切りを総当たりで固定する。 このとき、前半部分と後半部分の両方ともできるだけ均等に分けるのが最適。なぜか。 AとBの区切りを考えてみよう。AとBをできるだけ均等に(差が最小になるように)分けたときの小さい値をlow, 大きい値をhighとする。…

C: Linear Approximation - AtCoder Regular Contest 100

B[i] = A[i] - iとおく。 入力例2ではB[i]は以下のような値をとっている。なお図ではb=2と仮置きしている。 であるから、 これは上図では点と直線y=bの距離の和を求めればいいことがわかる。 直線bを上下に動かしてみると以下の事がわかる。 一番上の点より…

AOJ 2333 : 僕の友達は小さい My friends are small (JAG Summer 2010)

まずは簡単な例外的な組合せから数えてみる。以下、解をanswerと表記する。どの友達もリュックに入れることができないならばanswer+=1。また、すべての友達をリュックに入れることができるならばanswer+=1。 それ以外の場合を数える。とりあえずリュックに入…

10歳の動的計画 (AOJ 2335) (JAG Summer 2010)

とりあえず縦横を別々に考えられる。よって、縦でx回寄り道して座標Nにいる場合の数をf(x), 横でy回寄り道して座標Mにいる場合の数をg(y)とすると が解である。ここでは縦の移動と横の移動を別々にみたあとにマージするとして、そのマージの仕方の数。N+M+2K…

D - Snuke Numbers | AtCoder Regular Contest 099

証明なしで思いつき方だけ書いておく。 自然数nがすぬけ数あるためには がnより大きいすべてのmについて成り立たなければならない。 まず、十分大きいmに対して、S(n), S(m)の値は十分小さいので と見做してよい。 小さめの自然数nについて、十分大きなm(こ…

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の要素がいくつかのグループに分けられる。この…