2014-04-03
SRM 603
着想 |
Div1 Easy (250) MaxMinTreeGame
問題
- 頂点と辺からなる木が与えられる
- それぞれの頂点には点数がある
- 2人のプレーヤーが交互に辺を一つ選び除去する
- 分離された一方を残し、もう一方を消す
- 残りが頂点一つになったとき、その頂点の点数がスコアとなる
- 先手が点数を最大化、後手が点数を最小化しようとするとき、先手の点数の最大値を求める
方針
- 愚直にメモ化DFSっぽい何かを提出
- Failed System Test
- 後手は任意の葉を選択できる
- なので、先手は葉でない頂点を選ぶのは意味がなく、葉の最大を選択するのが最善
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_603/MaxMinTreeGame.cpp
結果
x-- 0pt 442nd/608 rating 1301 -> 1247 (-54)
思考力不足
2014-03-30
SRM 602
DP |
Div1 Easy (250) TypoCoderDiv1
問題
- LowerはTypoCoderに参加している
- レーティング2200未満が水色、2200以上が茶色である
- 一回の増減が配列Dで与えられる
- 増えるか減るかのどちらかを選べる
- 0未満にはならない
- 2回連続で茶色になりたくない
- レーティングの変化回数の最大値を求める
方針
- Dの値が大きいのでレーティングを配列で持てなさそう
- 2200以上になるときは、その次は2200未満になる必要がある
- rate+D[i]-D[i-1]が2200未満のとき更新というDPを書く
- 最後だけはその次がないので、2200以上のみ考慮する
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_602/TypoCoderDiv1.cpp
結果
o-- 101.85pt 530/789 rating 1298 -> 1301 (+3)
DP力が上がっている気がするが、一年間の実績では1327 -> 1301で進歩してなかった。
2014-03-23
SRM 601
greedy |
Div1 Easy (250) WinterAndPresents
問題
- りんごとみかんが入っている袋がいくつかある
- それぞれの袋からX個取り出す
- りんごとみかんの数の組み合わせが何通り可能かを求める
方針
- 任意のX個取り出す場合について考える
- それぞれの袋から、取り出せるみかんの最小個数と最大個数を集計する
- 最大-最小+1通り取り出すことができる
- Xを1から試していき、X個取り出せない袋があったら終了
- Passed System Test
- (書き直し)
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_601/WinterAndPresents.cpp
Div2 Easy (250) WinterAndMandarins
問題
- みかんの入った袋がある
- K袋選ぶ
- みかんが入っている個数の差の最小値を求める
方針
- ソートする
- 先頭のK個に着目する
- K個の末尾と先頭の差を求める
- スライドしていき最小値を求める
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_601/WinterAndMandarins.cpp
Div2 Medium (500) WinterAndCandies
問題
- 何種類かのキャンディーがある
- キャンディーの種類は正の整数
- K個取り出す
- 1からKまでの種類が揃うのは何通りか求める
方針
- 同じ種類で別のキャンディーは別物として数えるっぽい
- 種類ごとに配列cにカウントしておく
- 3種類の場合c[1]×c[2]×c[3]通り
- 全体としてはc[1]＋c[1]×c[2]＋c[1]×c[2]×c[3]...となる
- 歯抜けになる場合は、途中のカウントがゼロになるので問題ない
- K=1から足してかけて...としていく
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_601/WinterAndCandies.cpp
結果
o-- 118.42pt 513rd/767 rating 1297 -> 1298 (+1)
提出したときは、最初にXの最大値を求めた。条件を分離するのは悪くないけどタイプ数としては無駄だった。あとK=0から足してつじつまが合わなくなり最後に1ひいてださかった。
冬はこたつみかんですね。
2014-03-16
SRM 600
greedy |
Div1 Easy (250) ORSolitaire
問題
- 数値の配列が与えられる
- 初期値を0として、配列の要素をORしてgoalにする
- 要素をいくつ削除したらgoalにできなくなるかを求める
方針
- bit単位で考える
- goalに含まれないbitが立っている要素は無視する
- 取り除く最小値 = 各bitの出現数の最小値が答え
- Failed System Test
- 書き直し
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_600/ORSolitaire.cpp
Div2 Easy (250) TheShuttles
問題
- N箇所の拠点と、それぞれの社員数が与えられる
- それぞれの拠点について、全員を運べる台数を用意する
- 全てのシャトルの座席数は同じである
- シャトル1台のコストはbaseCost＋seatCost×座席数である
- コストの最小値を求める
方針
結果
x-- 0pt 889th/1007 rating 1420 -> 1297 (-123)
ビットのループを、小ネタで
for (int b = 1; b > 0; b *= 2)
と書いたらTLEで死んだ。
Visual C++では停止するが、GCCだと条件が常に真と見なされて無限ループになっていた。
条件は色々あるようだ。
https://twitter.com/hirose_golf/status/435034777968603136
for(int i = 715827882; i >= 0; i *= 3)は無限ループするが
for(int i = 715827883; i >= 0; i *= 3)は無限ループしなかったり。
C言語むずかしい。
2014-03-10
SRM 599
math |
Div1 Easy (250) BigFatInteger
問題
- LunはAのB乗のような巨大な数が大好きである
- Xの初期値を1とする
- Xには素数か、または、Xの約数をかけることができる
- AのB乗にするための最小の手数を求める
方針
- 素数については必ず1回は必要
- 素因数分解する
- 任意の約数をかけることができるので、素因数の中で乗数Cが一番多いものだけ考えればいい
- 繰り返し2乗法的な感じ
- 2^16だったら2^1 -> 2^2 -> 2^4 -> 2^8 -> 2^16と5回でいける
- B乗の部分についても繰り返し2乗法
- Failed System Test
- A^(C×B)という形になるが、乗数をC×Bでひとまとめにして2の累乗で切り上げする必要があった
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_599/BigFatInteger.cpp
Div2 Easy (250) MiniatureDachshund
問題
- みかんを食べた量だけ体重が増える
- 体重は5000グラムを超えてはならない
- 食べられる最大の個数を求める
方針
結果
x-- +1 -1 25pt 481st/739 rating 1439 -> 1420 (-19)
素数表まったくいらなかった。シンプルに書くの難しい。