TopCoder SRM390 Div2 250Pts

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

あなたの幼い息子が左手で数を数えている。親指から小指へ向かって順に数えていく。小指まで数えたら親指へ向かって逆方向に数えていく。これを目的の数を数える前で行う。途中で数える指を飛ばしたりはしないものとする。例えば、10まで数えるとしたら、息子さんは親指、人差し指、中指、薬指、小指、薬指、中指、人差し指、親指、人差し指の順で数える。悲しいことに、息子さんの指の1本はケガをしており、その指については限られた回数しか数えることができない。指には1～5までそれぞれ親指から小指に割り当てられている。weakFingerというケガをしている指を表す数字と、maxCountというケガをしている指を数えられる回数の上限が与えられたとき、数え続けることのできる回数の最大値を求めよ。もし数えはじめることができないときは0を返すようにせよ。

私の解答はこちら。

public class FingerCounting {

 public int maxNumber(int weakFinger, int maxCount) {
  int nCount = 0; // ケガをしている指を数えた回数
  int ret = 0; // 指を数えた回数の合計
  int numFinger = 0; // 現在注目している指の番号
  boolean countUp = true; // 親指から小指に向かって数えているときにtrue
  while( true ){
   if( numFinger == 5 ){ // 小指まで数えたら逆走
    countUp = false;
   }else if( numFinger == 1){ // 親指から小指へ向かって数える
    countUp = true;
   }
   numFinger = countUp ? numFinger+1 : numFinger-1; // 次の指へ進める
   if( numFinger == weakFinger ){ // もしケガをしている指なら
    if( nCount == maxCount ) break; // 数えられる回数の上限なら終了
    nCount++; // そうでなければケガした指のカウントした回数を1増やす
   }
   ret++;
  }
  return ret;
 }

}

得点は225.38/250、1回のsubmitでシステムテストクリア。中央値は約170点。printしながら確認していたら、maxCountが大きいときに時間的に間に合わなくなったので、結構ギリギリです。上の問題はO(n)のアルゴリズムで解いてますが、うまくやればO(1)で答えが出そうな気もします。