hotpepsiの練習帳

SRM 598

greedy, ソート | 23:15

Div1 Easy (250) BinPacking

問題

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

方針

• 3つ詰め込めるのは100のときだけ
• それ以外は最大2個しか入らない
• 重い順に貪欲に詰め込んでいけばよさそう
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_598/BinPacking.cpp

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文字を削除していくことにした
• 最終的に得られる文字列を求める

方針

• 単純に消していく 再帰でもよさそう
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_598/ErasingCharacters.cpp

結果

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

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

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