hotpepsiの練習帳

SRM 514 Div2

01:47

不参加なので後追い。

Easy (250) MagicalGirlLevelOneDivTwo

問題

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

方針

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

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_514/MagicalGirlLevelOneDivTwo.cpp

Medium (500)

問題

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

方針

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

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_514/MagicalGirlLevelTwoDivTwo.cpp

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に入っているのかを再帰で求める

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_514/MagicalGirlLevelThreeDivTwo.cpp