Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-01-24SRM456 Div1 450 CutSticks

SRM456 Div1 450 CutSticks

| 12:10 | SRM456 Div1 450 CutSticks - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM456 Div1 450 CutSticks - SRM diary(Sigmar) SRM456 Div1 450 CutSticks - SRM diary(Sigmar) のブックマークコメント

様々なintの長さの棒がn本与えられる。棒を最大C回まで切ることができる。切った棒は2本の棒になる。切った棒をさらに切ることもできる。最終的に切り終わったあと棒を長い順に並べたとき、K番目に長い棒が最も長くなるように切ったときのK番目の棒の長さを求めよ。
解はdouble。棒の数の初期値は1~50本、各棒の長さの初期値は1~1,000,000,000、Cは1~1,000,000,000、Kは1~n+Cの間の値。

二分探索で解を求めることができます。
解の候補値をxとした場合、以下の2つの条件を満たすとき、解はx以上となりえます。

  • 各棒の長さの初期値をxで割った値を切り捨てて整数に丸めたもの(長さx以上の棒の最大数、s[i]とする)を合計した値(ssumとする)がK以上(Cが無限大の場合の、長さx以上の棒をK個以上作れるかどうかの判定)
  • s[i]を-1したもの(切断回数)の合計からssum-K(必要以上に切断した回数)を減算した値がC以下(切断回数C以下で上記の条件を満たせるかどうかの判定)

以上の条件で、両方とも真のときに下限をxとし、どちらかが偽のときに上限をxとし、xを上限と下限の中央値として判定を繰り返すことで解を導き出すことができます。初期値は上限が最も長い棒の長さ、下限は0です。(上限と下限の差の最大値10^9から誤差10^-9以下にするため、60回以上繰り返せば解が算出されます。)

私は本番中には二分探索で解くという方針を思いつかなかったので、直接的に解を求めようとして時間切れになってしまいました。解の範囲が大きい時は二分探索を方針の一つとして考慮してみる価値があるようです。

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100124

2010-01-23SRM456 Div1 250 SilverDistance

SRM456 Div1 250 SilverDistance

| 16:41 | SRM456 Div1 250 SilverDistance - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM456 Div1 250 SilverDistance - SRM diary(Sigmar) SRM456 Div1 250 SilverDistance - SRM diary(Sigmar) のブックマークコメント

将棋の銀将は前、斜め前、斜め後ろに進むことができる。
無限に大きい将棋盤において、始点と終点が与えられたとき、始点から終点まで銀将は最短何手で移動できるか。
始点、終点のx座標、y座標は-1,000,000以上1,000,000以下の値。

値の範囲が大きいので、bfs等での探索は厳しいと考えられます。
この問題は終点までのマンハッタン距離が最小になるように進むGreedy的な手法で解答が可能です。

銀ではなく、王将だったとしましょう。この場合、最短経路は明らかに上記Greedy手法となり、解はmax(|始点のx座標-終点のx座標|,|始点のy座標-終点のy座標|)です。一方銀の場合、真横と後ろには進めませんので、斜め移動により横や後ろに進むことになります。
ここで、斜め移動のみをする場合を考えます。斜め移動のみだと、市松模様でいう同じ色のマスにしか移動できません。そのため、始点と終点が別の色のマスだった場合、必ず前に一手進まなければなりません。また、逆に同じ色のマスにいる場合は、斜め移動のみで必ず王将と同じ最短手数で終点に到達できます。
|始点のx座標-終点のx座標|+|始点のy座標-終点のy座標|が偶数の場合、始点と終点は同じ色となり、奇数の場合異なる色となります。

以上より解は、奇数の場合のみ始点のy座標を+1して、奇数の場合解の初期値を1、偶数の場合0としてmax(|始点のx座標-終点のx座標|,|始点のy座標-終点のy座標|)と加算することで求められます。

なお、本番中は解の計算が面倒なのと、手計算での誤りを防ぐため、最初の斜め移動を、while文でx座標かy座標が終点と同じになるまでxとyをインクリメントorデクリメントするという実装をしていました。また、最初に前に進むという手法が思いつかなかったので、斜め移動のあと適当に帳尻合わせをしていました。

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100123