2015-01-02
SRM 638
Div1 Easy (300) ShadowSculpture
問題
- XY平面、YZ平面、ZX平面の影が与えられる
- Yが存在する部分、Nが存在しない部分
- 連続する物体で条件を満たすものがあるかどうかを求める
方針
- Nの部分を削った
- Failed System Test
- DFSで条件を満たす部分を伸ばしていき、与えられた影と同じになるか調べる
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_638/ShadowSculpture.cpp
結果
x-- +1 50pts 135th/400 rating 1467 -> 1522 (+55)
変数xyの添え字は変数名通り[x][y]なのだが図に書いたりすると混乱した。
3Dプリンタっぽい。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150102
2015-01-01
SRM 637
Div1 Easy (250) GreaterGame
問題
- 1から2×Nまでの数が書かれた2×N枚のカードがある
- 2人のプレーヤーにそれぞれN枚のカードを配る
- それぞれのプレーヤーの手札の配列が与えられる
- 相手は順番に出す手札と、順番が決まっていない手札がある
- 出した数値が大きいほうが1点得る
- 一人目のプレーヤーの点数の期待値を求める
方針
- 相手の手のうち、確定しているものについて、小さい順に処理する
- 勝てるものには最小限で勝てるものを、負けるものには手持ちの最小値をぶつける
- 不明な部分については、出さなかったカードについて単純な期待値を求める
- Failed System Test
- 負けるものの処理が抜けてた
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_637/GreaterGame.cpp
Div1 Medium (500) PathGame
問題
- 縦2マスの通路がある
- 升目は白か黒で、白い升目だけ通れる
- 2人で交互に升目を黒く塗る
- ただし左端から右端まで通れる状態を維持する必要がある
- 塗れないほうが負け
- 最善手のときの勝者を求める
方針
- Grundy数でも解ける
- cafelierさんのを写経
- 塗れるブロック毎に分割して、それぞれのGrundy数を求める
- 塗り状態は、両方白、上だけ黒、下だけ黒のいずれか
- 連続する両方白の部分がひとつのブロック
- それぞれのブロックについて、左端の塗り状態L + 長さNの白い部分 + 右端の状態R、のGrundy数を求める。Nの全範囲について、塗れる部分のGrundy数の集合を求める
- N=1のGrundy数は、両方の上か両方の下が空いているときは1、それ以外は0
- 塗れる部分が分割されるときは、それぞれの部分のGrundy数のXORを取る
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_637/PathGame.cpp
結果
x-- 0pts 486th/688 rating 1564 -> 1467 (-97)
GCJ 2014予選Dの問題に似ている。実装中に方針が適当になってしまった。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150101
2014-11-29
SRM 636
Div1 Easy (250)
問題
- チョコレートを9分割する
- それぞれの部分の合計値がその部分の品質になる
- もっとも品質が低い部分の最高値を求める
方針
- 分割する位置は縦2つ、横2つなので全探索する
- 全部再計算すると重そうなので、(0,0)から全ての点(x,y)の合計を求めておく
- (a,b)から(c,d)の合計は、(c,d)の合計から、(a-1,d),(c,b-1)の合計を引いて(a-1,b-1)の合計を足すので、表で作っておく
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_636/ChocolateDividingEasy.cpp
結果
o-- 104.40pts 413rd/532 rating 1649 -> 1564 (-85)
やややるだけゲー。遅い
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20141129
2014-11-01
SRM 635
Div1 Easy (250) SimilarRatingGraph
問題
- 日付とレーティングの配列が与えられる
- 変動のグラフが同じ形になっている部分の最大の長さを求める
方針
- 区間(a,a+k)と区間(b,b+k)が一致するかどうか全探索
- それぞれの区間で傾きが一緒で、かつ、長さの比が最初の日の長さの比と同じであること
- Failed System Test
- 比の計算が間違ってた
- kusanoさんのを写経して整理
- 差分だけ最初に求めておいてもよい
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_635/SimilarRatingGraph.cpp
結果
x-- 0pt 222nd/602 rating 1705 -> 1649 (-56)
部屋の全員easyを落とすという珍しい回だった。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20141101