TopCoder SRM435 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文についておおまかに説明する。

ケイトは一直線のコースの初めに、スキーの板をつけて立っている。コースはn個の同じ長さの部分からなる。pathFrictionという、コースの摩擦を表す文字列が与えられる。pathFrictionのi文字目は1から9の整数であり、コースのi番目の地域の摩擦を表している(以後、添字は0から始まるとする)。この問題では、ケイトのスキー板を1つの板として扱う。スキー板は同じ長さのm個の部分からなる。スキー板の摩擦はskiFrictionというi番目の文字が1から9という文字列でそれぞれ与えられる。これらはスキー板のi番目の位置を表している。最初に、ケイトはスキー板のi番目の部分がパスのi番目の部分に触れるように立っている。次に、ケイトはスキー板の(m-1)番目の部分がパスの(n-1)番目に触れるまで前に進む。1つの部分だけ前に進むときは、ケイトは一番遅い速度で前に移動する。1つの部分だけ前にすすむのにかかる時間というのは、スキー板の部分の数と現在いるコースの摩擦の合計で表される。ケイトがコースの最後にたどり着くまでにすべる時間の合計を返すメソッドを作成せよ。

例えば、skiFriction="45"、pathFriction="15196"であるとき、返す値は33になる。これは次のようにして計算される。スキー板は4、5という部分を持つ。板はコースは1、5という位置にある。ここで4+1、5+5というそれぞれの位置に対応させるようにして和をとる。すると、最大値は10なので、1つ前に進むのに10秒かかるということになる。次に進むと、コースは5、1になる。4+5、5+1と同様に対応する位置で和をとると最大値は9である。最後のステップでは、4+1と5+9を比較して14秒移動にかかるということになる。次のステップではpathFrictionの最後の文字を使うことになるので、移動は終了となる。以上より10+9+14=33が導出されることになる。

私の解答はこちら。

public class SkiFriction {

 public int bestPosition(String skiFriction, String pathFriction) {
  int n = 0;
  for( int i=0 ; i<pathFriction.length() - skiFriction.length() ; i++ ){
   int max = -1;
   for( int j=0 ; j<skiFriction.length() ; j++ ){
    int s = skiFriction.charAt(j) - '0';
    int p = pathFriction.charAt(i+j) - '0';
    max = Math.max(max, s+p);
   }
   n += max;
  }
  return n;
 }

}

得点は222.02/250、1回のsubmitでシステムテストクリア。私にとっては実装は楽でしたが、読解がしんどい一問でした。問題設定が現実的でなく、想像しづらいためかと思います。