SRM 500 Div 1 - Problem 250 MafiaGame

問題
SRM 500 Div 1 - Problem 250 MafiaGame
TopCoder Statistics - Problem Statement

使用言語
C++

方針
・最も投票された人にのみ注目
・N人の人が残る候補者にどう投票するかでループ

所感
・問題文理解できなかったり，スペルわからなくなったり，英弱の極みという感じだった．
・複雑に考えちゃいけない問題

コード

vector<int> vote(555, 0);

class MafiaGame {
    public:
    double probabilityToLose(int N, vector<int> decisions) {
      int size = decisions.size();
      for (size_t i = 0; i < size; i++) {
        vote[decisions[i]]++;
      }

      //最も投票された回数
      int maxvote = *max_element(vote.begin(), vote.end());
      //最も投票された人の人数
      int maxnum = count(vote.begin(), vote.end(), maxvote);

      //最も投票された人でも1票ということは，全員1票で無限ループ
      if (maxvote == 1 && N != 1) return 0.0;
      //単独で最多投票獲得数ならばその人が敗者決定
      if (maxnum == 1) return 1.0;

      //ここで候補を絞る
      //N票しか存在しないので，候補者がmaxnum以上になることはない
      //確実に入れる人の数は同じなので，全員ランダムとみなして問題ない
      //一人になったら終了
      int candidate = maxnum;
      while (candidate != 1) {
        //次の投票数が最多の人の人数を計算
        candidate = N % candidate;
        //(mod 0)==投票数が最多の人の人数が変化しない==無限ループ
        if (candidate == 0) return 0.0;
      }

      //maxnum人の中誰が候補者になっておかしくなかった．
        return 1.0 / maxnum;
    }
};

主に要約など参考：
Top Coder Single Round Match 500 Div1 - 練習帳 - TopCoder部

ABC097-C(12問目)

問題
AtCoder Beginner Contest 097 C - K-th Substring
C: K-th Substring - AtCoder Beginner Contest 097 | AtCoder

使用言語
C++

方針
・k文字以下の文字列作りまくる
→木にぶち込む
→k番目出力

所感
・setディスられてたの見たけど，重複可なの逆に便利

コード

int main()
{
  string s;
  int K;
  set<string> S;

  cin>>s>>K;

  int size = s.length();

  for (int i = 0; i < size; i++) {
    string tmp;
    for (int j = 0; j < 5 && j + i < size; j++) { //多分ここ5じゃなくてkでもいける
      tmp = s.substr(i, j+1);
      S.insert(tmp);
      //cout<<tmp<<S.size()<<endl;
    }
  }


  set<string>::iterator itr = S.begin();
  for (int i = 0; i < K - 1; i++) itr++;

  cout<<(*itr)<<endl;

  return 0;
}

三年目の初学者(11問目)

問題
Topcoder Single Round Match 620 Round 1 - Division I, Level One
TopCoder Statistics - Problem Statement

使用言語
C++

方針
・大きいところから、一個ずつ値を減らしていく。
(X, Y) -> (X-Y, Y) (X >= Y の時)

・一致したら終了（これ以下の値の数字の組も題意を満たすかもしれないが、x+yの最大値を求める問題なので、これで十分）

所感
・0になった時の処理が少し面倒くさいです。
・文字通りの逆転の発想。

コード

class PairGame {
    public:
    int maxSum(int a, int b, int c, int d) {
      while (a != c || b != d) {
        if ((a == 0 || b == 0) && (c == 0 || d == 0)) break;
        int maxab, maxcd;

        if (a == 0 || b == 0) maxab = 0;
        else maxab = max(a, b);
        if (c == 0 || d == 0) maxcd = 0;
        else maxcd = max(c, d);

        if (maxab >= maxcd) {
          if (a >= b) a -= b;
          else b -= a;
        } else {
          if (c >= d) c -= d;
          else d -= c;
        }
      }
        return a == c && b == d ? a + b : -1;
    }
};

三年目の初学者(10問目)

問題
Topcoder Single Round Match 619 Round 1 - Division I, Level One
TopCoder Statistics - Problem Statement

使用言語
C++

方針
まず、
1発でLOSEする状態を考える。初期で
{n1, n2} (数字2つ以下)
{1, 1, 1, ... , 1} (すべて1)
となるとき。

重要なのは「分割」するということなので、各numberにおいて重要なのは、2以上であるかどうか。
分割したものは、また別のnumberに加えるということなので、
{n, 1, 1, ... , 1} (n>=2)
というデータセットだとしても、次の操作で
{0, m1, m2, 1, ... , 1} (mi>=2)
となり、分割が続けられる。

WINする状況とは、Shinyの回で
{n1, n2, n3, 0, 0, ... , 0}
となる状況である。

