Hatena::Grouptopcoder

hotpepsiの練習帳

2011-08-23

SRM 514 Div2

01:47

不参加なので後追い。

Easy (250) MagicalGirlLevelOneDivTwo

問題

  • 魔女をやっつけるために移動する
  • 魔法は2d×2dの大きさの正方形
  • 最小の移動距離を返す

方針

  • すでに射程内なら移動しない
  • x,yが負のときを考慮する
  • 水平移動距離min(0, |x|-d)
  • 垂直移動距離min(0, |y|-d)

実装

Medium (500)

問題

  • 魔女をやっつけるために移動する
  • チェスのナイトみたいな動きしかできない (n歩+1歩)

方針

  • TLEしたのでAnalysisを読む。
  • 奇数の移動(nが偶数)ができればどこでも移動できる
  • そうでなければ、(x+y)が偶数ならYES

実装

Hard (1000)

問題

  • 魔法少女が、悪い魔女を倒すために応用呪文を唱えようとしている
  • 応用呪文はK個の基本呪文の組み合わせからなる
  • 応用呪文A[i]は、A[i-1] + A[i-K-1] + A[i-2*K-1] + ...という和である
  • 呪文の強さは、呪文を唱える範囲のビットが立っている数の和である
  • 応用呪文A[n][lo..hi]の強さSを求める

方針

  • 題意がわからなかった
  • kusanoさんのを写経して理解
  • A[x]の長さを求めておいて、どのindexに入っているのかを再帰で求める

実装

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