ferinの競プロ帳

競プロについてのメモ

yukicoder 710 チーム戦

問題ページ
No.710 チーム戦 - yukicoder

考えたこと

  • 二人でスケジューリング問題をしましょうみたいな問題
  • どうせ貪欲かDP
  • 制約小さいしとりあえずDPを考える
  • dp[i問目][男がj秒][女がk秒] = (この条件が可能か) のDP
  • 状態数が多すぎる
  • dp[i問目][男がj秒] = (女が使う時間の最小) のDP
  • これなら状態数問題ない
  • DPを書いて投げる

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int dp[105][100010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;
  VI a(n), b(n);
  REP(i, n) cin >> a[i] >> b[i];

  REP(i, n+1) REP(j, 100010) dp[i][j] = INF;
  dp[0][0] = 0;
  REP(i, n) REP(j, 100010) {
    chmin(dp[i+1][j], dp[i][j] + b[i]);
    chmin(dp[i+1][j+a[i]], dp[i][j]);
  }

  int ret = INF;
  REP(i, 100010) {
    chmin(ret, max(i, dp[n][i]));
  }
  cout << ret << endl;

  return 0;
}

yukicoder 709 優勝可能性

問題ページ
No.709 優勝可能性 - yukicoder

考えたこと

  • 各パラメータで一番大きい値とその人を持てばいいだけでは?と思って書く
  • サンプルで落ちる
  • 冷静に読むと同じ値が複数出てくる
  • 各パラメーターjで一番大きい値を取る人の集合cnt[j]を持っておきたくなる
  • この集合を毎回マージしてるとTLEで人生終了しそう
  • v[i] = i番目の人が最大になっているパラメータの数 を持っておく
  • v[i]が0→1、1→0になったタイミングで答えの人数は変化する
  • v[i]を使えば毎回マージしなくても答えがわかる
  • v[i]が変化するのは各パラメーターの最大値が更新されたとき
  • 更新されるたび各集合cnt[j]のv[i]を変化させるとパッと見計算量がN^2
  • 各パラメータごとにv[i]が+,-されるのは高々1回ずつ
  • したがってO(NM)で通る

N^2っぽいけど冷静に考えると線形、これすき

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;
  VVI r(n, VI(m));
  REP(i, n) REP(j, m) cin >> r[i][j];

  VI ma(m, 0), v(n, 0);
  VVI cnt(m);
  int ret = 0;
  REP(i, n) {
    REP(j, m) {
      if(ma[j] < r[i][j]) {
        ma[j] = r[i][j];
        for(auto k: cnt[j]) {
          v[k]--;
          if(v[k] == 0) ret--;
        }
        cnt[j].clear();
        v[i]++;
        if(v[i]==1) ret++;
        cnt[j].PB(i);
      } else if(ma[j] == r[i][j]) {
        v[i]++;
        if(v[i]==1) ret++;
        cnt[j].PB(i);
      }
    }
    // cout << v << endl;
    cout << ret << endl;
  }

  return 0;
}

ABC100 A - Happy Birthday!

問題ページ
A: Happy Birthday! - AtCoder Beginner Contest 100 | AtCoder

解法

a <= 8 && b <= 8 なら条件を満たしているのでYay!、違うなら:(を出力する。

abs(a-b) <= 1 ならとか考えてたら2分かかってしまった。

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  string s, t;
  int a, b;
  cin >> a >> b;
  if(a <= 8 && b <= 8) cout << "Yay!" <<endl;
  else cout << ":(" << endl;

  return 0;
}

ABC100 B - Ringo's Favorite Numbers

問題ページ
B: Ringo's Favorite Numbers - AtCoder Beginner Contest 100 | AtCoder

