Div2から抜けだしたいsuztomoの日記

OrderedNim

20:20

後ろから見ていけばいい自分今日冴えてる！！！１

class OrderedNim {
public:
  string winner(vector <int> layout) {
    vector<string> rets;
    rets.push_back("Alice");
    rets.push_back("Bob");
    int a = 1;
    int n = layout.sz;
    REP(i, layout.sz) {
      int t = layout[n - i - 1] > 1 ? 2 : 1;
      if (a == 0) {
        if (t > 1) {
          a = 0;
        } else {
          a = 1;
        }
      } else {
        a = 0;
      }
    }
    return rets[a];
  }
};

とか思ったら、両方が最も優れた戦略をとるのなら前から見ていって先に選択肢があるほうが勝つに決まってるじゃないですか。

StrangeComputer

20:20

シンプルなものをシンプルに書く。

class StrangeComputer {
public:
  int setMemory(string mem) {
    int ret = 0;
    char p = '0';
    REP(i, mem.sz) {
      if (p != mem[i]) {
        ret++;
        p = mem[i];
      }
    }
    return ret;
  }
};

天下一プログラマーコンテスト決勝2問目

10:14

ナンクロ．

#define _GLIBCXX_DEBUG
#include "cout.h"
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <cmath>
#include <queue>
#include <list>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
#define Fill(a, b) memset((a), (b), sizeof(a))
#define REP(a, b) for (size_t (a) = 0; (a)<(size_t)(b); ++(a))
#define sz size()
#define Tr(c, i) for(typeof((c).begin()) i= (c).begin(); (i) != (c).end(); ++(i))
#define All(c) (c).begin(), (c).end()
#define Present(c, x) ((c).find(x) != (c).end()) // for Map or Set
#define CPresent(c, x) (find(All(c), x) != end()) // for vector


int board1[][11] = {
  {1, 2, 12, 15, 17, 3, 15, 12, 18, 19, 5},    // tate
  {10, 12, 11, 6, 16, 2, 3, 17, 3, 11, 9},
  {12, 6, 4, 3, 2, 12, 18, 19, 5},
  {15, 2, 5, 12, 17, 7, 2},
  {2, 5, 17, 3, 2, 5, 6},
  {1, 2, 3, 4, 5},
  {6, 7, 8, 9, 10},
  {5, 2, 7, 6, 5},
  {5, 2, 5, 15, 17},
  {12, 6, 7, 2, 5},
  {17, 10, 7, 11, 9},
  {7, 2, 6, 5, 2},
  {18, 8, 19, 9, 5},
  {15, 10, 5, 16},
  {13, 12, 2, 6},
  {2, 8, 14, 10},
  {11, 5, 12, 2},
  {12, 11, 17, 3},
  {2, 5, 14, 17},
  {9, 5, 12, 2},
  {14, 10, 8, 11},
  {2, 8, 11},
  {2, 12, 13},
  {1, 5, 12},
  {3, 15,5},
  {5, 2, 12},
  {7, 8, 2},
  {19, 12, 6},
  {14, 5, 5},
  {9, 8, 11},
  {7, 16, 5},
  {2, 3, 18},
  {5, 2, 2},
  {17, 5, 5},
  {8, 14, 5},
  {6, 13, 5},
  {2, 12, 17},
  {9, 5, 17},
  {2, 13, 5},
  {7, 2, 5},
  {8, 1},
  {9, 7},
  {6, 7},
  {10, 3},
  {3, 11},
  {12, 14},
  {12, 11},
  {18, 5}
};
int board_size;
vector<string> dict[12];



vector<string> search(char answer[], int n, int s) {
  vector<string> ret;
  for (int i=0; i < (int)dict[s].sz; ++i) {
    // get i-th string whose length is s
    string t = dict[s][i];
    bool ok = true;
    for (int j=0; j<s; ++j) {
      char c = answer[board1[n][j]];
      if (c != 0 && c != t[j]) {
        ok = false;
        break;
      }
    }
    if (ok) // put t if it is along with answer[]
      ret.push_back(t);
  }
  return ret;
}

void output(char answer[20]) {
  REP(i, 20) if (i >= 1)
      cout << i << " : " << (answer[i] == 0 ? '-' : answer[i]) << endl;
}

bool is_unique(char answer[]) {
  REP(i, 20) if (i>0) {
    for (size_t j=i+1; j<20; ++j) {
      if (answer[i] && answer[i] == answer[j])
        return false;
    }
  }
  return true;
}
vector< vector< int > > board;

/*
  Fill answer[] using board[n].
 */
void solve(char answer[], int n) {
  if (n >= board_size) {    // last operation
    output(answer);
    return;
  }
  int s = board[n].size();

  char ans[20];
  vector<string> r = search(answer, n, s);
  REP(i, r.sz) {
    string t = r[i];
    memcpy(ans, answer, sizeof(ans));
    REP(j, t.sz) {
      ans[board[n][j]] = t[j];
    }
    if (is_unique(ans))
      solve(ans, n+1);
  }
}



