2016-06-14
SRM 677
https://competitiveprogramming.info/topcoder/srm/round/16627/div/1
Div1 Easy (300) DoubleOrOneEasy
問題
- 数aとbが与えられる
- 一回の操作で+1または2倍にできる
- 数aをnewAに、数bをnewBにするための最小操作回数を求める
方針
- (newB-newA)÷(b-a)をもとに、2倍の操作を何回やったか求めて、割っていく
- Challenge Succeeded
- (終了後)
- a <= bとなるように交換する
- newAが奇数でaが偶数なら-1、両方偶数でnewA/2-a <= newB/2-bが成り立つなら半分にする
- 残りは(newA-a)だけ減らす
- 一致すればOK
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_677/DoubleOrOneEasy.cpp
結果
x-- +1 50pt 163rd/420 rating 1299 -> 1380 (+81)
a==bで死んだけど1撃墜。
2015年はかろうじてdiv1を維持できた。
2016-05-28
SRM 676
https://competitiveprogramming.info/topcoder/srm/round/16626/div/1
Div1 Easy (250) WaterTank
問題
- Cリットル入るタンクがある
- N個の連続する区間があり、区間ごとに水量が変わる
- 区間iの長さはt[i]秒で、毎秒x[i]リットルの水がタンクに入る
- タンクがあふれないようにするための出力Rリットル/秒の最小値を求める
方針
- 二分探索
- 各区間で足してみて、あふれない下限を求める
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_676/WaterTank.cpp
Div1 Medium (450) BoardEscape
問題
- r×cの升目がある
- 出口EとトークンTが置かれている
- トークンは初期値kを持っていて、上下左右いずれかに動かすと1減る
- 出口と重なるか、値がゼロになるとトークンは消滅する
- 2人で交互に動かすとき、トークンを動かせなくなったほうが負け
- 両者が最適な戦略を取るとき、勝者を求める
方針
- grundy数 + DFS
- Failed System Test
- Tの残りの数を状態に持つ必要がある
- memo[行][列][Tの残数]でメモ化
- ただしTが4を超えるときは4つごとに同じ状態なので、4 + (T MOD 4)にする
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_676/BoardEscape.cpp
結果
ox- 173.83pt 258th/407 rating 1268 -> 1299 (+31)
yukicoderのおかげで久しぶりにmedium提出できたが、状態の持ち方が悪くて死んだ。
2016-05-20
SRM 675
https://competitiveprogramming.info/topcoder/srm/round/16625/div/1
Div1 Easy (300) TreeAndPathLength3
問題
- 頂点数500以下で長さ3のパスがS本の木を作成せよ
方針
- Sが497以下のとき、S+3個を横一列につなぐだけでいい
- Sが498以上のときは、ウニ状のノードを二つ連結して作る
- たとえばノード0にノード1,2,3,4,5、ノード1にノード6,7,8,9がつながっていて、ノード0と1を連結させると、長さ3のパスは4×4=16個のパスできる
- R=√Sとして、R+1個とR個のノードでウニを作って連結して、不足分は適当なノードの末尾に横一列で足す
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_675/TreeAndPathLength3.cpp
結果
o-- 114.79 245th/412 rating 1219 -> 1268 (+49)
超久しぶりに正の点数を得て良かった。なんとかDiv1に残留した。
ウニ状のノードといえばSRM 566のPenguinSleddingで、そっちもたまたま解けた。
Mediumはメモリ1MBという鬼のような制限だったらしい。
2016-05-15
SRM 674
https://competitiveprogramming.info/topcoder/srm/round/16624/div/1
Div1 Easy (250) VampireTree
問題
- バンパイアは、人間をバンパイアに変化させることで生まれる
- その変化の際、もともとのバンパイアがマスターに、元人間はサーバントとなる
- バンパイアから別のバンパイアへ、マスターまたはサーバントへ1つずつたどった最小の回数を距離とする
- バンパイアの親子関係が与えられる
- マスターを持たないバンパイアが一つだけ存在する
- 親子関係に矛盾がない場合、バンパイアの距離の最大値を求める
方針
- (終了後)
- たぶん木
- 木のとき、辺を2以上持つノードを移動していく
- 葉から辺を2以上持つノードを経由して葉に至るので、葉が2つ以上あるノード数+1が答え
- 木でなければ-1
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_674/VampireTree.cpp
結果
--- 0pt 181st/316 rating 1219 -> 1219 (+0)
サーバントが直接の子のみを指す、というのは最後の長いサンプルをよく読むとわかるようになっていたが、どのみちシンプルな解法を見つけるのが難しかった。
AC率が低くDiv2落ち回避。
2016-05-10
SRM 673
https://competitiveprogramming.info/topcoder/srm/round/16616/div/1
Div1 Easy (300) BearCavalry
問題
- N頭の熊と馬がいる
- それぞれの強さが与えられる
- それぞれの熊に馬を1頭ずつ与えて騎兵とする
- 騎兵の強さは熊と馬の強さの積である
- 先頭の騎兵の強さが、他のどの騎兵よりも強い組み合わせの場合の数を求める
方針
- (終了後)
- 先頭の熊に対して、全ての馬を試す
- 2番目以降の騎兵[i]が先頭の騎兵を上回らない数をx[i]個とすると、max(0, x[i]-i)通りあるので、かけていく
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_673/BearCavalry.cpp
結果
--- 311th/429 0pt rating 1270 -> 1219 (-51)
数えあげ難しい。