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

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2383 Rabbit Game Playing

とある勉強会に参加したので,そこで解いた問題の解説を暫くやっていこうと思います.

問題概要

問題文:Rabbit Game Playing | Aizu Online Judge

N個のゲームがあります.各ゲームには1以上10^5以下の難易度がつけられている.
N個のゲームを順に全てプレイしたいが,直前に行ったゲームの難易度-T未満のゲームはプレイすることができない.
ゲームのプレイする順番は何通り考えられるか.

解法のようなもの

入力で与えられるゲームは順番を変えても答えに影響がないので,とりあえず難易度順にソートしてみる.
空の数列に,難易度の低い順に数字を追加していく方針で考えてみる.

数字の重複があると面倒くさいので,はじめは重複無しの場合で考える.
今見ている数字をKとすると,数列にはK未満の数字しか含まれていないため,数列の一番後ろにKを追加することができる.
他の部分に挿入できないかを考えると,K-T以上の数字の直前に挿入しても問題ない.

例えばT=4で数列が
1 ,3 ,5 ,7
のときに8を5の直前に挿入する
1, 3, 8, 5 ,7
この前後の数列はともに問題の条件を満たしている.
ここで,次に9を5の直前に挿入しても,
1 ,3 ,8 ,9 ,5 ,7となり関係性が壊れない.

Kを挿入できる箇所は常にK-T以上の数字の直前と一番後ろなので,(K-T以上の数字の個数+1)をかけていったものが答えになる.

次に数字が重複している場合について考える.
同じ数字をいっぺんに挿入することを考え,
数字KS個,K-T以上の数字が数列にR個含まれているとすると,
S+1個の挿入候補にR個の区別するものを挿入することになる.(+1は一番後ろに追加する分)
これは,S個の仕切りと区別するR個のものを並べる組み合わせの問題と一緒になるので,
この組み合わせの数は\frac{(S+R)!}{(S)!}となるので,これを掛け合わせると答えが出てくる.

ソースコード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1882232#1
割と考え方がyukicoderのペガサスの挿入DPに似ていて,
数列に挿入していくという考え方は割と大事なのかもしれないと思った.