考えたこと

  • ちょうど0回割り切れるって何だと思ってサンプルを見たら1回も割りきれないことっぽい
  • nの後ろに'0'を2d個つければいいでしょと思って投げる
  • 落ちてて何事かと思ったら"ちょうど"の部分が問題
  • D=0,n=100のときに100を出力してるけどこれは100で1回割りきれる
  • n=100なら101にすべき
  • D=1,2でn=100のときも同じ

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int d, n;
  cin >> d >> n;
  if(d == 0 && n == 100) cout << 101 << endl;
  else if(d == 1 && n == 100) cout << 10100 << endl;
  else if(d == 2 && n == 100) cout << 1010000 << endl;
  else cout << to_string(n) + string(2*d, '0') << endl;

  return 0;
}

ABC100 C - \*3 or /2

問題ページ C: *3 or /2 - AtCoder Beginner Contest 100 | AtCoder

考えたこと

  • 全ての要素に対して2で割るか3倍するのどちらかをするのかと思う
  • 全てのiに対して3倍するって何のことだと思って数分が経過する
  • 操作1回につき各要素について2で割るか3倍するかのどっちかをする、ただし全部3倍はだめってことっぽい
  • 3倍したとしても2で割る数は増えない
  • 全て3倍がだめならひとつだけ2で割って他を3倍すればいい
  • sum(a[i]を2で割れる数) が答えになる

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;
  VI a(n);
  REP(i, n) cin >> a[i];

  int ret = 0;
  REP(i, n) {
    while(a[i] && a[i]%2==0) a[i] /= 2, ret++;
  }
  cout << ret << endl;

  return 0;
}

ABC100 D - Patisserie ABC

問題ページ
D: Patisserie ABC - AtCoder Beginner Contest 100 | AtCoder

考えたこと

  • 与えられる値が全て正だったらx[i]+y[i]+z[i]が大きい方から取ればいいだけ
  • 最大化するのは絶対値で負がある
  • それぞれ正負を試せばいいのでは?
  • 正負を固定すればソートして大きい方から貪欲に取っていけばよさそう
  • O(nlogn) で通りそうなので投げると通る

未証明貪欲でWJで10分待つの心臓に悪い

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;
  VI x(n), y(n), z(n);
  REP(i, n) cin >> x[i] >> y[i] >> z[i];

  int ans = 0;
  REP(i, 1<<3) {
    VI v;
    REP(j, n) {
      int tmp = 0;
      if(i&1) tmp += x[j];
      else tmp -= x[j];
      if(i&2) tmp += y[j];
      else tmp -= y[j];
      if(i&4) tmp += z[j];
      else tmp -= z[j];
      v.PB(tmp);
    }
    sort(ALL(v));
    reverse(ALL(v));
    int ret = 0;
    REP(j, m) ret += v[j];
    chmax(ans, ret);
  }
  cout << ans << endl;

  return 0;
}

AOJ2596 Points and Lines

問題ページ
Points and Lines | Aizu Online Judge

考えたこと

  • BNFがパッと目に入って明らかに構文解析
  • 幾何の操作がBNFの形で与えられるのでその結果を求める
  • 幾何の操作は2点から直線を作る操作とreflectionと直線の交点
  • 割と単純な操作でライブラリを貼ればいいのでここはできる
  • 構文解析パートで難しい点としてLL(1)でない
  • 1字先読みしたところで<line-factor>か<point-factor>かとかの区別がつかない
  • ここでJAG合宿2018day1Eを思い出すとpointとlineをまとめたくなる
  • pointとlineをまとめられればそもそも区別する必要がない
  • 適当な構造体を作り構造体が保持しているのがpointなのかlineなのかを変数typeで管理
  • こうすると@が来た時に左辺と右辺のtypeから@ですべき操作を把握できる
  • BNFのpointとlineの部分を以下のように書く
<pl> = <plf> | <pl>@<plf>
<plf> = (<pl>) | (<num>,<num>)
  • これはが左再帰なので除去する
<pl> = <plf><pl_tail>
<pl_tail> = @<pl><pl_tail> | empty

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

const double EPS = 1e-8;

using R = long double;
using P = complex<R>;
using L = pair<P,P>;
using G = vector<P>;
struct C {
  P c; R r;
  C() {}
  C(const P &a, const R &b) : c(a), r(b) {}
};
struct S : public L {
  S() {}
  S(const P &a, const P &b) : L(a,b) {}
};

