395.1

NHC SRM

誤差変動。手が遅いなぁ...。

250

原点から(X,Y)へ移動する際に、縦か横に一マス移動するコストと斜めに一マス移動するコストが与えられる。このとき最小のコストを答えよという問題。


斜めに移動する方が縦に進んで横に進むよりも得するケースと、さらには縦ないし横に二マス移動するよりも斜めに二回移動する方が早いケースを吟味した上で答えれば良い。

500

NのPermutationのうち、右から見たときに、自分より前のすべてのものより多い個数と、左から見たときの個数を満たすものの数を答えよという問題。


Nから順に右端に追加するか左端に追加するかそれ以外の場所に追加するか、というので使用した数と右から見たときにいくつなのか左から見たときにいくつなのかというDP。

  int dp[n][n][n]; // checked * left * right
  dp[x][y][z] = (x - 2) * dp[x-1][y][z] + dp[x-1][y-1][z] + dp[x-1][y][z-1];


実際にはこれの変化形をグズグズやっていたのでひどいスコアになってしまった。

900

N問のクイズについて、正解したときにそれぞれもらえるスコアが決まっている。K問連続して正解すると、K問目に解いた問題に応じてボーナスももらえる。このとき連続回数が0にクリアされる。この状況で可能な最大のスコアを答えよという問題。


実装するだけなら簡単なDP。ただしO(N*K)になり、いずれも500k程度なので終わらない。どうやって最適化するのがいいんだろうなぁ...。

追記

各問題について、正解するか不正解するかでDPすればいいらしい。ある問題に正解する場合、K問前の時点でのスコアにK問連続正解分の点を足したものか、直前の時点でのスコアに今の正解分の点を足したもののうち大きい方。ある問題に不正解する場合、直前の時点でのスコアから今の不正解分の点を引いたものを入れる。


確かに特殊な状況だけ例外処理して、後は何食わぬ顔でDPするっていうのは妥当なんだろうなぁ...。