SRM712 Div1 Easy LR

整数列s, tが与えられる。sの整数列について、次の操作LまたはRを施す。

1. 操作L：{..., a[i], a[i+1], a[i+2], ...} -> {..., a[i] + a[i-1], a[i+1] + a[i], a[i+2]+a[i+1], ...}
2. 操作R：{..., a[i], a[i+1], a[i+2], ...} -> {..., a[i] + a[i+1], a[i+1] + a[i+2], a[i+2]+a[i+3], ...}

 LRの操作を100回以内で繰り返して数列tに変換できるならば、その操作列を求めよ。変換できない場合はNo solutionを返せ。

操作Lと操作Rは可換である。そのためLとRの数がそれぞれ決まればよい。あとは愚直に操作をしてみて、一致したらその数だけLとRを並べて返す。Lの数とRの数を決めたら毎回その分だけ操作をするとTLEするので、ちゃんとDPっぽいことをする。また、数列の中の数値がLong maxを超えたら0以下になるので、最大値になる前に失敗と判定する。

SRM714 Div1 Easy Parenthesis Removal

対応が正規の括弧列の文字列与えられる。この文字列に対し以下の操作を行う。

1. 左端の開括弧を削除
2. 除去後も括弧列が正規であるような任意の閉括弧を1個削除する

この操作を繰り返し行なった後、空文字になるパターンは何通りあるか。

括弧列の問題は後ろから考える。(以前AtCoderでも似たような問題があったのだがまたやらかしてしまった気がする)

後ろから閉じ括弧の深さでレベルをインクリメントしていき、開き括弧に当たった時点でその消し方は{現在のレベル}通りある。これが何故前から考えると駄目かというと、括弧を削除した結果、その後続にある括弧についてペアになれないものが存在することがあるからである。その点後ろから見た場合は必ず今まで見た閉じ括弧のいずれかと開括弧が組み合わせになることができる。

その為、初期値をret=1として、開括弧に当たるごとにレベルをかけていけばよい。modを忘れないこと。O(N)。

Rでガチャ推定

最近のガチャは確率pで当たりが出ます、というだけじゃなく天井と言うものが設定されてることがあります。これは、例えばガチャにある一定の数nが設定され、その中で必ず1枚は当たりがある、といったものです。とりあえずこれをモデル化してみます。

流石に天井付きガチャで当たりを引く確率なんてのはデフォルトライブラリにはないので適当に関数を書きます。

g <- function(m, n) {
arr <- c()
last <- 0
for (k in n) {
if (m <= k) {
arr <- c(arr, 0)
} else {
ret <- 1.0
for (i in 0:(k-2)) {
ret <- ret * (m - 1 - i) / (m - i)
}
ret <- ret * 1 / (m - (k - 1))
arr <- c(arr, ret)
last <- ret
}
}
return (arr)
}

一方で、通常の天井のないガチャは簡単です。二項分布っぽいですが、若干違うのでこっちも関数を自作します。

f <- function(p, n) { return (p * (1-p)^n) }

 で、書きます。

plot(1:1000, cumsum(f(1/200, 1:1000)), type="l", xlim=c(0, 1000), ylim=c(0, 1), lty=2, ylab="")
par(new=T)
plot(1:1000, cumsum(g(200, 1:1000)), type="l", xlim=c(0, 1000), ylim=c(0, 1), ylab="p")

 点線が天井なしガチャ、実線が天井ありガチャで、n=200(天井なしの場合は1/n=0.005の確率で当たる)として、累積で当たった人の割合をplotしてあります。100回あたりから徐々に差がではじめ、ワースト10％の運が悪い人では6倍ぐらいの投資金額の差が出ています。というわけで自分がとても運が悪いという認識のある人は天井ありガチャのあるゲームをやりましょう。

AtCoder Grand Contest 014 D - Black and White Tree

agc014.contest.atcoder.jp

N頂点からなる木について、交互に白黒白と色を塗っていくゲームをする。最後に1回だけ、黒が隣接している白の点を一斉に黒にする。この時白が残っていれば白の勝ちである。最適に行動したときにどちらが勝つか求めよ。