inline int sgn(const R& r) { return (r>EPS) - (r<-EPS); }
inline R dot(const P& a, const P& b) {
  return real(a)*real(b) + imag(a)*imag(b);
}
inline R det(const P& a, const P& b) {
  return real(a)*imag(b) - imag(a)*real(b);
}
inline P vec(const L& l) {return l.second - l.first;}
namespace std {
    bool operator < (const P& a, const P& b) {
        return sgn(real(a-b)) ? real(a-b) < 0 : sgn(imag(a-b)) < 0;
    }
    bool operator == (const P& a, const P& b) {
        return sgn(real(a-b)) == 0 && sgn(imag(a-b)) == 0;
    }
  bool cmp_y (const P& a, const P& b) {
    return sgn(imag(a-b)) ? imag(a-b) < 0 : sgn(real(a-b)) < 0;
  }
}

// P,L,Sについて入力
inline istream& operator>>(istream& is, P& p) {
  R x, y;
  is >> x >> y;
  p = P(x, y);
  return is;
}
inline istream& operator>>(istream& is, L& l) {
  P a, b;
  is >> a >> b;
  l = L(a, b);
  return is;
}

// 射影
P inline projection(const L &l, const P &p) {
  R t = dot(p-l.first, l.first-l.second) / norm(l.first-l.second);
  return l.first + t*(l.first-l.second);
}
// 反射
P inline reflection(const L &l, const P &p) {
  return p + (R)2 * (projection(l, p) - p);
}

// 交差判定
template<bool strict=false> inline bool intersect(const L&l1, const L&l2) {
  if(strict) return sgn(det(vec(l1),vec(l2))) != 0;
  return sgn(det(vec(l1),vec(l2))) != 0 || l1 == l2;
}

// 交点 交差判定を先にすること!!!
inline P crosspoint(const L& l1, const L& l2) {
  R ratio = det(vec(l2), l2.first-l1.first)/det(vec(l2),vec(l1));
  return l1.first + vec(l1)*ratio;
}

struct node {
  int type;
  P p;
  L l;
};

node plf();
node pl_tail();
node pl();

string s;
int pos = 0;
int number() {
  int ret = 0;
  bool neg = false;
  if(s[pos] == '-') neg = true, pos++;
  while(isdigit(s[pos])) {
    ret *= 10;
    ret += s[pos] - '0';
    pos++;
  }
  if(neg) ret *= -1;
  return ret;
}

node plf() {
  node ret;
  pos++;
  if(s[pos] == '-' || isdigit(s[pos])) {
    int vl = number();
    pos++;
    int vr = number();
    ret.type = 0;
    ret.p = P(vl, vr);
  } else {
    ret = pl();
  }
  pos++;
  return ret;
}

node pl() {
  // plfを読む
  node ret = plf();
  // pl_tailを読む
  while(pos < s.size() && s[pos] != ')') {
    if(s[pos] == '@') {
      pos++;
      node tmp = plf();
      // ret = ret @ tmp
      if(ret.type == 0 && tmp.type == 0) {
        ret.type = 1;
        ret.l = L(ret.p, tmp.p);
      } else if(ret.type == 0 && tmp.type == 1) {
        P p = reflection(tmp.l, ret.p);
        ret.type = 0;
        ret.p = p;
      } else if(ret.type == 1 && tmp.type == 0) {
        P p = reflection(ret.l, tmp.p);
        ret.type = 0;
        ret.p = p;
      } else if(ret.type == 1 && tmp.type == 1) {
        P p = crosspoint(ret.l, tmp.l);
        ret.type = 0;
        ret.p = p;
      } else {
        assert(false);
      }
    } else {
      cout << "err" << pos << " " << s[pos] << endl;
      assert(false);
    }
  }
  return ret;
}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    cin >> s;
    if(s == "#") break;

    pos = 0;
    node ret = pl();
    cout << fixed << setprecision(15) << ret.p.real() << " " << ret.p.imag() << endl;
  }

  return 0;
}