三年目の初学者(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);
    }
};

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

問題
topcoder SRM 602 div2 med PilingRectsDiv2
TopCoder Statistics - Problem Statement

使用言語
C++

方針
・各長方形を重ねるかどうかで場合分け
・limitを下回らないように毎回チェック

所感
・もう英語できるとは言いません。ごめんなさい。
・圧倒的再帰&&条件分け
・再帰の条件自体はそこまで難しくない？
・関数の引数を減らす方法がないか探っている(以前外部変数使ってやろうとしたけどだめだった)(誰か教えてください)
・条件演算子極めたい(条件演算子って入れ子にできる？←というか ? : で伸ばせるじゃん)
・何もないところに重ねるのって、無限の大きさの長方形に重ねるのと一緒だよね(哲学)

コード

//重なっている長方形の辺をx,y
//各i枚目について調べる
int pile(vector<int> X, vector<int> Y, int i, long x, long y, int size, int limit)
{
  //全部見終わったら終了
  if (i == size) return 0;

  if (x <= X[i] && y <= Y[i]) {
    return x * y >= limit ? pile(X, Y, i+1, x, y, size, limit)+1 : 0;
  } else if (x >= X[i] && y <= Y[i]) {
    if (x * y >= limit) {
      if (X[i] * y >= limit)
        return max(pile(X, Y, i+1, x, y, size, limit),
          pile(X, Y, i+1, X[i], y, size, limit)+1);
      else return pile(X, Y, i+1, x, y, size, limit);
    } else return 0;
  } else if (x <= X[i] && y >= Y[i]) {
    if (x * y >= limit) {
      if (x * Y[i] >= limit)
        return max(pile(X, Y, i+1, x, y, size, limit),
          pile(X, Y, i+1, x, Y[i], size, limit)+1);
      else return pile(X, Y, i+1, x, y, size, limit);
    } else return 0;
  } else {
      if (x * y >= limit) {
        if (X[i] * Y[i] >= limit)
          return max(pile(X, Y, i+1, x, y, size, limit),
            pile(X, Y, i+1, X[i], Y[i], size, limit)+1);
        else return pile(X, Y, i+1, x, y, size, limit);
      } else return 0;
  }
}

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

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

使用言語
C++

サンプルケースの検証
(リンゴの個数, オレンジの個数)で表すとする。

{7, 4, 5}
{1, 10, 2}のとき
1個の時 (3, 0)~(0, 3)
2個の時 (6, 0)~(1, 5)
3個の時 (9, 0)~(3, 6)
...
赤字のところの差が各個数-1になる
→ max_a += min(i, apple[j]);
min_a += max(0, i - orange[j]);

所感
・問題の理解がしにくかった
・実際に紙に書くのは大事

コード

int check_combination(int i, vector<int> apple, vector<int> orange)
{
  int max_a = 0, min_a = 0;

  for (int j = 0; j < apple.size(); j++) {
    max_a += min(i, apple[j]);
    min_a += max(0, i - orange[j]);
  }

  return max_a - min_a + 1;
}

class WinterAndPresents {
    public:
    long long getNumber(vector<int> apple, vector<int> orange) {
      vector<int> sum; long long ans = 0;

      for (int i = 0; i < apple.size(); i++) {
        sum.push_back(apple[i] + orange[i]);
      }

      for (int i = 1; i <= *min_element(sum.begin(), sum.end()); i++) {
        ans += check_combination(i, apple, orange);
      }
        return ans;
    }
};