hotpepsiの練習帳

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問解けるようにしたい。