Hatena::Grouptopcoder

cou929のTopCoder日記

2009-11-21

SRM453 div2

09:47

前回のsrmは,tcのサーバがダウンしノーコンテストになりました.本番中は重すぎて250しか開けなかったので,あとでpractice roomでやった記録です.

Easy - TheTournamentDivTwo

勝ち点が,勝つと2点,ドローで1点,負けると0点与えられるトーナメント.各チームの勝ち点が与えられるので,最小で何回の試合が行われたかを返す.あり得ない点数の場合は-1.

はじめに全てのチームの点数を2で割り,何勝したかを調べます.勝ち点が奇数のチームは一試合ドローだったと考えられるので,カウントしておいてあとで結果に足し込みます.点数が正しいかどうかは,奇数点のチームが偶数か奇数かでわかります.

class TheTournamentDivTwo {
public:
  int find(vector <int> points)
  {
    int ret = 0;
    int zeros = 0;

    for (int i=0; i<points.size(); i++)
      {
        ret += points[i]/2;
        zeros += points[i]%2;
      }

    if (zeros%2 == 1)
      return -1;
    else
      return ret + zeros/2;
  }
};

Medium - TheBasketballDivTwo

バスケットのトーナメント.各チーム同士はホーム・アウェイで2試合戦う.必ず勝敗がつき,ドローはなし.この条件の下で,現在の試合結果が与えられる.残りの試合結果は任意に決められると仮定したとき,優勝するチームが勝った回数の最小値を求める.

チーム数は高々5チーム.試合は勝つ・負けるの2通りしかない.ワーストケースは5チームが一度もまだ試合をしていない状態で,その場合20試合行われる.この20試合について,全ての可能性を計算した場合,2^20 = 1048576 なので,bruto-forceで行けそうです.再帰を使って全ての状態を探索しました.

vector <string> tbl;
int ret;
int cc = 0;

int r(int x, int y)
{
  if (x == (int)tbl.size())
    {
      int win = 0;
      for (int i=0; i<tbl.size(); i++)
        {
          int sum = 0;
          for (int j=0; j<tbl.size(); j++)
            {
              if (tbl[i][j] == 'W')
                sum++;
              if (tbl[j][i] == 'L')
                sum++;
            }
          win = max(win, sum);
        }
      ret = min(ret, win);
    }
  else if (y == tbl.size())
    {
      r(x+1, 0);
    }
  else if (tbl[x][y] != '?')
    {
      r(x, y+1);
    }
  else
    {
      tbl[x][y] = 'W';
      r(x, y+1);
      tbl[x][y] = 'L';
      r(x, y+1);
      tbl[x][y] = '?';
    }
  cc++;
  return 0;
}

class TheBasketballDivTwo {
public:
  int find(vector <string> table)
  {
     tbl = table;
     ret = INT_MAX;

     r(0, 0);

     return ret;
  }
};

Hard - TheSoccerDivTwo

現実のサッカーリーグのように,勝つと勝ち点3,ドローで勝ち点1,負けると0というトーナメントがある.トーナメントの全ての試合が終わったあと,勝ち点に応じて順位が決まる.勝ち点がタイの場合は,インデックスが低いチームを上位とする.現在の得点(この得点はvalidであることを保証)が与えられるので,残りの試合の勝ち負けを自由に決められると仮定すると,チーム0は最大で何位になるか.

問題文が理解できませんでした.残りの試合数を何回でもできるとすると,100%チーム0が優勝ですし,テストケースから残り1節(各チーム1試合ずつ)ぽいなあと予想したんですが,問題文にそのような記述が見つけられませんでした.またあとで読み直して最チャレンジします.