2015-01-17
SRM 643
Div1 Easy (250) TheKingsFactorization
問題
- 数Nを素因数分解したい
- 奇数番目の素因数が与えられる
- 全ての素因数を昇順に求める
方針
- まず与えられた素因数で割る
- 大きな素因数が2つ残るケースは{2,未知a,既知,未知b}のとき
- 未知aは最大でも10^6なので、10^6まで素因数分解する
- 残った数は素数
- Passed System Test
- (書き直し)
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_643/TheKingsFactorization.cpp
結果
o-- 129.17pts 252nd/538 rating 1382 -> 1426 (+44)
年末のレートは1093 -> 1327 -> 1301 -> 1426
微妙に成長している。
コメントを書く
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150117
2015-01-13
SRM 642
Div1 Easy (250) WaitingForBus
問題
- N台のバスがある
- ランダムでどれかのバスが出発する
- 戻ってきたら次のバスがランダムで選ばれる
- バスが選ばれる確率と、戻ってくるまでの時間の配列が与えられる
- 時刻sでの平均待ち時間を求める
方針
- 時刻ゼロの時は待ち時間なし
- 確率で重みづけして到着時刻の位置に加算していく
- 時刻sまで計算する
- 時刻sより先のtに確率pでバスが存在するなら期待値は(t-s)*p
- 期待値の和が答え
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_642/WaitingForBus.cpp
結果
o-- 192.21pts 133rd/367 rating 1298 -> 1382 (+84)
誤差恐怖症なのでlong doubleにした。
もしバスのスケジュールがこんなだったらタクシーに乗る。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150113
2015-01-11
SRM 641
Div1 Easy (250) TrianglesContainOrigin
問題
- 点の集合が与えられる
- 一直線上に3点が並ぶことはない
- 原点を内側に含む三角形が何個できるか求める
方針
- 任意の2点A,Bを選び、そこを底辺として、原点の向こう側にある点の範囲を数える
- 提出間に合わず
- 反時計回りに列挙できるように、2π足した点も配列に足しておく
- 角度がA＜B、かつ、(B-A)＜πの2点を底辺とする
- A＋πより大きくB＋π未満の点を数える
- 3辺のうち全ての2辺を列挙することになるので、最後に半分にする
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_641/TrianglesContainOrigin.cpp
結果
--- 0pts 232nd/519 rating 1312 -> 1298 (-14)
外積を使って解けるらしい。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150111
2015-01-08
SRM 640
Div1 Easy (250) ChristmasTreeDecoration
問題
- クリスマスツリーのデコレーションをする
- N個の星飾りがあり、それぞれの色が与えられる
- 飾りと飾りはリボンで結ぶことができる
- 結ぶことができる飾りの番号のリストが与えられる
- できる限り異なる色で結びたい
- 同じ色で結ぶことになる最小の個数を求める
方針
- まずできる限り異なる色のものだけ結ぶ。union find木で記憶しておく
- そのあと同じ色のものを必要最小限だけ結ぶ(=木同士を接続する)
- 木の総数-1が答え
- 最小全域木らしい
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_640/ChristmasTreeDecoration.cpp
結果
o-- 132.62pts 337th/416 rating 1368 -> 1312 (-56)
div1勢は典型問題つよい。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150108
2015-01-06
SRM 639
Div1 Easy (250) AliceGame
問題
- 2人でターン制のゲームをする
- 各ターンの勝者はターン番号×2－1ポイントを得る
- 2人の総ポイントxとyが与えられる
- xポイントを取るための最小のターン数を求める
方針
- 提出できず
- 総和がN^2でない場合は不可能
- 片方が2の場合も不可能
- 2以外の数は作れる
- N*2-1からはじめて、x以上、かつ、偶奇が合うまで足す
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_639/AliceGame.cpp
Div1 Medium (500) BoardFolding
問題
- 升目上に白か黒が書かれた紙がある
- 模様が完全に重なるとき、端から折りたたむことができる
- 折りたたみの状態数を求める(結果的に残った範囲が同じなら重複して数えない)
方針
- 縦方向と横方向の折りたたみ方は独立しているので、最後に掛け算する
- 縦方向の折りたたみについて考える
- 1列単位で同じかどうかのテーブルを作る
- ある列を右端として左にK列折りたためるかと、左端から右にK列折りたためるかのテーブルを作る。ある列Xについて、K=1から左右の両方が同じかどうかで1列ずつ広げていく
- あとはDFS
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_639/BoardFolding.cpp
Div2 Easy (250) ElectronicPetEasy
問題
- 二匹の電子ペットに餌をやる
- 餌やりは時刻stから周期pでt回
- 同時に2匹の餌やりが発生するかどうかを求める
方針
Div2 Medium (500) AliceGameEasy
問題
- 2人でターン制のゲームをする
- 各ターンの勝者はターン番号と同じポイントを得る
- 2人の総ポイントxとyが与えられる
- xポイントを取るための最小の勝利ターン数を求める
方針
- 総和がN×(N＋1)÷2でない場合は不可能
- Nから足していく
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_639/AliceGameEasy.cpp
結果
--- -1 -25pts 493rd/539 rating 1522 -> 1368 (-154)
足し算してループするときにTLEすると勘違いしてチャレンジ失敗した。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150106