SRM 340 div1 level2

久しぶりです。TopCoder Open 2007に向けて、スキルを蓄積していこうかと思います。

SRM 340 div1 level2

理論スキルと実践スキルの2次元マップだと思えば、(0,0)から(skillBound, skillBound)まで移動する最短経路問題となる。ただし、移動は(0,1), (1,0), (1,1)が可能で、授業が受けられればどれも同じコスト。マップの大きさは、授業の数が50で二回以上受けても意味がないことから、0－50の５１ｘ５１でＯＫ。よって幅優先探索でも～51x51で十分ＯＫ。各探索で授業全部をスキャンするとしても51x51x50は余裕。

理論スキル、実践スキル、時間（月）、これまで受けた授業をＱｕｅｕｅに渡してぐるぐる回して、受けられる授業があれば片っ端から受けて枝を広げる。その時、その座標でより短く若い受講数・辞書順で到達していたらその枝は止める。両スキル目標達成したら、今までの最短受講数・辞書順を比べて更新する。

授業を受けるたびにintを加えていかなければいけないが、最初から最大個数の配列を用意しておいて、受講記録用配列（最大固定）と受講数の２つのメモライズを使えば楽。その代わり、返却値を返す時はSystem.arraycopyで整えなければならない。

• LinkedListを使え（一応）
• ゴールは（skillBound, skillBound）ではない。（>=skillBound, >=skillBound）のどこかの地点。到達チェックを毎回行って、到達したら最小値チェックをして返却候補に収めてしまえばよい。
• 動的配列を無理にmemしないで、固定配列memとインデックスmemの2つを使えばよい。
• 初期条件を確認。目標値０ならば授業を受けなくていいので{}を返さなければならない。（０，０）から始めるなら、到達チェックは最初にやらなければならない。