{n1, n2, n3, n4, 0, 0, ... , 0} ではLOSE
{n1, n2, n3, n4, n5, 0, 0, ... , 0} ではWIN
.
.
.
(n>=1)

と、帰納的に奇数でWIN、偶数でLOSEであるとわかる。
って感じ。

所感
・頭やわらかゲー
・紙に書くの大切

コード

class SplitStoneGame {
    public:
    string winOrLose(vector<int> number) {
      if (number.size() <= 2 || number.size() % 2 == 0 ||
      number[*max_element(number.begin(), number.end())] == 1)
        return "LOSE";
      else return "WIN";
    }
};

三年目の初学者(9問目)

問題
AtCoder Beginner Contest 092 C - Traveling Plan
C: Traveling Plan - AtCoder Beginner Contest 092 | AtCoder

使用言語
C++

方針
・本来の値段をまず求めて、そこから値段を増減させる。
・計算量的にもこれがベスト

所感
・すぐに解きたい問題だったが、時間かかった
・添字大事。

コード

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define INF 1e9

int solve(int a[], int all_payment, int i)
{
  int ans = all_payment;

  ans += max(a[i-1], a[i+1]) - min(a[i-1], a[i+1]);
  ans -= max(a[i-1], a[i]) - min(a[i-1], a[i]);
  ans -= max(a[i], a[i+1]) - min(a[i], a[i+1]);

  return ans;
}

int main()
{
  int n, tmp, all_payment = 0;
  cin>>n;

  int a[n+2];
  a[0] = 0; a[n+1] = 0;
  FOR(i,1,n+1) {
    cin>>a[i];
  }

  REP(i,n+1) all_payment += max(a[i], a[i+1]) - min(a[i], a[i+1]);

  FOR(i,1,n+1) {
    cout<<solve(a, all_payment, i)<<endl;
  }

  return 0;
}

三年目の初学者(8問目)

問題
AtCoder Beginner Contest 093 D - Worst Case
D - Worst Case

使用言語
C++

方針
・100マス計算の表みたいな感じで行けるものだと思っていたが、細かいところができない。
・解説（https://img.atcoder.jp/arc094/editorial.pdf）を参考にした。下の通りに考えると判りやすい。（丸が最大となるときの候補の一つ）

所感
・簡単そうに見えて難しそうなやつだと思ったら、やっぱりそうだった。
・実装はクソ楽。
・結構力作の解説のつもり。
・桁落ち、負の処理、根号の処理を気をつけたい。

コード

#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define INF 1e9

typedef long long ll;
typedef unsigned long long ull;

void solve(ll a, ll b)
{
  if (a > b) swap(a, b);
  //常に a <= b

  if (b - a <= 1) {
    cout<<2 * (a - 1)<<endl;
  } else {
    ll c = (int) sqrt(a * b);
    if (c * c == a * b) c--;

    if (c * (c + 1) >= a * b) {
      cout<<2 * (c - 1)<<endl;
    } else {
      cout<<2 * c - 1<<endl;
    }
  }
}


int main(){
  int q;
  cin>>q;

  ll a[q], b[q];
  REP(i,q) cin>>a[i]>>b[i];

  REP(i,q) solve(a[i], b[i]);

  return 0;
}

三年目の初学者(7問目)

問題
topcoder SRM 602 div1 easy
TopCoder Statistics - Problem Statement

使用言語
C++

方針
・全探索
(・dp)

所感
・いけるもんだと思っていた。実行するまでは

問題点と解決案(解決してない)
・O(2^n)で大変
・一部ケースでTLEになったため、残りの全てのコンテストで勝ったとしても2200を超えない(brown coderにならない)場合はすぐに0を返すようにした。
・実行時間が少し減少したが、一部TLEのまま
・できたら追記します

コード

//status: true->brown, false->ciel
int cc (int rate, int i, vector<int> D, int size, bool status, vector<int> dp)
{
  if (i == size) return 0;

  if (status) {
    return (rate - D[i] < 2200)
            ? cc(rate - min(rate, D[i]), i+1, D, size, false, dp) + 1 : -INF;
  } else {
    if (rate + dp[i] < 2200) return 0;

    int r = rate + D[i];
    bool status_p = (r >= 2200);
    return max(cc(r, i+1, D, size, status_p, dp) + (int) status_p,
            cc(rate - min(rate, D[i]), i+1, D, size, false, dp));
  }
}

class TypoCoderDiv1 {
    public:
    int getmax(vector<int> D, int X) {
      int size = D.size();

      vector<int> dp(51, 0);
      for (int i = size - 1; i >= 0; i--) {
        dp[i] = dp[i+1] + D[i];
      }

        return cc(X, 0, D, size, X >= 2200, dp);
    }
};