torus711 のアレ

主に競技プログラミングの問題について書きます

SRM 587, Division 1, Level 1 ( Division 2, Level 2 ) : JumpFurther

概要

無限に長い階段があり、最初は 0 段目にいる。
次のような移動を N 回行う。

  • i 番目( 1-indexed ) の移動では、現在地点を c とすると、c または c + i 段目に移動する

ただし、階段の内どこか一段は壊れていて、その部分を踏むことはできない。
到達できる最高の高さを求めよ。

解法

まず、階段が壊れていない場合について考えます。
この場合、その場に留まる判断は無駄になるので、全ての移動に於いて登ることが最善になります。
次に、どこか一段が壊れているという条件を加えます。
この場合でも、全ての移動で登る戦略を取ったときに壊れている段を踏まなければ、全ての移動で登ることが最善になります。
そのような移動をすると壊れている段を踏んでしまう場合はその段を避ける必要があります。
ところで、一番最初の移動でその場に留まる判断をするとそれ以降の全体が一段下にずれます。
移動のルールに着目すると、一番最初を除き、一段以上間を開けて移動していることが分かります。
つまり、最初に一段ずらすことで壊れている段を確実に避けることができます。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class JumpFurther
{
public:
	int furthest( int N, int badStep )
	{
		bool onBroken = false;
		int cur = 0;
		REP( i, 1, N + 1 )
		{
			cur += i;
			onBroken |= cur == badStep;
		}

		return cur - onBroken;
	}
};