int main() {
  string s;
  ifstream cin("english.dic");
  while(cin >> s) if (s.sz < 12) {
    transform(All(s), s.begin(), (int (*)(int))std::toupper);
    dict[s.sz].push_back(s);
  }
  char answer[20]; // 1 - 19

  REP(i, 48) { // copy board1
    vector<int> t;
    REP(j, 11) {
      if (board1[i][j] == 0)
        break;
      t.push_back(board1[i][j]);
    }
    board.push_back(t);
  }
  board_size = board.sz;
  Fill(answer, 0x0);
  solve(answer, 0);
}

// END CUT HERE

SRM443 CirclesCountry

21:42

片方しか入ってない輪を探す．

#define Fill(a, b) memset((a), (b), sizeof(a))
#define REP(a, b) for (size_t (a) = 0; (a)<(size_t)(b); ++(a))
#define FOR(a, b, c) for (size_t(a) = (b); (a) < (size_t)(c); ++(a))
#define sz size()

class CirclesCountry {
public:
  int leastBorders(vector <int> X, vector <int> Y, vector <int> R, int x1, int y1, int x2, int y2) {
    int ret = 0;
    vector<bool> containA(X.sz, false);
    vector<bool> containB(X.sz, false);
    int rounds[2] = {0, 0};
    REP(i, X.sz) {
      if ((x1-X[i])*(x1-X[i])+(y1-Y[i])*(y1-Y[i]) < R[i] * R[i]) {
        containA[i] = true;
      }
      if ((x2-X[i])*(x2-X[i])+(y2-Y[i])*(y2-Y[i]) < R[i] * R[i]) {
        containB[i] = true;
      }
      if (containA[i] && !containB[i]) {
        rounds[0] += 1;
      }
      if (containB[i] && !containA[i]) {
        rounds[1] += 1;
      }
    }
    ret = rounds[0] + rounds[1];
    return ret;
  }
};

SRM442 EqualTowers

00:52

答えをがんばって解読して自分で書いたけれど#3が通らない．．．

#define Fill(a, b) memset((a), (b), sizeof(a))
#define REP(a, b) for (size_t (a) = 0; (a)<(size_t)(b); ++(a))
#define FOR(a, b, c) for (size_t(a) = (b); (a) < (size_t)(c); ++(a))
#define sz size()
class EqualTowers {
public:
  int height(vector <int>);
};
int b[50][500001];
int EqualTowers::height(vector <int> bricks) {
  int sum = 0;
  int N = bricks.sz;
  Fill(b, 0xFF);
  b[0][0] = 0;
  REP(i, N) {
    if (i > 0) memcpy(b[i], b[i-1], sizeof(b[i]));
    if (i == 0) {
      b[0][bricks[0]] = bricks[0];
    }
    else REP(j, sum+1) {

        if (b[i-1][j] >= 0) {
          int diff[2] = {abs(b[i-1][j] + bricks[i]),
                         abs(b[i-1][j] - bricks[i])};
          for(int k=0; k<2; ++k) {
            b[i][diff[k]] >?= b[i-1][j] + bricks[i];
          }
        }
      }
    sum += bricks[i];
  }
  if (b[bricks.sz-1][0] > 0) return b[bricks.sz-1][0] / 2;
  return -1;
}

間違っていたので直したが...

#define Fill(a, b) memset((a), (b), sizeof(a))
#define REP(a, b) for (size_t (a) = 0; (a)<(size_t)(b); ++(a))
#define FOR(a, b, c) for (size_t(a) = (b); (a) < (size_t)(c); ++(a))
#define sz size()
class EqualTowers {
public:
  int height(vector <int>);
};
int b[50][500001];
int EqualTowers::height(vector <int> bricks) {
  int sum = 0;
  int N = bricks.sz;
  Fill(b, 0xFF);
  b[0][0] = 0;
  REP(i, N) {
    if (i > 0) {
      memcpy(b[i], b[i-1], sizeof(b[i]));
    }
    if (i == 0) {
      b[0][bricks[0]] = bricks[0];
    }
    else REP(j, sum+1) {
        if (b[i-1][j] >= 0) {
          int diff[2] = {abs((int)j + bricks[i]),
                         abs((int)j - bricks[i])};
          for(int k=0; k<2; ++k) if (b[i][diff[k]] < b[i-1][j] + bricks[i]) {
            b[i][diff[k]] = b[i-1][j] + bricks[i];
          }
        }
      }
    sum += bricks[i];
    //memcpy(b[i+1], b[i], sizeof(b[i]));
  }
  if (b[bricks.sz-1][0] > 0) return b[bricks.sz-1][0] / 2;
  return -1;
}

SIGKILLがとんでくるよ．．．

