2016-10-04

CodeForces #375_Div2 : C. Polycarp at the Radio

CodeForces

問題

大きさ $n$ の整数配列 $a$ が与えられる。
「 $a_i$ の値を任意の値に変更することができる」という条件下で、
$1$ から $m$ $( m \leqq n)$ それぞれの値の出現数の最小値を最大化させたい。

最大化させた出現数の最小値 / この時の最小変更回数 / 変更後の配列を求めよ。

解法

まず第一に配列の大きさ $n$ 、最大化させたい値の範囲 $m$ から、
最大化させた出現数は $\lfloor\frac{n}{m}\rfloor$ に固定される。 ( $M = \lfloor\frac{n}{m}\rfloor$ とおく)

( $m$ を超える値の数の総数) + ( $1$ から $m$ の中で出現数が $M$ を超えた差分) を使って
$1$ 〜 $m$ の内、出現数が $M$ に達していないものを補填してあげれば良い。

$1$ 〜 $m$ の出現数を配列 $c$ 、
( $m$ を超える値の数の総数) を $f[m$ ]、
( $1$ から $m$ の中で出現数が $M$ を超えた差分) を $f[0$ ]〜 $f[m-1$ ] に入れ管理している。

計算量は $O(n+m)$

ソース

感想

やるだけの問題なのに落としたのが勿体なさすぎる・・

2016-04-30

TopCoder SRM689_Div2 : ColorfulGardenHard

TopCoder

TopCoder Statistics - Problem Statement

問題

花の種類を表す文字列とある位置における配置禁止の色の二つの情報が与えられる。
花は色を持ちアルファベットで表現される。

与えられた花を以下の条件に従い並び替えた時、そのパターンの総数を求めよ。 (重複は除く)
・同じ色の花が隣合わない
・位置iで禁止されている色を置いてはいけない

解放

文字列の長さが高々15のため、bitDPを利用できる。(制約からすぐに気付きたい)
重複を避けるために各bitマスクの状態で、次に追加する特定の色が2回以上選択されないように注意する。

計算量は $O(2^n n^2)$ となる。
・ bitマスクの状態数 $2^n$ 通り
・最後に選択した色 $n$ 通り
・各状態に対して、最大 $n$ 通りの次に選ぶ花の選択技

コード

gist.github.com

2016-04-04

ARC #050：B. 花束

AtCoder

問題

B: 花束 - AtCoder Regular Contest 050 | AtCoder

解法

片方の色の花束をいくつ作るか決めた時に、作ることのできる花束の総数が凸関数になる。
よって片方の色の花をいくつ作るかについて三分探索をすればよい。

三分探索については以下の記事が参考になります。
・三分探索と黄金分割探索 - naoya_t@hatenablog

解説では二分探索による解法が紹介されています。
(こちらは理解できていない・・)

ソース

2016-04-03

CodeForces #309_Div1 : A. Kyoya and Colored Balls

CodeForces

http://codeforces.com/contest/553/problem/A

問題

1〜kまでナンバリングされたボールがそれぞれ $c_i$ 個与えらえる。
これらのボールを全て並べたとき、color(i)の中で右端に存在するボールよりも右側に
color(1)〜color(i-1)が存在しないような並べ方が何通りあるか求めよ。

解法

ナンバーの小さい順にボールを配置していく。
color(i)を配置する際、最も右側に存在するcolor(i)よりも右側にcolor(1)〜color(i-1)が
存在してはいけないので、まずcolor(i)のうち1つを右端に配置する。
残りの $c_i -1$ 個のボールを、既に配置されているボールの隙間に重複を許して配置すれば良い。
例えば以下の例で、 $c_3=3$ を追加したい場合 $_5H_2$ を計算する。 f:id:suigingin:20160404011004p:plain

重複組み合わせについては hosさんのスライドが分かりやすいと思う。
ボールの総数が1000を超えないためコンビネーションの計算にパスカルの三角形を使用できる。

コード

2016-02-15

CodeForces #8VCVentureCup : D. Jerry's Protest

CodeForces

Problem - D - Codeforces

問題

ツボの中に重複のない番号の書かれたボールがn個入っている。
Andrewと Jerryはこのツボの中から同時にボールを一つだけ無作為に選びとり、
番号の大きい方が勝者となる。(選んだボールはツボにまた戻す)

このゲームを3回連続で行った時、
最初の2回は Andrewが勝ち最後の1回は Jerryが勝ったとする。
3回のゲームを通して Jerryの出た番号の和が Andrewより大きくなる確率を求めよ。

解法

d、cを以下のように定義し
勝者が敗者にi枚差・i枚以上差をつけて勝つパターン数を事前に求める。
cはdの累積和から得ることができる。

d[i] := 1回の勝負で勝者が敗者にi枚差をつけて勝つパターン数
c[i] := 1回の勝負で勝者が敗者にi枚以上差をつけて勝つパターン数

d,cより以下の場合の数を、差の最大値(5000)の2重ループで求める。
1戦目. Andrewがi枚差をつけてJerryに勝った
2戦目. Andrewがj枚差をつけてJerryに勝った
3戦目. Jerryがi+j+1枚以上差をつけてAndrewに勝った
d[i] * d[j] * c[i+j+1]