Hatena::Grouptopcoder

hotpepsiの練習帳

2014-02-23

SRM 598

| 23:15

Div1 Easy (250) BinPacking

問題

  • 制限重量が300の容器がいくつかある
  • 重さ100以上300以下の品物がいくつか与えられる
  • 必要な容器の最小の個数を求める

方針

Div1 Medium (550) FoxAndFencing

問題

  • 1直線状の升目があり2人でゲームを行う
  • 二つの駒を距離d離して配置する
  • それぞれの速度と射程が与えられる
  • それぞれが最善手でプレイするときの勝者を求める

方針

  • (a)1手目で決まる(b)2手目で決まる(c)それ以外、に場合わけ
  • (c)は、速い方が勝者の候補
  • Challenge Succeeded
  • 自分のターン終了時、相手が1歩動いても相手の射程内にぎりぎり入らない状態でいる必要があるが、相手は最大限離れるので、自分の速度 > (相手の速度×2+射程差) が必要条件
  • https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_598/FoxAndFencing.cpp

Div2 Easy (250) ErasingCharacters

問題

  • 誕生日に文字列をもらった
  • 長すぎるので、連続する2文字を削除していくことにした
  • 最終的に得られる文字列を求める

方針

結果

ox- 211.32pt 212nd/484 rating 1400 -> 1439 (+39)

easyはまあまあ良かった。このmediumが解けないのは痛い。

SRMでも誕生日プレゼントが文字列に。

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

2014-02-22

SRM 597

| 19:57

Div1 Easy (250) LittleElephantAndString

問題

  • 同じ長さの文字列AとBがある
  • Aの任意の文字を先頭に移動できる
  • AとBを等しくするための手数を求める(不可能なら-1)

方針

  • ソートして一致しない場合は不可能
  • 例としてA=edcba,B=abcdeで考える
  • 先頭への移動しかできないので、末尾の文字eより後ろの文字は全て移動する必要がある
  • dについて考えると、e以外の文字は全て移動する必要がある
  • と考えていくと、末尾から、移動不要なものをe->d->cと一つずつ見つけ、それ以外のものは全て移動すればよい
  • Passed System Test
  • https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_597/LittleElephantAndString.cpp

Div2 Easy (250) LittleElephantAndDouble

問題

  • 数値の配列が与えられる
  • どれかの要素を2倍にできる
  • 全ての要素を等しくできるかどうかを答える

方針

結果

o-- +1 198.95 + 50 = 248.95pt 69th/740 rating 1236 -> 1400 (+164)

初の二桁順位。

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