sigkillは大きすぎる領域をグローバルに確保しようとしたら起きるらしい． @nodchipさんに教えてもらった．

2つの配列だけあればいいのでこれでおk.

#define Fill(a, b) memset((a), (b), sizeof(a))
#define REP(a, b) for (size_t (a) = 0; (a)<(size_t)(b); ++(a))
#define FOR(a, b, c) for (size_t(a) = (b); (a) < (size_t)(c); ++(a))
#define sz size()
class EqualTowers {
public:
  int height(vector <int>);
};
int b[2][500001];
int EqualTowers::height(vector <int> bricks) {
  int sum = 0;
  int N = bricks.sz;
  Fill(b, 0xFF);
  b[0][0] = 0;
  REP(i, N) {
    if (i == 0) {
      b[1][bricks[0]] = bricks[0];
    }
    else REP(j, sum+1) {
        if (b[0][j] >= 0) {
          int diff[2] = {abs((int)j + bricks[i]),
                         abs((int)j - bricks[i])};
          for(int k=0; k<2; ++k) if (b[1][diff[k]] < b[0][j] + bricks[i]) {
            b[1][diff[k]] = b[0][j] + bricks[i];
          }
        }
      }
    sum += bricks[i];
    memcpy(b[0], b[1], sizeof(b[1]));
  }
  if (b[1][0] > 0) return b[1][0] / 2;
  return -1;
}

と思ったら．

{{90000, 60000, 60001, 60000, 60001}}

Expected:

120001

Received:

• 1

これが通らないよ．．．

1つ目の要素が必ず使うようになっていたのを修正したら通った．

#define Fill(a, b) memset*1

#define REP(a, b) for (size_t (a) = 0; (a)<(size_t)(b); ++(a))

#define FOR(a, b, c) for (size_t(a) = (b); (a) < (size_t)(c); ++(a))

#define sz size()

class EqualTowers {

public:

int height(vector <int>);

};

int b[2][500001];

int EqualTowers::height(vector <int> bricks) {

int sum = 0;

int N = bricks.sz;

Fill(b, 0xFF);

b[0][0] = 0;

REP(i, N) {

if (i == 0) {

b[1][bricks[0 = bricks[0];

b[1][0] = 0;

}

else REP(j, sum+1) {

if (b[0][j] >= 0) {

int diff[2] = {abs((int)j + bricks[i]),

abs((int)j - bricks[i])};

for(int k=0; k<2; ++k) if (diff[k] <= 500000 &&

b[1][diff[k < b[0][j] + bricks[i]) {

b[1][diff[k = b[0][j] + bricks[i];

}

}

}

sum += bricks[i];

memcpy(b[0], b[1], sizeof(b[1]));

}

if (b[1][0] > 0) return b[1][0] / 2;

return -1;

}

SRM442 SimpleWordGame

23:01

class SimpleWordGame {
public:
  int points(vector <string> player, vector <string> dictionary) {
    int ret = 0;
    set<string> in_dict;
    REP(i, player.sz) {
      if (count(dictionary.begin(), dictionary.end(), player[i]) >= 1) {
        in_dict.insert(player[i]);
      }
    }

    Tr(in_dict, i) {
      ret += (*i).sz * (*i).sz;
    }
    return ret;
  }
};

dictionaryはdistinctなんだからそっちをメインにしてまわせばsetを使わなくてもいいということに気づくべき．

SRM442 UnderPrimes

22:47

100000をひとつひとつ素因数を数えていく．

その際, 2からその数までの数で割っていって時間切れ．

素数だけを見て割っていけば時間内でおさまる．

計算量は同じのように感じたんだけどなぁ．2からNまでの素数をたどっていく場合の計算量ってなんだろ．

int is_prime[100000];
vector <int> primes;

class Underprimes {
public:
  int primecount(int A) {
    int k = 0;
    int t = 0;
    if (is_prime[A])
      return 1;
    int limit = A / 2;
    while(primes[k] <= A) {
      if (A % primes[k] == 0) {
        A /= primes[k];
        ++t;
      } else {
        ++k;
      }
    }
    return t;
  }


  void sieve_of_eratosthenes(int n) {
    is_prime[0] = is_prime[1] = 0;
    for (int i=2; i<n; i++)
      if (is_prime[i]) {
        for (int j=i*2; j<n; j+=i)
          is_prime[j] = 0;
        primes.push_back(i);
      }
  }

  int howMany(int A, int B) {
    int ret = 0;
    REP(i, 100000) is_prime[i] = 1;
    sieve_of_eratosthenes(100000);
    for (int i = A; i <= B; ++i) {
      int pc = primecount(i);
      if (is_prime[pc]) {
        ++ret;
      }
    }
    return ret;
  }
};

SRM440 Div1 500 MazeWandering

00:57

期待値 = 親の期待値 + 子孫の数*2 + 1 になっているような予感