Hatena::Grouptopcoder

hotpepsiの練習帳

2015-06-07

Facebook Hacker Cup 2015 Qualification Round

21:40

A. Cooking the Books

問題

  • 数字が与えられる
  • 2つの桁を交換して、最小と最大を作る
  • ただし先頭が0にならないこと

方針

B. New Year's Resolution

問題

  • 3つの栄養素を目標量だけきっちりとりたい
  • N種類の食べ物と、3つの栄養素の量が与えられる
  • 食べるか食べないかを選ぶ
  • 目標量にできるかどうかを求める

方針

C. Laser Maze

問題

  • スタート地点とゴール、いくつかのレーザー砲台からなる迷路がある
  • レーザー砲台は1ターンに時計回りに90度回転する
  • ゴールまで到達できるかどうかを求める

方針

結果

ooo 100pt

レーザー砲台みたいなアレンジは好き。

半年遅れだけど埋めていく予定。

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150607

2015-04-14

SRM 647

00:51

Div1 Easy (250) BuildingTowersEasy

問題

  • N個の建物を建てる
  • 位置x[i]にある建物の高さはt[i]以下であること
  • 1番目の建物の高さは0であること
  • 隣り合う建物の高さの差は1以下であること
  • 建物の高さの最大値を求める

方針

  • 結果

o-- 161.34pts 219th/511 1410 -> 1460 (+50)

ぎざぎざの山頂のイメージ。


http://togetter.com/li/774013

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150414

2015-02-15

SRM 646

00:13

Div1 Easy (250) TheConsecutiveIntegersDivOne

問題

  • いくつかの数が与えられる
  • 任意の数を+1または-1して、k個の連続した数を作る
  • 最小の操作回数を求める

方針

結果

x-- 0pts 250th/352 rating 1492 -> 1410 (-82)

平均に合わせるとかえって移動量が多くなってしまうようだ。

参加者少ない。やばい。


http://togetter.com/li/770610

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150215

2015-02-11

SRM 645

21:50

Div1 Easy (250) JanuszTheBusinessman

問題

  • ホテルを経営している
  • 宿泊客の到着日と出発日の配列が与えられる
  • 宿泊客に特別なサービスをすると、良いレビューを残してくれる
  • 特別なサービスを受けた宿泊客に居合わせた宿泊客も良いレビューを残してくれる
  • 全員が良いレビューを残すために必要な特別サービスの最小値を求める

方針

  • 蟻本の区間スケジューリング問題のようなやつ
  • 出発日が一番早い人から貪欲に処理していけばよさそう
  • 良いレビュアーではない人のうちの一番早い出発日に宿泊していて、出発日が一番遅い人に特別サービスを与える
  • その範囲内の人を良いレビュアーにする
  • Failed System Test
  • すでに良いレビュアーだが、それ以降の区間で特別サービスを与えたほうがよいケースを見落としていた
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_645/JanuszTheBusinessman.cpp

結果

x-- +1 50pts 162nd/471 rating 1426 -> 1492 (+66)

easyはDPできるかと思ったが無理だった。

貪欲のコーナーケース難しい。


http://togetter.com/li/769406

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150211

2015-01-28

SRM 644

01:35

Div1 Easy (250) OkonomiyakiParty

問題

  • M人でお好み焼きパーティーをする
  • T種類のお好み焼きがあり、それぞれの大きさが与えられる
  • M種類購入したとき、大きさの差がK以下になる組み合わせの総数を求める

方針

結果

unrated

サンプル4が114514になっているの全く気がつかなかった。


http://togetter.com/li/765225

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150128