2016-01-07
SRM 656
https://competitiveprogramming.info/topcoder/srm/round/16416/div/1
Div1 Easy (250)
問題
- N枚のパンケーキがある
- それぞれの大きさは1からNで、それぞれのおいしさが与えられる
- 1枚ずつランダムに選んで積んでいく
- ただし、一つ前に積んだものより大きければ、それを積まないで終了
- 詰まれたパンケーキのおいしさの合計の期待値を求める
方針
- 座るだけ
- (終了後)
- こじはらさんのブログを参考に
- 全体の並べ方はN!通り
- 並べ替えの結果、i番目(0-index)のパンケーキがj番目(0-index)にあるとき、それがおいしさにカウントされる(終了していないとき)は、前半がカウント条件を満たしていたときで、その総数は、i番目より大きなg個(N-i-1個)のパンケーキからj個取った場合の数。g!÷((g-j)!×j!)通り。
- 後半についてはカウント条件に関わらず全て数える(後半の並びかた関わらず、i番目のパンケーキのおいしさをカウントするかどうかだけ気にすればよい)
- 後半のr個(N-j-1個)の並べ方はr!通り
- すなわちi番目のパンケーキのおいしさの総和はg!÷((g-j)!×j!)×r!×おいしさ
- 期待値は全体の並べ方はN!なので最後にそれで割る
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_656/RandomPancakeStack.cpp
結果
--- -1 -25pt 517th/531 rating 1543 -> 1384 (-159)
考察不足。
2016-01-05
TCO15 Algorithm Round 1A
https://competitiveprogramming.info/topcoder/srm/round/16432/div/1
Easy (250)
問題
- 2つの数値について、10進数表記にしたとき共通する数字の数を類似性とする
- L以上R以下の異なる2つの数の類似性の最大値を求める
方針
- 各数値について0-9の有無をbit0-9に対応させて持っておき、全探索で間に合う
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/tco_2015/Similars.cpp
Medium (500)
問題
- N個の場所とN個のトークンがある
- それぞれの場所には矢印がついていて、いずれかの場所を指している
- 初期配置として0個以上のトークンを異なる場所に置く
- 各ターンでは、各場所のトークンを、矢印で指示された先に移動する
- トークンが同じ場所に置かれるとゲームオーバー
- ゲームオーバーにならないトークンの置き方の総数を求める
方針
- 全てのトークンを置いてKターンシミュレーションしてみる
- 場所が重なるものがあったら同じグループと見なす
- 同じグループは、どれか一つだけ置くか、または、置かない
- なので総数は(各グループの個数+1)の積
- Kが大きいがmin(N,K)ターンで良い
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/tco_2015/Autogame.cpp
結果
oo- +1
153.34 + 309.42 + 50 = 512.76pt 163rd/1195 rating 1459 -> 1543 (+84)
毎度TCOご祝儀。
参加者が少なくて1pt以上の人は全員通過。
2016-01-04
Google Code Jam Qualification Round 2015
https://code.google.com/codejam/contest/6224486/dashboard
A. Standing Ovation
問題
- 友人のオペラの公演で観客全員をスタンディングオベーション状態にしたい
- ある観客がSO状態となるためにはSO状態の観客がSi人以上必要である
- 観客全員をSO状態にするためのサクラの人数を求める
方針
- Sが小さいほうから数えていき、S人未満ならサクラを追加する
- https://github.com/firewood/topcoder/blob/master/gcj_2015/QR_A.py
B. Infinite House of Pancakes
問題
- D個の皿に何個かのパンケーキが配られる
- 毎秒、全ての皿のパンケーキを1つずつ食べるか、または、どれかの皿のパンケーキをどこか(新しい空の皿でもよい)に移動できる
- 全てのパンケーキを消費する最小秒数を求める
方針
- 分割するなら最初が一番いいので、最初に必要な分割を行い、そのあとほったらかしにする
- X個より多ければ分割、でX=1～1000で試す
- https://github.com/firewood/topcoder/blob/master/gcj_2015/QR_B.py
C. Dijkstra
問題
- i、j、kからなる基本文字列Lと、その繰り返し回数Xが与えられる
- 隣接する2文字は置換ルールで1文字に短縮できる
- 3文字の文字列ijkに短縮可能かどうか求める
方針
- 数値に変換して先頭からシミュレーション
- 先頭がiになるまで次の文字と短縮していく
- 文字がjになるまで次の文字と短縮していく
- 文字がkになるまで次の文字と短縮していく
- 残りの文字が空か、すべて短縮したら1(同じ)になるかどうかを調べる
- 同じ文字列を4回かけると1になるので、4の倍数分はカットする
- https://github.com/firewood/topcoder/blob/master/gcj_2015/QR_C.py
結果
A、B、C-smallで49点。例年より通過枠が厳し目か。
Cで末端の処理をX % 16としていたが、これだと残りがちょうど16回の場合に誤判定するので、(X > 4のとき)4 + (X % 4)のようにしないといけなかった。
2016-01-03
SRM 655
greedy |
https://competitiveprogramming.info/topcoder/srm/round/16415/div/1
https://competitiveprogramming.info/topcoder/srm/round/16415/div/2
Div1 Easy (250)
問題
- Wで塗りつぶされた升目がある
- K×Kの大きさ単位でBまたはWで塗りつぶす
- 最終状態が与えられる
- 初期状態から最終状態にできるかどうかを求める
方針
- 提出できず
- 貪欲に全体をスキャン
- Wと?、またはBと?のみからなるエリアがあったらOK
- OKなエリアを?で塗る
- OKなエリアがなくなるまで調べる
- Bが一つも残らなければOK
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_655/BichromePainting.cpp
結果
--- 0pts 248th/564 rating 1504 -> 1459 (-45)
「どちらでもよい状態」を思いつけなかった。
2016-01-02
UTPC 2014
http://utpc2014.contest.atcoder.jp/
チーム抹茶として3人で参加した。
チームメイトが大変優秀で総合20位だった。
個人としてはE解いて、KとLの部分点とった。
このコンテスト、毎回難しいけど問題文も問題内容もユーモラスなのですばらしい。