TopCoder SRM練習 - SRM 450 DIV1 Easy

2011年7月12日火曜日

昨日に続いて、少しずつやる。
今日やったのはOrdered Nim。

・AliceとBobの2人がゲームをしてる
・複数のヒープ(インデックスが振られている)のうち1つから、1つ以上の石を交互に取り出す
・あるヒープから石を取り出せる条件は、そいつよりインデックスの小さなヒープが全て空の場合だけ
・最初に取り出すのはAlice
・各ヒープに入ってる石の数は10億個以下
・お互いが最も効率的にゲームをプレイする場合、勝つのはAliceかBobか返せ

先日落としたトラウマ化しつつある問題と少々似てるところがある。いくつかケースを紙に書いてみて
・Aliceが必ず勝てる場合以外は、Bobが必ず勝てる(直感的にこうだけど未証明)
・n-1番目へたどり着いたら全部取って勝てるので、n-2(境界注意)までが勝負
・"Aliceが勝つかどうか"をn-2番目のヒープから逆順でたどって検証していけばよさげ
・あるヒープに石が最初から1個しかなければ、勝者判定をひっくり返す
・あるヒープに石が最初2個以上あれば、その次(ループ上はひとつ前)のヒープにある石が1個であれば勝者判定をひっくり返し、2個以上であればAliceの勝ち判定とする(総取りか1つ残すかのどちらかで、Bobに不利条件を押し付けられるから)
とたどり着いた。

テストケースを自前で増やしてやばそうなパターンを拾えるようにしたけれど、それでも抜けがあって一度failed system test。その後訂正し再提出して75.0pt(実際だったら0pt)。なかなか凹みますな。avg=205 / 正答率74%。この回なら文句なしに落ちてる。

public class OrderedNim {

 public String winner(int[] layout) {
  String ALICE = "Alice";
  String BOB = "Bob";
  if (layout.length == 1) {
   return ALICE;
  }

  boolean aliceWins = true;
  boolean oneStoneFollows = false;
  for (int i = layout.length - 2; 0 <= i; i--) {
   if (oneStoneFollows == true) {
    if (layout[i] == 1) {
     aliceWins = !aliceWins;
    }
    else {
     aliceWins = true;
     oneStoneFollows = false;
    }
   }
   else {
    if (layout[i] == 1) {
     aliceWins = !aliceWins;
     oneStoneFollows = true;
    }
   }
  }
  return aliceWins ? ALICE : BOB;
 }

}

"both players play optimally"な問題はまあまあ苦手だなぁ。