主食は米

主に競プロ備忘録

AtCoder Grand Contest 028 B - Removing Blocks (600)

解法

解説の1つの解釈として.

解説/解説放送と同じように, iをremoveした時に A_j が足されるかどうかを考える.
ただし,確率ではなくそのような順列の場合の数を数え上げることにする.

事前準備として,n個の順列のうちで
そのうちの要素 x,y (x!=y) に関して x<y が成り立っているものは n!/2 になる.
これをもう少し考えると x_1 < .. < x_k+1 のk個の不等号があるものは n!/(k+1)! になることがわかる.
(n個の場所からx_iの場所k+1個を選ぶ) * (残りのN-k-1個は自由に並べる)
= nC(k+1) * (n-k-1)! = n!/(k+1)!
と考えても良い.

これを使って,上の順列が何通りあるかを数える.
簡単のため, i < j と仮定して
x_0 = i, x_1, ... , x_k, x(k+1) = j とする. (k = j-i-1)
ここで, 求めたい順列を束縛する不等式は i の後にx_1, x_2,.., x
(k+1) が出るという条件のみを満たしていれば良いことを考えると
x_0 < ( x_1, x_2, .. , x(k+1) を好きに並べて不等号で繋いだもの ) であることがわかる.
これは, x_1,...,x
(k+1) の順番が決まればk+1個の不等号が繋がっているので N!/(k+2)! 個ずつある.
このいずれかを満たす順列(つまり順列の和集合)を求めればよく,これらは全て排反であるため
合計で n!/(k+2)! * (k+1)! = n!/(k+2) = n!/(j-i+1) 個あることがわかる.

ここからは解説と一緒で,
A_j * sum_i{ n!/abs(j-i+1) } のjに関する和が答えになる.
調和級数を事前に計算しておけばO(N)

メモ

確率として典型処理するようにしたほうがいい気もする..

コード

「みんなのプロコン」2017 本選 A - YahooYahooYahoo

解法

典型的な文字列AとBの編集距離を求める問題において, B = "yahoo" と固定したバージョンになる.
(
正規表現における閉包)

i=1,2,.. として 部分文字列S[0,i) を最終的な状態 "yahoo"* の前半と一致させることにしよう.
それまでの最小の編集距離に注目する上では, 末尾が "yahoo" の何番目になっているかということにだけ注目すれば良い.
よって, dp[i][j] := (S[0,i) を 末尾が"yahoo"のj番目(0-index)になるようにした,最小の編集距離 ) とする.

すると, 遷移は dp[i][j] からs[i] をそのまま足して 1<=k<=5 回末尾に insert, または末尾を 1回deleate したパターンを考えればわかる.
1<=k<=5 回でなく1回だけinsertすると考えて dp[i][j] から dp[i][j+1] に遷移させることもできるが, その場合解説にあるように2周しないといけない.
初期値と答えに注意.

コード

DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 C - ロト2

解法

a_i は K と共通の因数しか注目しなくて良いことがわかるので, a_i = gcd(a_i, K) とみなして良い.
Kの約数は高々 2sqrt(K) しかないので(エラトステネスの篩をやっていくとわかる), a_i として現れる数は O(sqrt(K)) しかない.

定跡としてこの分布をとると,(つまり cnt[a] := aの現れる回数 とする)
全ての a<=b (a,bはcntのkey) についての全探索がO(K)となって間に合う.

ただし a==bのときは abがKの倍数になるならば cnt[a](cnt[a]-1) を足すことに注意(自分自身とは組にできないため)

コード

square869120Contest #3 D - お土産購入計画2 / Souvenirs (600)

解法

  • 最短路なので2人とも(0,+1) or (+1,0) で進む
  • 1人だったら? -> DPで(x,y)または(何回進んだか,x)をキーとして持ってやればできる
  • なぜなら(x,y)で最大のお土産を持つためには(x-1,y)or(x,y-1)で最大のお土産を持っている必要があるため
  • 2人でも2人の座標を持ってやればできそう
  • (x,y)両方とも持つ必要はなく, (ターン数,1人目のx,2人目のx) を持てばOK
  • 漸化式は
  • 2人とも同じとこにいく(nx,ny)=>+a[nx][ny]
  • 2人が別のとこにいく(nx1,ny1),(nx2,ny2) => +a[nx1][ny1]+a[nx2][ny2] でOK

メモ

1人ならDPできるねーからマップを2つに分けて各々DPするか?みたいな方向に行ってしまってできなかった.
どういう状態を持つべきか,とかの訓練が足りなさそう

コード

AGC 026 C - String Coloring

解法

  • 制約から半分全列挙をエスパーする
  • 2Nとあるので半分と後半に分けてみる
  • 前半の赤色がa文字とすると,前半の青色はN-a,後半の青色はaになる
  • 前半の赤色=reverse(後半の青色) かつ 前半の青色=reverse(後半の赤色)である必要がある
  • どちらも全列挙してkeyを(赤色の文字列,青色の文字列),valueを何個できるかで持っておけばOK

メモ

これ思いつかなかったの厳しい

コード

AGC 026 B - rng_10s

解法

  • 明らかに,解説で除いている3ケースはわかる.
  • そうでないとき, 個数をy個とすると無限に買い続けられるときは y = C の周りを振動する
  • 無限ループするので,yが周期をもつ-> C+1 <= y <= C+B の値を全て取りうる? .. そうであればC+1-B>=0を判定すればOK
  • 実際上のようなケースは gcd(B,D)=1のときに限られることがわかる
  • ex. (A,B,C,D) = (7,3,1,6) は 7,4,1,7,4,1,..
  • g = gcd(B,D) のとき A+kg であってCより大な最小のものがCより大きい最小な個数っぽい
  • このようなkは k=(A-C-1)/g で求められるのでこれで A-kg-B>=0 であればOK

以上で1回のクエリがO(1)で解けた.
わざわざクエリ方式にしたのは嘘解法が無限に作れそうだからっぽい.

メモ

解けたが,解説のような綺麗な解法はできなかった.
以下のことを意識すると良いかも?

  • 2回定数加算の操作があるときは1つのmodをとってみる(操作が1回になるため)

コード

codeFlyer 2018 final D - 数列 XOR(600)

解法

考察

  • XOR swapによりswapが可能( a ^= b, b ^= a )
  • これによってa_i, a_j (i!=j) で操作ができる
  • あるbitだけ立っている要素があればそれを使ってそのbitを自由に立たせることが可能
  • そのような要素は {1101, 1001} のような1bitだけ異なる数があっても作ることができる
  • それが作れれば {a} と {b} でその要素ができるか?という基準で判定さえすればOK
  • しかし上の {1101, 1001} の 1001のように2bitが必ず同じように現れることもありえる
  • 全ての組み合わせは264で判定するのは無理だし..?

上の操作が行列の行基本変形に酷似していることに頑張って気付こう.
結果的にいえば, 1bit目が立っているものを調べてそのような要素(a_rank)がなければそのbitは無視し,あるならばその他の要素(a_i)をその要素とのxor (a_i ^= a_rank)にして消していくというのをやれば良い.
これはxorをmod2での加算と見て,bit方向を列と見たときのGaussの消去法に他ならない.
またxorは逆操作が可能なので {a} -> {b} という操作が可能か?という問題でなく, {a}, {b} を共に共通の標準形にできるか?という問題に言い換えることができる.
よって {a}, {b} に上の操作をして,等しくなればYes,そうでなければNoになる.

メモ

  • 逆操作が可能なら共通要素に変換できるか?という問題になる
  • bitを列にして行列で捉える味方

コード