Hatena::Grouptopcoder

hotpepsiの練習帳

2014-09-19

SRM 633

| 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の記念にスクリーンショット撮っておいた。

f:id:firewood:20140919143429p:image:w256

f:id:firewood:20140919143622p:image:w256

http://togetter.com/li/720547

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140919

2014-05-15

SRM 617

| 02:15

Div1 Easy (250) MyLongCake

問題

  • 長さNのケーキがある
  • 何人かの友達が来るので、到着前にケーキを切っておく
  • 友達の数はN未満かつNの約数であり、何人到着するかは不明である
  • 友人の到着後、切っておいたケーキの連続するピースを渡す
  • ただし各友人には同じ量だけ渡す
  • 分割数の最小値を求める

方針

結果

o-- 162.54pts 551st/842 rating 1578 -> 1544 (-34)

わからないのにプラス点で反省。


http://togetter.com/li/657938

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140515

2014-04-29

SRM 611

| 01:40

Div1 Easy (250) LCMSet

問題

  • 集合Sが与えられる
  • Sの全要素の最小公倍数をlcm(S)とする
  • Sの全ての部分集合のlcmの集合をLCM(S)とする
  • AとBが与えられる
  • LCM(A)とLCM(B)が等しいかどうかを求める

方針

  • Challenge Succeeded
  • BにAの1要素aが含まれていないときは、Bの部分集合からaを作れる必要がある(逆も)
  • Bの要素のうち、aの約数になっているもののLCMを取っていって、結果がaと等しいなら、aが作れる。作れないなら、等しくない
  • Aの任意の部分集合について考える
  • Aの任意の要素p,qについて、pとqそれぞれはBの部分集合で作ることができる。LCMについては、素因数単位で考えると乗数の最大値を取ったものであり、Bの同じ要素を2回以上使う必要はないので、LCMについても作ることができる。つまり任意の部分集合のLCMが作れる
  • なので、要素を作れるかどうかだけ判定すればよい
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_611/LCMSet.cpp

結果

x-- 0pt 341st/644 rating 1257 -> 1247 (-10)

なぜ要素が作れるかどうかだけで判定できるのか理解するのに時間がかかった。


http://togetter.com/li/637876

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140429

2014-04-16

SRM 608

| 00:38

Div1 Easy (300) MysticAndCandies

問題

  • N個の箱がある
  • それぞれの箱にはキャンディーがlow[i]~high[i]個入っている
  • キャンディーは全部でC個
  • X個以上食べるには何箱あければよいか

方針

結果

x-- 0pt 389th/741 rating 1242 -> 1227 (-15)

十分条件ではさむのって典型ぽいけど割と解けない。


http://togetter.com/li/626507

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140416

2014-04-06

SRM 604

| 23:39

Div1 Easy (250) PowerOfThree

問題

  • 4方向の移動を受け付けるロボットがいる
  • ターンkに距離3^k移動できる
  • 与えられた座標に移動可能かどうかを求める

方針

  • 各桁が-1か+1の3進数みたいな感じ。平衡三進法というらしい。
  • xとyを平衡三進法で表したとき、各桁がxとyどちらかだけに属すること
  • x方向とy方向の移動をそれぞれビット化
  • xとyが排他で、下位から全てのビットが連続していること
  • Failed System Test
  • 書き直し
  • 一番下の桁から見ていく
  • xとyを3で割った余りを調べる
  • 片方だけ余りがあるならOK、そうでなければ不能
  • 余りを加えて3で割っていく(余りが2のときは繰り下がりがあるので、そのぶんを加える)
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_604/PowerOfThree.cpp

結果

x-- 0pt 513rd/843 rating 1247 -> 1228 (-19)

余りの処理を間違って死。

Cの場合余りが数の正負に影響されるので、absで正にしておいたほうが楽。


http://togetter.com/li/614555

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140406