Topcoder SRM150 Div1 Level 1 InterestingDigits

問題

---

http://community.topcoder.com/stat?c=problem_statement&pm=1523&rd=4555

解法

---

まだ

コード

---

#include <bits/stdc++.h>
#include <stdint.h>
#include <sys/time.h>

class InterestingDigits {
public:
  std::vector<int> digits(int base) {
    int n = base - 1;
    std::vector<int> res;

    for(int i = 2; i < 30; ++i) {
      if( n % i == 0 ) {
        res.push_back(i);
      }
    }
    
    return res;
  }
};

Topcoder SRM149 Div1 Level 1 BigBurger

問題

---

http://community.topcoder.com/stat?c=problem_statement&pm=1648&rd=4550

解法

---

まだ

コード

---

#include <bits/stdc++.h>
#include <stdint.h>
#include <sys/time.h>

class  BigBurger{
public:
  int maxWait(std::vector<int> arrival, std::vector<int> service) {
    int end[64];
    int n = arrival.size();

    end[0] = arrival[0] + service[0];
    for(int i = 1; i < n; ++i) {
      end[i] = std::max(0, end[i-1] - arrival[i]) + arrival[i] + service[i];
    }

    int wait[64] = {};
    for(int i = 1; i < n; ++i) {
      wait[i] = std::max(0, end[i-1] - arrival[i]);
    }

    int res = wait[0];
    for(int i = 1; i < n; ++i) {
      res = std::max(res, wait[i]);
    }
    
    return res;
  }    
};

Topcoder SRM148 Div1 Level 1 CircleGame

問題

---

http://community.topcoder.com/stat?c=problem_statement&pm=1735&rd=4545

解法

---

0は飛び越えて，隣接する数の和が13になるものを0にしていく．

コード

#include <bits/stdc++.h>
#include <stdint.h>
#include <sys/time.h>

class CircleGame {
public:
  int cardsLeft(std::string deck) {
    int num[64];
    int n = deck.size();

    for(int i = 0; i < n; ++i) {
      switch( deck[i] ) {
      case 'A' :
        num[i] = 1; break;
      case '2' ... '9' :
        num[i] = deck[i] - '0'; break;
      case 'T' :
        num[i] = 10; break;
      case 'J' :
        num[i] = 11; break;
      case 'Q' :
        num[i] = 12; break;
      case 'K' :
        num[i] = 0; break;
      };
    }

    for(int i = 0; i < n; ++i) {
      for(int left = 0; left < n; ++left) {
        if( num[left] != 0 ) {
          int right;
          for(right = (left + 1) % n; num[right] == 0; right = (right + 1) % n) ;
          if( num[left] + num[right] == 13 ) {
            num[left] = num[right] = 0;
          }
        }
      }
    }
    
    int res = 0;
    for(int i = 0; i < n; ++i) {
      if( num[i] != 0 ) {
        res += 1;
      }
    }

    return res;
  }
};

Topcoder SRM147 Div1 Level 1 PeopleCircle

問題

---

http://community.topcoder.com/stat?c=problem_statement&pm=1225&rd=4540

解法

---

一旦すべての文字を'M'にしておく．
この状態で，問題文の順番通りに'M'を'F'にしていけばいい．
ただし，次に'F'にする場所を数えるときに，すでに'F'になっているところは飛ばす．
(すでに'F'になっている場所はそこまでの作業で消えるので)
ある場所を'F'にした次に'F'にする場所は，'F'の次の 'M'から，その'M'を含めてK個目の'M'なので，
K個目の'M'が次の'F'にする場所になる．
(最初の場所を合計人数-1にしておくと最初からK個数えればいいことになる)

例 Testcase 3

MMMMMMMMMM
123       
  |
MMFMMMMMMM
   123
     |
MMFMMFMMMM
      123
        |
MMFMMFMMFM
23       1
 |
MFFMMFMMFM
   12 3
      |
MFFMMFFMFM  ...答え

コード

---

#include <bits/stdc++.h>
#include <stdint.h>
#include <sys/time.h>

class PeopleCircle {
public:
  int n;
  char ans[64];
  int next(int i) {
    return (i + 1) % n;
  }
  int next_M(int i) {
    i = next(i);
    while( ans[i] != 'M' ) i = next(i);
    return i;
  }
  std::string order(int numMales, int numFemales, int K) {
    n = numMales + numFemales;

    for(int i = 0; i < n; ++i) ans[i] = 'M';

    int i = n - 1;
    for(int j = 0; j < numFemales; ++j) {
      for(int k = 0; k < K; ++k) {
        i = next_M(i);
      }
      ans[i] = 'F';
    }

    return std::string(ans, n);
  }
};

Topcoder SRM146 Div1 Level 1 RectangularGrid

解法

---

数える長方形の幅をw，高さをhとすると，
その大きさの長方形の個数は(width - w + 1) * (height - h + 1)
これを2重ループで正方形でないもの(w != h)を数えればいい

コード

---

#include <bits/stdc++.h>
#include <stdint.h>
#include <sys/time.h>

class RectangularGrid {
public:
  long countRectangles(int width, int height) {
    long res = 0;

    for(int w = 1; w <= width; ++w) {
      for(int h = 1; h <= height; ++h) {
        if( w != h ) {
          res += (width - w + 1) * (height - h + 1);
        }
      }
    }

    return res;
  }
};

Topcoder SRM145 Div1 Level 1 Bonuses

解法

---

問題文通りそれぞれの人のポイントの割合を求めた後，
あまった分をpointsの値の大きい人から足していく．
pointsの各値は1から500なので，2重ループにするとたぶん楽

std::accumulateを初めて使ってみた

コード

---

#include <bits/stdc++.h>
#include <cstdint>
#include <sys/time.h>

class Bonuses {
public:
  std::vector<int> getDivision(std::vector<int> points) {
    int total = std::accumulate(points.begin(), points.end(), 0);
    int n = points.size();
    int res[64];

    for(int i = 0; i < n; ++i) {
      res[i] = points[i] * 100 / total;
    }
    
    int remainder = 100 - std::accumulate(res, res + n, 0);
    for(int i = 500; i >= 0; --i) {
      for(int j = 0; j < n and 0 < remainder; ++j) {
        if( points[j] == i ) {
          res[j] += 1;
          remainder -= 1;
        }
      }
    }

    return std::vector<int>(res, res+n);
  }    
};

Topcoder SRM144 Div1 Level 1 BinaryCode

解法

---

最初の数字から順番に決めていく
答えに0と1以外が入ってたら"NONE"
問題ないならそれが答えになる

コード

---

#include <bits/stdc++.h>
#include <stdint.h>
#include <sys/time.h>

class BinaryCode {
public:
  std::vector<std::string> decode(std::string message) {
    std::vector<std::string> res;
    res.push_back(solve(message, 0));
    res.push_back(solve(message, 1));
    return res;
  }
  std::string solve(std::string message, int first) {
    int ans[64] = {};
    int n = message.size();
    std::string res;

    ans[1] = first;
    for(int i = 0; i < n; ++i) {
      ans[i+2] = message[i] - '0' - ans[i] - ans[i+1];
    }

    for(int i = 1; i <= n; ++i) {
      if( not ( ans[i] == 0 or ans[i] == 1 ) ) {
        return "NONE";
      }
    }
    if( ans[n + 1] != 0 ) {
      return "NONE";
    }

    for(int i = 1; i <= n; ++i) {
      res += (char)ans[i] + '0';
    }
    return res;
  }
};