木の葉が2個以上ある節が存在すれば勝ち確定である(※)。そうでない時は、頂点が2n個の直線状に並んでいるところについて、葉の一歩手前に白を置くと、黒は葉に置かないと「-○-○」(右端が葉)のような形を作られて白が勝ち確定であるので、葉に置くという行動が最適解になる。「-○-●」よってこのような形になったあと、この部分は無視してよく、結果として2n個の直線状に並んでいるところはどんどん頂点を削除していこう。そういう操作を続けていった結果、(※)の状態が現れた、もしくは1点のみになった時点で白の勝ち、それ以外は黒の勝ちである。

実装としてはdfsで直線上のところは頂点の偶奇をつけておき、そうでないところは子が奇数の点をカウントし、2個以上あったら白の勝ち確定、それ以外は奇数の数を親ノードに返す、みたいなことをする。O(N)。

Codeforces 411 Div.1C Ice cream coloring

codeforces.com

ツリーTが与えられて、Tの各頂点v[i]にアイスクリームの集合s[i]が与えられる。同一のアイスが含まれる頂点だけからなる部分グラフは連結である。この時、新しいアイスの集合を頂点とするグラフGを、Tのある頂点v[i]があって、アイスaとアイスbがs[i]に含まれるならば、aとbの間に無向エッジを貼る。この時、Gの最小Coloringを構成せよ。

Gにおいて、Tの各頂点に対応するs[i]に含まれる元ついてはクリークとなる。さらに、部分グラフが連結であるという条件から、二つのクリーク同士を接続する頂点集合もクリークとなる(つまり二つの独立したクリークで接続されていることはない)。なのでクリークごとに貪欲に色を決めていけば良い。

つまり、dfsで各クリークを見ていったとして、その時点で着色可能であった色が、別の頂点の探索中で棄却されることはない。

そのためTのある頂点からdfsする。今見ている頂点がGのクリークに対応する。Colorを数字で表した時、既に着色済みの頂点を除いて小さい方から貪欲に色をつけていく。O(V)。

AtCoder Regular Contest 073 E: Ball Coloring

arc073.contest.atcoder.jp

(x[i], y[i]) (1≦i≦N) が与えられる。任意の点について、xとyを交換できるとき、これらの点をすべて含み、辺がx軸またはy軸に平行な長方形の面積の最小値を求めよ。

まずすべての点についてx[i]≦y[i]となるようにしておく。この時をminX, maxYとするとき、次の2パターンが存在する。

1. max(y[i]) - min(x[i]) の長さの辺がある
2. 角の座標が(min(x[i]), max(y[i]))となる

2の場合はもう一つの角の座標が(max(x[i]), min(y[i])) なので、これで面積が出る。

1の場合は残りの辺の最大の高さh=max(x[i])として、x[i]を小さい方から見ていき、h - x[i] をもう一方の辺の長さとして面積を計算する。hは今見ているx[i]に対応するy[i]とのmaxを取り更新、次の辺について調べる。x[i]がmin(y[i])を超えない範囲で調べた後、min(y[i])が角のy座標になるパターンも調べてそれぞれの最小値を求める。O(N)。

Google Code Jam 2017 Round 1-C A

Dashboard - Round 1C 2017 - Google Code Jam

円柱型のパンケーキをN枚の中からK枚選択して、大きい順に重ねたとき底面を除いた表面積を最大化せよという問題。

まず側面を除いた面積は最大の半径を持つパンケーキの上面の面積に等しい。なので、パンケーキを側面の面積順でソートすると、大きい順にからK-1枚は常に選ぶ必要がある。残りの自由度はパンケーキ1枚なので、総当りする。

最初に選んだパンケーキK-1枚の中の最大の半径を取得しておき、総当たりのパンケーキの半径とmaxをとるとそれが上面の円の半径。この半径と、今見ているパンケーキの側面積と、元々選んだK-1枚の側面の面積が今見ているセットの総表面積になる。O(N)。