2016-08-30
SRM 684
https://competitiveprogramming.info/topcoder/srm/round/16688/div/1
Div1 Easy (250) CliqueParty
問題
- 数値の集合Sが与えられる
- 任意の要素A,Bが常にA <= k×Bを満たすとき、良い集合とする
- Sの部分集合Xの任意の要素A,Bの差|A-B|からなる集合をDとする
- Dが良い集合となるXの要素数の最大値を求める
方針
- ソートしておき、区間[i,j]をすべて試す
- 2要素を取り出したとき、差は一つで、これは必ず成立する
- 区間(i,j)の要素を一つずつ試し、成立するなら追加していく
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_684/CliqueParty.cpp
結果
o-- 103.15pt 188th/386 rating 1442 -> 1474 (+32)
問題文に出てくるk-smoothは、数学用語だと、最大の素因数がk以下の数のことらしい。
2016-08-23
SRM 683
https://competitiveprogramming.info/topcoder/srm/round/16653/div/1
Div1 Easy (250) MoveStones
問題
- 何個かの石からなる山がN個あり、円環状に並んでいる
- 各山の個数は配列a[0],a[1],...a[N-1]で与えられる
- 1ターンに、1個の石を隣に移動できる
- 山の個数をb[0],b[1],...b[N-1]にするための最小ターン数を求める
方針
- 適当に書く
- Challenge Succeeded
- (終了後)
- 最適解では、お互いにやりとりしない山が発生するので、各山がその位置であると仮定して全山で試せばよいらしい
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_683/MoveStones.cpp
結果
x-- 0pt rating 1490 -> 1442 (-48)
部屋一位の人(Blue.Maryさん)の解法は、差分の累積和v[i+1] = v[i] + a[i] - b[i]を求めておいて、その中央の値m = v[N÷2]とすると、その差の累積和Σ|v[i] - m|が答えらしい。
ひとつずつ移動する系はSRM 645 Div2 MediumとかSRM 646 Div1 Easy TheConsecutiveIntegersDivOneとか、(平均ではなく)中央値に集めるのが最適になることが多いようだ。
2016-08-20
SRM 682
https://competitiveprogramming.info/topcoder/srm/round/16652/div/1
Div1 Easy (300) SmilesTheFriendshipUnicorn
問題
- 友人関係の双方向のグラフが与えられる
- 友人関係を4つたどって異なる5人にたどりつけるかどうかを求める
方針
- 辺の数が少ないので、ぎりぎり全探索行けそう
- こういうのを列挙する D <- B <- A -> C -> E
- DからEまで全て異なっていればOK
- Aは全頂点で試す
- 頂点Aから行ける、異なる2頂点B,Cを全て列挙する
- DはBから行ける頂点のうち、A,C以外
- EはCから行ける頂点のうち、A,B,D以外
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_682/SmilesTheFriendshipUnicorn.cpp
結果
o-- 127.68pt 110th/280 rating 1427 -> 1490 (+63)
もっと長いのを見つけるにはcolor codingらしい
2016-08-19
SRM 681
https://competitiveprogramming.info/topcoder/srm/round/16651/div/1
Div1 Easy (300) FleetFunding
問題
- M種類の部品から宇宙船を作る
- N個の工房があり、それぞれ番号a[i]からb[i]までのいずれかの部品を最大k[i]個だけ作れる
- 最大何隻の宇宙船を作れるかを求める
方針
- (終了後)
- 二分探索
- (b[i],a[i])でソートしておく
- 貪欲に使って、作れたらOK
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_681/FleetFunding.cpp
結果
--- 0pt unrated
りんごさん復活の回。
にぶたん思いつかなかった。
2016-08-17
SRM 680
https://competitiveprogramming.info/topcoder/srm/round/16650/div/1
Div1 Easy (250) BearFair
問題
- 森で熊に出会った
- 熊が配列Xに関するクイズを出す
- Xの要素は全て異なる
- XはN個の数値からなり、Nは偶数である
- Xの全ての要素は1以上b以下である
- Xの半分は偶数で半分は奇数である
- q個のヒントが与えられる
- Xの要素のうちupTo[i]以下の個数はquantity[i]個である
- 熊が嘘をついているかどうかを求める
方針
- 番兵としてb以下がN個という情報を足す
- bでソートして昇順に処理する。ありうる偶数奇数の総数をカウントする。
- quantityがNを超えていたら不正
- upTo[i]がupTo[i-1]と同じでquantityが異なるとき、不正
- そうでないときは、upTo[i-1]+1からupTo[i]までの数について、(quantity[i]-quantity[i-1])個を超えない範囲で、偶数奇数のカウントを増やす
- 最終的に偶数奇数どちらもN÷2個以上の可能性があればOK
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_680/BearFair.cpp
結果
o-- 134.51pt 175th/439 rating 1365 -> 1427 (+62)
番兵を使えば場合分け不要だった。