Hatena::Grouptopcoder

yowa の TopCoder 日記

TopCoder yowa / twitter: @yowa

2010-07-29

SRM 477 DIV2

03:00 | SRM 477 DIV2 - yowa の TopCoder 日記 を含むブックマーク はてなブックマーク - SRM 477 DIV2 - yowa の TopCoder 日記

今回は開始に間に合った。

250 VacationTime

N日の期間の中でK日の連続休暇を取りたいけど、たまに会議があるので、休暇にかぶる会議は移動させなきゃいけない。移動させる会議数の最小値は?

N<=1000,会議数<=50なので、二重ループで問題なし。

ただ会議のリストの構造を勘違いしてたのと(ビットマップだとおもってた)、境界条件がややこしいのと、日付が1-originなのを忘れてたのと、もろもろで20分くらい時間がかかった。

配点的に、前回の最易問題が300で今回が250なのは逆じゃね?とか思った。

#include <vector>
#include <string>
#include <iostream>
using namespace std;
class VacationTime
{
public:
  int bestSchedule(int N, int K, vector <int> workingDays)
  {
    int sum[2000];
    int min = 0;

    for (int i=1; i<=N; i++)
      sum[i] = 0;

    for (int i=0; i<workingDays.size(); i++)
      for (int j=0; j<K; j++)
	if (workingDays[i]-j >= 1)
	  sum[workingDays[i]-j]++;

    min = sum[1];
    for (int i=1; i<=N-K+1; i++) {
      if (sum[i] < min)
	min = sum[i];
    }

    return min;
  }
};

500 Islands

陸地と海の地図が与えられるから、海岸線の長さを計算してね。地図はHEXタイル(各区画は正六角形)だよ。

奇数行目が半キャラ右に動く、と。

 ##.       ■■_
 #..    ■__
 ..#       __■

上下左右とは必ず隣接してて、偶数行目なら左斜めの2マス、奇数行目なら右斜めの2マスとも隣接することになる。

#include <vector>
#include <string>
#include <iostream>
using namespace std;
class Islands
{
public:

#define IS_WATER(x,y) ((x)>=0 && (x)<w && (y)>=0 && (y)<h && kingdom[y][x]=='.')

  int beachLength(vector <string> kingdom)
  {
    int len = 0;
    int h, w;
    h = kingdom.size();
    w = kingdom[0].size();

    for (int y=0; y<h; y++) {
      int bias = (y%2 == 0) ? -1 : 1;

      for (int x=0; x<w; x++) 
	if (kingdom[y][x] == '#') {
	  if (IS_WATER(x-1, y)) len++;
	  if (IS_WATER(x+1, y)) len++;
	  if (IS_WATER(x, y-1)) len++;
	  if (IS_WATER(x, y+1)) len++;
	  if (IS_WATER(x+bias, y+1)) len++;
	  if (IS_WATER(x+bias, y-1)) len++;
	}

    }
    return len;
  }
};

1000 CarelessSecretary

ドジっ子秘書に N 通の手紙を送らせたところ、全部同じ文面だと思っててきとーに送っちゃったので、あわてて K 人に確認したら全員が「宛先間違ってたよ」とのこと。こんなことになる組合せの数を答えてね。(mod 1000000007)

頭からなめて行って、自分宛の手紙が既に消費されてるかどうかで場合の数が変わってくるので、2次元DPで、K人中の何人を選んでるかもメモればいいんじゃなかろうかと思ってコードを書いたものの、サンプル通らず考え直してる間に時間切れ。

結果

250VacationTimeAC
500IslandsAC
1000CarelessSecretaryOpened

Rating: 1170 -> 1263(DIV1に昇格)