■時間
40分ぐらいorz
■問題
perfect binary treeで表される街と道路のネットワークがある。持っている車を全て合わせて、全部の街にちょうど１回ずつしか通らないように走らせたい時、最小の車の台数はなにか。
■試した解き方
・greedyに解いた。なんとなく最小の数ってのは、一つ車を端から端まで走らせて（下図の「0番目の車」）、残った木をsubtreeとしてそれぞれの最小車数を足していけばいいんじゃないかと考えた。（これが最小となる証明は出来てない）
N(n)= 1+ 2*Σ[i=0~n-2].N(i)
となる。
nがでっかい（最大1000000）なので、全てのN(n)を覚えるのは現実的ではない。
なので漸化式に直す：
N(n)=N(n-1)+2*N(N-2)
N(0)=N(1)=1で始めて、任意のnまで計算する。
static final int MOD=1000000007;
public int theMinCars(int treeHeight) {
long pprev=1, prev=1;
for(int n=2;n<=treeHeight;n++){
long current= (prev+2*pprev)%MOD;
pprev=prev;
prev=current;
}
return (int)prev;
}
■結果
無事System Test通過。
■反省
greedyな解き方を思いつくのに時間かかりすぎた。
漸化式に直すのにも時間かかった。
こんな問題は１０分ぐらいで解きたい。
Medium "LISNumber"
■時間
Not Submitted。その後５時間ぐらいかけて解いた。
■問題
ある数列を渡された時に、その数列を「単調増加する数列」の最も短い列として表したときの列数をLISNumberと定義する。
数字が沢山渡された時、入力されたLISNumberとなる並び替え方の組み合わせ数を返せ。
■試した解き方
順番に小さい数字から足していった時に各LISNumberのパターン数を考えていく。
便宜的に、i番目の数字までを考慮した際のLISNumber=nのパターン数をN(i,k)と呼ぶ。
例えば入力が
0×3
1×2
2×11
3×5
4×7
でLISNumberが20の場合・・・
最初の「0」しか考えないとすると：
LISNumber=3となる数列は1パターン（0_0_0）
それ以外のLISNumberは0パターン存在する。
次に「0」「1」を考える時、
LISNumber<=2の数列を作る方法は存在しない。
LISNumber=3は、「0」の時のLISNumber=3の数列の中の数列の後ろに足していけば作れる。
（例えば0_0_0→01_0_01）
３カ所に2つの数字を置きたいので、N(1,3)= 3C2 × N(0,3) 。
LISNumber=4,5は、「0」の時のLISNumber=3の数列の頭か、各数列の中を分割するような位置に置いていけば作れる。
例えばLISNumber=4は1_01_0_0、LISNumber=5は1_1_0_0_0など。
LISNumber=4の場合は一つを既存の数列に結合するように置き、もう一つを新規の数列になるように置く必要があるので、
N(1,4)= 3C1 × 1S1 × N(0,3)
（where: nSkは「n個の箱にk個のボールを置く方法」。パスカル三角形的なので計算できる。）
このように一つずつ数字を足していき、最後N(|array|,n)を返せばいい。
■結果
OK（ただしSRM終了後）
全体結果
レーティング： 1521→1458（-63）
Easyに時間かけすぎたせいでレーティングが落ちてしまった。
また青に逆戻り。
コメント
・Easyは安定して解けるようにはなったが、スピード遅すぎる。
・Mediumは珍しく本番中に解き方が分かったので、少し満足。
・部屋で誰にもchallengeされなかったのにSystem Failしていた人がいた。こういうのはchallengeの敗北なのできっちり倒していきたい。
0 件のコメント:
コメントを投稿