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種類の動物を決める。そうしたら、仮定が間違っていないかを条件に従ってチェッ…

Codeforces #397 E: Tree Folding

Codeforces #397 D: Artsem and Saunders

まず2式 g(h(x)) = x h(g(x)) = f(x) を別々に考えてみる。 g(h(x)) = x を満たすg,hは 例えば g(x)=x h(x)=x があり、必ず構成できる。 また h(g(x)) = f(x) については g(x) = x, h(x) = f(x) とすればよく、これもf(x)の値によらない。 ところが、2式を同…

101 Hack 46 lena-sort : Lena Sort

yukicoder #484: 収穫

解説の理解

yukicoder #483: マッチ並べ

各座標を頂点としてグラフを書く。連結成分ごとに考えてみる。 グラフが木になる場合は、根付き木と見なして親から子へ、マッチの頭薬を向けて並べていけばいい。 グラフが閉路を1個だけもつ場合。まず、その1個の閉路を、片方向(時計回り、反時計回りどち…

yukicoder #482: あなたの名は

解法 N>=2なので ソートするのにかかる最小の交換回数をsとしたとき s-K>=0 かつ 2 | (s-K) ならばOK 与えられているのは順列で、グラフにしてみるとsの求め方はわかりやすい。複数のサイクルに分割できてサイクルごとにソートするのが最も交換回数が少なく…

yukicoder #250: atetubouのzetubou

実行時間をf(X,D)とすると f(X,D) = (X+D-1)!/(X!(D-1)!) これを普通に計算するとオーバーフローなどが面倒。 なのでとりあえず素因数分解した形で、肩の足し引きだけしておく。 素因数を1個ずつ掛けていって、tを超えないか、オーバーフローしないかをチェ…

SRM 638 DIV1 Medium: NarrowPassage2

解法は簡単だが思いつけないタイプ 解法 分割統治法、再帰 maxSizeSum=10で色々やってみる。 m = min(size), M = max(size) とする。 size = {5,2,3,4,6} のような場合 m = 2, M = 6 であり、 m+M <= maxSizeSumが成り立つので 2はどこにでもおける。 すなわ…

SRM 708 DIV2 Hard: PalindromicSubseq2

dp[i][j]:=左は文字iまで、右側はjまで見たときの偶数長(長さ0以上)の回分の個数の数(ただし1<=i<=j<=N) たとえば、文字列sが以下のような形の場合(1-indexed) abcxycba abc...ba dp[3][7] = 2^2 = 4 1<=j-i<=nを nから順に確定していけばいい。つまり dp[i]…

SRM 708 DIV1 Easy: BalancedStrings

文字列s[0]~s[N-1]の文字列の末尾に文字追加して解を構成すことを考える。ある文字列s[i]に文字を追加したときに全体で、instabilityは0~1、similarityは0~100*(N-1)増加する。このようにinstabilityの値のほうが調整がし易い。そこでまずsimilarityが小さく…

Codeforces #396 Div. 2 E: Mahmoud and a xor trip

とりあえず1を根とする根付き木として考える。 f[i][j][k] := 頂点iについて、頂点iの子孫のうち、iからその子孫までのパスの距離のjビット目がkであるような子孫の数 とする。これをメモ化再帰で解く。 ある頂点uについて uが最も根に近い頂点であるような…

Codeforces #396 Div. 2 D: Mahmoud and a Dictionary

等しい要素は、素集合データ構造でくっつけていく。 また、互いに素なAとBが反意語であることを示すのに an[A] = Bかつan[B] = A のような配列を使う。(unifon find木の各集合を代表する頂点を使えば単なる配列になる。) あとは問題文に従ってこれらを操作す…

Codeforces #396 Div.2 C: Mahmoud and a Message

解法 まず、[l,r)の部分文字列を作れるかどうか判定するのに 各文字のカウント部分和を計算しておき、 文字iについては cnt[i][r] - cnt[i][l] で数えられる。つまり[l,r)の範囲に文字iがあるかどうかわかる。 [l,r)の範囲にあるすべての文字iについて r-l >…

SRM 547 DIV2 Hard: RelativelyPrimeSubset

解法 Sの要素が100以下と小さいので100以下の素因数でビットDPを試みたい。しかし、100以下の素数の個数は25個なので 2^25 * |S| <= 2^25*50 = 1.6777216 × 10^9 で間に合わない。 ここでたかだか25個の素数を列挙してみると 2, 3, 5, 7, 11, 13, 17, 19, 23…

SRM 548 DIV2 Hard: KingdomAndPassword

解法 oldPasswordが新しいパスワードにもなる場合がコーナーケース。 そうでない場合を考える。 先頭からi桁が等しいとする。つまり、新しいパスワードがoldPasswordと異なる最上位の桁をi(0-indexed)とする。この桁の値によって新しいパスワードがoldPasswo…

SRM DIV2 Hard: OrderOfTheHats

解法 トポロジカルソートの要領で以下のビットDPを解く。 dp[mask] = トポロジカルソート済みの頂点の集合がmaskであるときの削除した辺の個数の最小値 N<=20 → ビットDP DAG →トポロジカルソート

AtCoder AGC010 C - Cleaning

エディトリアルの判定 L>=min(max(c[i]), Σ(c[i])/2)がよくわからなかった。 以下、条件判定の考察のみ変数名はエディトリアルのものを踏襲 葉ではない頂点をv、m = max(c[i])とする。 T >= 0 (1)は自明。 A[v]が最大になるのは子供=>v=>親 を含む経路がすべ…

AtCoder AGC010 A - Addition

解法 偶奇だけみればいい。 操作は以下の2種類だけ。 (偶数)+(偶数) = (偶数) (奇数)+(奇数) = (偶数) 奇数が奇数個あるとき、奇数同士を全部くっつけていっても、最後に奇数が1個に対して偶数が1個以上となり、詰む。 そうでないとき、つまり奇数が偶数個な…

AtCoder AGC010 B - Boxes

解法 N=1のときは明らかにYES 以下、N>=2とする。 1回の操作で合計 b=1+2+...+N = N*(N+1)/2 足される。なので Σ(A[i])がbで割り切れないときはNOとする。 操作回数をtとすると t = Σ(A[i])/b ここで数列cを以下のように定める c[i] = b[(i+1) mod n] - b[i]…