hotpepsiの練習帳

SRM 634

02:10

Div1 Easy (250) ShoppingSurveyDiv1

問題

• M種類の商品があり、購入総数が配列で与えられる
• N人の顧客がいて、それぞれの種類の商品を最大1個買う
• K種類以上購入した顧客(big shopper)の最小値を求める

方針

• とりあえず均等に振り分ける
• と、サンプルが通らない
• big shopperには買えるだけ買わせるのがベストで、残りを均等に分配する
• big shopperが何人かわからないので、2分探索
• Passed System Test
• ソートしないなら全探索でよかった
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_634/ShoppingSurveyDiv1.cpp

結果

o-- 139.27pt 185th/394 rating 1712 -> 1705 (-7)

ださいコードだけど、毎回ソートして全探索でTLEしている人もいたので、結果的にはまあ良かった。

最大ケースを用意しておくべき。

http://togetter.com/li/723958

SRM 633

math | 16:57

Div1 Easy (250) PeriodicJumping

問題

• 二次元平面上に蛙がいる
• ジャンプできる距離の配列が与えられる
• {2,5}が与えられたときは距離2,距離5,距離2,...のようにジャンプできる
• ジャンプする方向はx軸またはy軸に平行でなくてよい
• (x,0)に到達するために必要なジャンプの回数を求める

方針

• 総和をsumとすると、sum < |x|のときは常に到達不可能
• 基本的にはsum >= |x|なら到達できる
• が、test case3のようにでかい値が含まれているときはだめ
• 最大値をMとして、M > (|x|+sum-M)のときはどういう行きかたでも到達できない(原点とxを頂点にした3角形が作れない)
• そうでないとき、すなわちM <= (|x|+sum-M)なら、方向を工夫すれば必ず到達できる(多角形が作れる)
• 2週以上するときは、Mが2回以上含まれていて、sum以下のどこにでも行けるので、総和の判定だけでよい
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_633/PeriodicJumping.cpp

結果

o-- +3 75.00 + 150 = 225.00pts 43rd/737 rating 1557 -> 1712 (+155)

他の総和を超えたらというのはよくある感じだが、正解できてよかった。

総和をintにしていると死ぬ100,{1,1<<29×8}というケースを用意したらはまって3撃墜。

highestの記念にスクリーンショット撮っておいた。

http://togetter.com/li/720547

SRM 632

全探索 | 23:09

Div1 Easy (300) PotentialArithmeticSequence

問題

• N個の正の整数からなる配列aがある
• aの各要素を2進表現したときの末尾のゼロの個数の配列dが与えられる
• 1個以上の連続する要素が1ずつ増加する等差数列になっている部分集合の総数を求める

方針

• 規則性はありそうだが式が出せない
• とりあえず全部出力して眺める
• 大きな数は64個毎に、6→7→6→8→6→9...と出現し、それ以外の部分は6未満で周期性がある
• 7以上の数を全部7に置換すれば、0～256の範囲内の数値だけで比較できそう
• 全部の位置について、全部の長さを比較する
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_632/PotentialArithmeticSequence.cpp

結果

o-- 133.09pts 265th/600 rating 1536 -> 1557 (+21)

最近黄色率が高くて好調。

agwさんと同室だった。4回目らしい。(535,597,603,632)

http://togetter.com/li/715618

SRM 631

02:04

Div1 Easy (250) TaroJiroGrid

問題

• N×Nの升目があり、それぞれの升目は黒か白である
• 1回の操作で、1行全部を白に塗るか、または全部を黒に塗ることができる
• それぞれの列について、N/2個より多くの連続する升目がないようにしたい
• 最小の操作回数を求める

方針

• 半分のところを塗れば最大2回なので、1回で白黒ぜんぶ試してOKなら1、そうでなければ2
• ただし最初から条件を満たしていれば0
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_631/TaroJiroGrid.cpp

Div1 Medium (500) CatsOnTheLineDiv1

問題

• 左から右の直線上に猫が何匹かいる
• 位置と匹数が与えられる
• 時間timeだけ左右のどちらかに移動できる
• 2匹以上が存在する座標の総数の最小値を求める

方針

• 展開すると0、集めると1になる
• 展開したときと集めたときでDPみたいなテーブルを作る
• サンプル通ったので提出
• Challenge Succeeded
• 配列の制限が1000までだったので死んだが、それ直してもバグっていた
• kojingharangさんのところを読む
• 左から処理していく
• 一つ前に一箇所に集めたとき、そこに合流できるなら合流するのが優先
• 1匹に展開できるなら左に寄せる
• どちらも無理なら右に寄せて、答えを+1する
• 展開できる場合、狭いものを優先する必要があるかと思ったが、左詰めでぶつかるのであれば、少なくとも一方は集める必要があるので、幅の小さい(数が少ない)ほうを優先したりする必要はなかった

結果

ox- +1 169.55+50=219.55pts rating 1453 -> 1537 (+84)

SRMらしい問題。

http://togetter.com/li/713244

SRM 630

14:49

Div1 Easy (250) Egalitarianism3

問題

• N個の都市がある
• それぞれの都市はN-1本の道路で接続されておりそれぞれの長さが与えられる
• どの2都市の距離も全て等しいという条件を満たす最大の都市数を求める

方針

• とりあえずWFで距離を求める
• 終了
• 2点を決めてsetに突っ込んでおく
• 今までに存在する点すべてと距離が同じものを足す
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_630/Egalitarianism3.cpp

結果

xxx -1 -25pts 441st/465 rating 1613 -> 1453 (-160)

N<=2のときNになるという考察が足りなかった。

解がスター状になるといえばSRM 566のPenguinSleddingも。

http://togetter.com/li/709546