読者です 読者をやめる 読者になる 読者になる

Educational Codeforces Round 21 D: Array Division

n=1のとき明らかにNOよってn>=2とする。とりあえず、挿入は考えずに配列を前の部分(S)と後の部分(T)に分けてみる。ただし、S,Tは空であってもよいとする。z=Σ[x∈S](x), w=Σ[y∈T](y)とする。場合1. z=wの場合 ある要素を選んで同じ場所に挿入すればいいからYE…

Educational Codeforces Round 21 E: Selling Souvenirs

DP

エディトリアル見て書いたコード。コメントつき /* エディトリアルのとおりの解法 */ /* 重さ1, 2のsouvenirだけを使ったとき、重さの和がiとする。 このときdp[i]=(x,y,z)は以下の意味。 xはコストの和の最大値 yは重さ1のsouvenirをいくつ使ったか。 zは重…

Educational Codeforces #21 G: Anthem of Berland

上図は3番目の入力例の文字列t="abcab"にダミーの1文字を加えたt+'#'="abcab#"に対してKMP法のDFAを描いたもの。!はその他の文字を表す。tはオーバーラップしてもよいので、最終状態からの遷移もほしい。そこで、末尾にダミーの文字を加えた。これにより、最…

Codeforces #413 E: Aquarium decoration

解説付きコード /* 解説 二人とも好むアイテムの集合をX, MashaだけのはY, ArkadyだけのはZとする 全体でちょうどm個でなければならないが、とりあえずそのことは考えない。 Xからx個選ぶとする。xは|X|から0まで総当りする。 k-x個だけYとZから取る必要があ…

Codeforces #413 C: Fountains

解説付きコード /* 解候補は4種類ある。 何も買わない コインとダイヤモンドでそれぞれ1個ずつ噴水を買う コインで2個噴水を買う ダイヤモンドで2個噴水を買う 前二者は自明 後二者について 噴水をコインで2個買うとする 安い方の必要なコイン数を固定すると…

Codeforces #413 D: Field expansion

まずa[i]は大きい方を優先して使ったほうがいいので降順にソートしておく。 2^17>10^5かつa[i]>=2より 掛け算は縦横合わせてたかだか17+17=34回 よって f[i番目までは掛けた][横の長さ]=縦の長さの最大値 をDPで解けばいい。

AOJ 2606 : Perm Query

順列はいくつかのサイクルで表記できる。 [l, r)に含まれるサイクルの長さをc[l],...,c[r-1]のように表すと lcm(c[l], ..., c[r])回だけ、各要素は値が変わる。i番目の要素は lcm/c[i] 回だけサイクルを回るので、そのサイクルに含まれる数の和をS[i]とする…

AOJ 1169 : 最強の呪文 (The Most Powerful Spell)

接頭辞の長さごとに、辞書順最小となるものを求めるようなダイクストラ法。ゴールへの経路は、もし閉路を含まなければN個以下の頂点からなるはずで、接頭辞の長さの最大値は6*(N-1) これより長い接頭辞で、辞書順がさらに小さいような経路があれば、その呪文…

AOJ 1330 : Never Wait for Weights

int N, M, INF = 10000000, vis[100001], dis[100001], U[100001], V[100001]; vector<pii> G[100001]; void solve() { rep(i, N)G[i].clear(), vis[i] = 0; // Union-Find木 UnionFind uf(N); // クエリの種類 // 0: 返答可能な質問 // INF: 返答不可能な質問 //</pii>…

AtCoder AGC 014 B: Unplanned Queries

性質を満たす木が存在する必要十分条件は、すべての頂点についてクエリに現れた回数が偶数であることである。 (1)すべて偶数回の出現だった場合 すべてのクエリについて 辺(a[i], b[i])で2頂点をつなぐ。ただし、a[i], b[i]がすでに同じ連結成分内にある場合…

AtCoder AGC 014 C: Closed Rooms

k回目の魔法で部屋を開いた状態にする操作は、k+1回目以降の移動にしか影響しない。 よって、魔法を以下のように捉え直す。 1回目の魔法は移動のみ 2回目の魔法は部屋を開く操作ののち、移動 2回目以降の操作はK個以下の部屋を開き、K個以下のマスを移動でき…

AtCoder AGC 014 D: Black and White Tree

int main(){ ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vector<set<int> > G(N); rep(i, N - 1) { int a, b; cin >> a >> b; --a; --b; G[a].insert(b); G[b].insert(a); } /* 完全マッチングが存在するか判定 木なので、葉は必ずその親とペアにな</set<int>…

yukicoder #515: 典型LCP

事前に文字列を辞書順にソートしておく。l番目の文字列とr番目の文字列のLCPをlcp(l, r)のように表すことにする。|lcp(l, r)| <= |lcp(l+1, r)|が成り立つからlcp(l, r)= lcp(lcp(l, l+1), lcp(l+1, r))よって、長さx以下のprefixについて、lcp(i, j)を求め…

宝探し3 | yukicoder

f(X, Y)を質問(X, Y)の結果とすると f(0, 0) + f(10^9, 0) = 10^9 + 2AY AY = (f(0, 0) + f(10^9, 0) - 10^9) / 2 求まったAYを利用して AX = f(0, AY)

Expected diameter of a tree | Codeforces #411

コメントつきコード // 頂点の数、辺の数、連結成分のID、最も遠い点までの距離、連結成分の直径 int N, M, Q, cmp[100001], far[100001], nc, dia[100001]; // グラフ、連結成分ごとに最も遠い点までの距離をすべてもってソートしたもの vi G[100001], F[10…

Find Amir | Codeforces #411

2番目の入力例n=10を考えてみよう。 とりあえず、(i+j) mod (n+1) = 0 となるような辺(i, j)はコスト0なので全部張ろう。 1-10 2-9 3-8 4-7 5-6 あとはコスト1以上の辺を貼るしかない。 実はすべてコスト1の辺で繋げられる。 10+2≡1 9+3≡1 8+4≡1 7+5≡1 よっ…

Minimum number of steps | Codeforces #411 (Div. 1)

abのような形が残らないので、操作していくと最終的に bbb....baa...a のような形になる。 とりあえず実験してみる。 ab →bba bはaを飛び越えるときに1個から2個になった。 abに対する操作は1回。 aab →a<ab> →abba →<ab>ba →bbaba →bb<ab>a →bbbbaa aを2個飛び越えるこ</ab></ab></ab>…

Ice cream coloring | Codeforces #411 (Div. 1)

コメント付きコード // 頂点の数、色の数、頂点vに含まれるアイスの数 int N, M, S[300001]; // グラフ, 頂点vに含まれるアイス vi G[300001], C[300001]; // 解, 色iを使ったかどうか int X[300001], use[300001]; int main(){ scanf("%d%d", &N, &M); rep(…

Subsequence Queries | CS Academy #24

コメントつきコード /* 解法 漸化式で解を表して行列を作ってみる。 行列は添字ごとに異なるので累乗では解けない。 [l, r)の積 A[r-1]A[r-2]...A[l] の求め方 (1) セグメント木を使って求める http://yukicoder.me/problems/no/510 の解法 今回の問題ではTL…

Counting Perfect Subsequences | HourRank 20

sに含まれる文字xの数をn(x)とする。c, dが無いものと見做してsがa, bだけから成り立つと考えてみよう。f[i]を文字a, bをちょうどi個ずつ含む部分列の数とする。i>min(n(a), n(b))のときaまたはbの数が足りないからf[i] = 0i<=min(n(a), n(b))のときn(a)個の…

Birjik and Nicole's Tree Game | HourRank 20

復習用コメント付きコード /* 思いつき方 頂点を黒く塗る その黒い頂点を含む部分木は? 根まで行く距離が長過ぎる HL分解する */ /* HL分解 Heavy-Light Decomposition 木の構築 O(|V|+|E|) あらかじめ与えられた木について、頂点u,v間のパスをセグメント木…

AtCoder ARC 073 Ball Coloring

細かくコメント書いてみた。 /* 2個の配列u,vを値(u[i], v[i])でソートする。 */ template<class S, class T> void psort(vector<S> &u, vector<T> &v, bool isGreater); int main() { ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vll X(N), Y(N); rep(i, N) { cin ></t></s></class>…

Educational Codeforces #20 F: Coprime Subsequences

DP

事前に1~max(a[1],a[2],...,a[n])の約数を求めておく。次に、約数qをもつ数を数えてcnt[q]のように表す。部分列のgcdをgとしたときq|gを満たす空でない部分列を数えよう。これは簡単で、qを約数にもつ数すべてについて、部分列に含むかどうかを考えてcnt[q]^…

Educational Codeforces #20 C: Maximal GCD

a[1]~a[k]のGCDをgとする。 g | a[i]なのでb[i] = a[i]/gのような数列bを定められる。(b[i]>=1)Σa[i] = nよりgΣb[i] = ng | nよってgの候補はnの約数のみ。すべて試す。総和を考慮せずに、とりあえず一番和の小さい数列を作るとa[i]=giその和はΣgi=gΣi=gi*(i…

SRM 658 DIV1 Med: Mutalisk

/* 思いつき方二分探索チェック関数を書くbool のDPになった。boolのDPは次元を一つ減らせるかも。intで残りの1を使える回数の最大値をもたせればいい。*//*dp[i][j][k]:=i番目まで破壊し、残りj回9の攻撃、k回3の攻撃ができるとき、残りの1の攻撃回数の最大…

SRM 712 DIV1 Easy: LR

操作後のA[i]をA'[i]のように表記する。(1)LRの操作Lの操作によりA'[i] = A[i-1]+A[i]A'[i+1] = A[i]+A[i+1]更にRの操作によりA''[i]= A'[i] + A'[i+1]= (A[i-1]+A[i]) + (A[i]+A[i+1])= A[i-1]+2A[i]+A[i+1](2)RLの操作Rの操作によりA'[i] = A[i]+A[i+1]A'[…

AtCoder ARC D: 見たことのない多項式

ガウス・ジョルダンの消去法などを知っていればO(n^3)で部分点40(/100)、ラグランジュ補間を知っていればO(n^2)で部分点80(/100)をとれる。 ラグランジュ補間を工夫する。 ラグランジュ補間 一般に多項式P(x)についてi!=jのときx[i]!=x[j]ならば P(x) = Σ[i=…

CS Academy #23 (Div. 2 only) No Prime Sum

Sに含まれる数を頂点とし、その和が素数になるような2値の間に辺を張ったグラフを考える。すべての辺について、端点の少なくとも一方にある数は使わない。いいかえると、使わない数の集合はすべての辺の端点の少なくとも一方を含む。これは頂点被覆。 使わな…

配列のswapとvectorのswap

C++

vectorのswap vector<int> a(N), b(N); swap(a, b); このswapの実体はvector::swapでswap(a,b)はO(1)で終わる。DPでメモリを節約するのによくやる。 配列のswap int a[N] = {}, b[N] = {}; swap(a, b); 先程のコードを配列に変えただけ。実はこちらのswap(a,b)に</int>…

Codeforces #408 (Div. 2) E: Exam Cheating

DP

dp[i][j][fs][sc] =i番目まの問題まで確定していて、j回カンニングしている。1人目に対して直前にしたカンニングの左端はiからfs個左、2人目に対して直前にしたカンニングの左端はiからsc個左とする。ただし、fs,scはK以上はすべてKの1値で表す。このとき最…

Codeforces #408 (Div. 2) D: Police Stations

1個の町に複数の警察署がある場合もありうるが、明らかに無意味なので1個の町にはたかだか1個の警察署しか無いとする。 道路で結ばれた町は、全体で木になっている。 ある頂点が複数の警察署でカバーされているとする。そのうち最も近い頂点をu,二番目に近い…

Codeforces #408 (Div. 2) C: Bank Hacking

与えられた銀行の関係は木になっていることがわかる。最初にオフラインにする頂点を固定する。この頂点を根とする根付き木を考える。他の頂点をオフラインにするには、すでにオフラインの頂点と隣接していないといけないのであった。よって、親がオフライン…

AtCoder ARC071C: 井井井 / ###

解を式で表してそれを簡単にする (右端)-(左端) の長さの重複を認めた集合をW, (上端)-(下端) の長さの重複を認めた集合をH, とすると解は Σw*h (w∈W, h∈H) で表せる。 これにはよくある式変形により Σw*h (w∈W, h∈W) =Σw(w∈W) * Σh(h∈H) たとえば w0*h0+w0*…

Atcoder ARC E: TrBBnsformBBtion

部分文字列の文字の順序は関係ない つまり、部分文字列は任意の順序に並び替えることができる。 隣接する異なる2文字を入れ替えられることを示す。 AB →BBB →BBAA →BBBBA →BA したがって、任意の隣接する2文字は入れ替えられる。なのでバブルソートの要領で…

yukicoder #503: 配列コレクション

操作回数をa, 最後に残る要素の数をbとする。N>=Kよりa>=1K>=2よりb>=1 最終的にAの各要素はDの累乗になることがわかる。D=1のとき、コーナーケースでAのすべての要素は1になるので解はb 以下、D≠1とする。Aの要素はDの累乗であり、かつ操作回数がaなので、…

Codeforces #406 (Div. 1) B: Legacy

解法 セグメント木の上でダイクストラ セグメント木にある各頂点でダイクストラする。もう少しきちんと説明する。まず、操作2について考えてみるv->[l, r]であった。[l, r]は、セグメント木のいくつかの対応する頂点に分解できる。(図1)この頂点はたかだかlo…

yukicoder #492: とても長い数列と文字列(Long Long Sequence and a String)

解法 f(n)を文字列にしたものをS(n)とする。|S(n)| = 2|S(n)| + (n^2の桁数)更に|S(4)| = 16 = 2^4なので|S(60)|>2^60 が成り立つ。よってR<|S(60)|であり、K>60の場合は、K=60と見なしてよい。以下、1<=K<=60とする。f(n)の各桁の値d(0~9)の出現数をcnt[n][…

SRM 710 DIV1 Easy: ReverseMancala

解法 入力例(0)、(1)からわかるように、Bの操作の逆はAの操作で、Aの操作の逆はBの操作で表せる。なのでstartとtargetの両方にAの操作を適用してある状態(かりにSとおく)にできればよい。つまりstart->(Aの繰り返し)->Sかつtarget->(Aの繰り返し)->Sとなるよ…

Codeforces #403 (Div. 2) F: Innokenty and a Football League

解法 行列の累乗みたいなことをするには、 O(ビット数*n^3) で間に合わない。 実はbitsetを使えば十分速度が出せる。 メモリや実行速度が十分でないbool変数を使った解法は、bitsetを使うだけで間に合う場合がある。 最大の移動回数を求めるには、 0111<1000…

Codeforces #403(Div. 2) E: Underground Lab

解法 k人のクローンがいてそれぞれceil(2n/k)個の頂点を訪れることができるので、訪れることができる頂点の数の合計Sは S = ceil(2n/k)*k >= 2n 与えられたグラフは連結グラフなので全域木が存在する。与えられたグラフのある全域木Tについて考える。 TでDFS…

Codeforces #403 (Div. 2) C: Andryusha and Colored Balloons

解法 木の問題は、根付き木にすると見通しが立てやすくなることが多い。 根から再帰的に色を塗っていく。 ある頂点vの色をcur_col, 親の色をpar_colとする。また、部分木vのうち色が決まっているのはvだけとする。子の色を決めたい。問題文中の色を塗る条件…

Codeforces #403 (Div. 2) D: Innokenty and a Football League

解法 各チームについてshort nameの付け方は2通りある。 また、それぞれのチームのshort nameの関係は、いくつかの包含関係で表せる。 2値変数Aが真であることをa、偽であることを¬aのように表すと (x[1]=>x[2])∧(x[2]=>x[3])∧(x[3]=>x[1])∧(¬x[3]=>x[2])∧(¬…

SRM 708 DIV1 Medium: PalindromicSubseq

X[i]の値を具体的に求めていこう。 各文字S[i]についてそれぞれX[i]を求める。S[i]がある回文に含まれる場合、S[i]と一致するようなもじS[j]がある。ただし、i=jでS[i=j]が奇数長回文の中心である場合も含む。iとjを総当りで固定した場合、それだけでO(N^2)…

Codeforces #402 (Div. 1) B: Bitwise Formula

解法 AND, OR, XORのいずれもビットごとに独立に計算されることに注目する。ボブの選ぶm桁の数値(仮にxとする)は、各桁独立に求められる。各桁は0か1の2通り。それぞれ試して各変数のm桁目を求めて和をとり、最小値、最大値に対してそれぞれ適切なほうを選ぶ…

SRM 709 DIV1 Medium: Softmatch

http://codeforces.com/blog/entry/49911?#comment-344869 ↑の理解 |patterns|<=5なのでこれの最大ケース|patterns|=5の場合だけ考えてみよう。以下のような愚直なDPはすぐに思いつく。 dp[i][p[0]][p[1]][p[2]][p[3]][p[4]] := Sのi番目まで確定していて、p…

SRM 709 DIV1 Easy: Xscoregame

|A|<=15で順列で最小とあり、ビットDPっぽい。しかし、 X+(X^Y) の後半xorパートが怪しい。 の値が大きければ良いというわけでもない。 そこでA[i]<=50に注目する。A[i]<=50<64=2^6である。つまりA[i]の下位6ビット以外はすべて0。それに対してXの値は当然1…

Codeforces #399 E: Game of Stones

ニムのルールを少し変えたゲームの勝敗を知りたい。石の山の状態の数とその状態の遷移の数が十分小く表せれば、Grundy数やるだけ。山の状態を適切に表したい。愚直に考えれば山の状態=(石の個数, 1~60のうち取り除いたことのある個数についてのフラグ)たとえ…

Codeforces #399 D: Jon and Orbs

p[i]<=1000に注目する。p[i]/2000 <= 1000/2000 = 1/2 (1) i = 0,1,2,...,Tターンたったときに全種類そろっている確率をf[i]とし、これをすべて求めてl[i] = (p[i]-ε)/2000 の値で二分探索すればいい。ただし、(1)よりf[T]>=1/2でなければならない。そのよう…

AtCoder ARC069 E: Frequency

数列を辞書順最小にしたいということから、貪欲。ちゃんと説明する。 最初に取り除く石について考える。取り除く候補の石の山が2種類あるとし、それぞれp,qとする。pを取った場合に次のxは3、qを取った場合に次のxは7とする。このとき解は前者では 3,?,?,..…

AtCoder ARC069 D: Menagerie

i(>=2)番目の動物はi-1番目、i-2番目の動物が決まっていればわかる。そこで、1番目と2番目の動物の種類をたかだか4通りを総当りで仮定し、そのそれぞれの仮定について、他のN-2種類の動物を決める。そうしたら、仮定が間違っていないかを条件に従ってチェッ…