Hatena::Grouptopcoder

hotpepsiの練習帳

2012-05-29

Google Code Jam 2012 Round 2

00:08

A. Swinging Wild (5 + 9 points)

問題

  • 危険なジャングルの湿地帯にいる。
  • 自分の小屋から、愛するハニーのいる小屋へ到達したい。
  • 小屋と小屋の間には何本かの蔓(つる)がぶらさがっていて、蔓をターザンのようにスイングさせることにより、次の蔓をつかんで移動することができる。
  • 愛するハニーのもとへ到達できるかどうかを求める。

方針

  • 問題を何となく理解するのに30分かかり絶望
  • 蔓Bが蔓Aの稼動範囲内にあれば、行くことができる
  • 蔓Aから蔓Bへ移動してからスイングするまでには以下のお約束がある
  • (1)スイングして蔓Bをつかむ(2)蔓Bの真上に上る(3)蔓Aの方向へ水平方向へ戻る(4)蔓Bでスイングする
  • 蔓Aがぶらさがっている場所を越えて戻ることはできない(問題文の制約)
  • 蔓Bの長さが蔓Aがぶらさがっている場所までの距離より短い場合、蔓Bの長さでスイングできる(sample 3)
  • BFSで区間を更新するようにしたらlargeがTLEのため終了後解きなおし
  • 整理すると、最初にスイングする長さを超えることは決してなく、また、最適なコースをスタートからゴールまで進んでいくのみ
  • ある蔓の、つかむことができる最下点をメモしていく
  • 前方だけ更新していけばよい
  • https://github.com/firewood/topcoder/blob/master/gcj_2012/2_A.cpp

結果

5pt 2044th

A-smallしか解けなかったが、A(small+large)+B(small)を解いたとしてもTシャツに届かないという絶妙のゲームバランスだった。

positive scoreだったのはよかった。来年は2問解けるようにしたい。

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