超初心者が競プロに挑む

初心者からの競プロ練習記録

ABC008D解いてみた

座標圧縮はやったことなかったので練習してみます。
まず、素直に実装するとこうなる。
詰まったところ
下のような巨大な配列を何も考えずにmemsetすると凄まじい時間がかかるので、基本的にはギリギリを攻める。

#include <cstring>
#include <algorithm>
#include <cstdio>

#define MAX_N 30

using namespace std;

typedef pair<int,int> P;

int xs[MAX_N+10];
int ys[MAX_N+10];

int dp[MAX_N+10][MAX_N+10][MAX_N+10][MAX_N+10][2000];

P ps[MAX_N+10];
int W,H,N;

int dfs(int x1, int y1, int x2, int y2,int current) {
  if(dp[x1][y1][x2][y2][current]!=-1) {
    return dp[x1][y1][x2][y2][current];
  }
  int answer=0;
  for(int i=0;i<N;++i) {
    int subAnswer=0;
    int used=(current>>i)&1;
    if (used==1) {
      continue;
    }
    int x=ps[i].first;
    int y=ps[i].second;
    if (x>x1 && x<x2 && y>y1&& y<y2) {
      subAnswer +=xs[x2]-xs[x1] + ys[y2]-ys[y1]-3;
      subAnswer +=dfs(x1,y1,x,y, current | (1<<i));
      subAnswer +=dfs(x1,y,x,y2, current | (1<<i));
      subAnswer +=dfs(x,y1,x2,y, current | (1<<i));
      subAnswer +=dfs(x,y,x2,y2, current | (1<<i));
    }
    answer = max(answer, subAnswer);
  }
  return dp[x1][y1][x2][y2][current]=answer;
}

int main() {
  scanf("%d%d%d", &W, &H, &N);
  for(int i=0;i<N;++i) {
    int _x,_y;
    scanf("%d%d", &_x, &_y);
    xs[i]=_x;
    ys[i]=_y;
    ps[i].first =_x;
    ps[i].second=_y;
  }
  for(int i=0;i<=N+1;++i) {
    for(int j=0;j<=N+1;++j) {
      for(int k=0;k<=N+1;++k) {
        for(int l=0;l<=N+1;++l) {
          for(int m=0;m<(1<<N);++m) {
            dp[i][j][k][l][m] = -1;
          }
        }
      }
    }
  }
  xs[N]=0;
  ys[N]=0;
  xs[N+1]=W+1;
  ys[N+1]=H+1;
  sort(xs, xs+N+2);
  sort(ys, ys+N+2);
  for(int i=0;i<N;++i) {
    ps[i].first=lower_bound(xs,xs+N+2,ps[i].first)-xs;
    ps[i].second=lower_bound(ys,ys+N+2,ps[i].second)-ys;
  }

  printf("%d\n", dfs(0,0,N+1,N+1,0));

  return 0;
}

でも、領域のサイズがわかれば別に機械の作動状況は保存する必要がないので下のようになる。

#include <cstring>
#include <algorithm>
#include <cstdio>

#define MAX_N 30

using namespace std;

typedef pair<int,int> P;

int xs[MAX_N+10];
int ys[MAX_N+10];

int dp[MAX_N+10][MAX_N+10][MAX_N+10][MAX_N+10];

P ps[MAX_N+10];
int W,H,N;

int dfs(int x1, int y1, int x2, int y2) {
  if(dp[x1][y1][x2][y2]!=-1) {
    return dp[x1][y1][x2][y2];
  }
  int answer=0;
  for(int i=0;i<N;++i) {
    int subAnswer=0;
    int x=ps[i].first;
    int y=ps[i].second;
    if (x>x1 && x<x2 && y>y1&& y<y2) {
      subAnswer +=xs[x2]-xs[x1] + ys[y2]-ys[y1]-3;
      subAnswer +=dfs(x1,y1,x,y);
      subAnswer +=dfs(x1,y,x,y2);
      subAnswer +=dfs(x,y1,x2,y);
      subAnswer +=dfs(x,y,x2,y2);
    }
    answer = max(answer, subAnswer);
  }
  return dp[x1][y1][x2][y2]=answer;
}

int main() {
  scanf("%d%d%d", &W, &H, &N);
  for(int i=0;i<N;++i) {
    int _x,_y;
    scanf("%d%d", &_x, &_y);
    xs[i]=_x;
    ys[i]=_y;
    ps[i].first =_x;
    ps[i].second=_y;
  }
  for(int i=0;i<=N+1;++i) {
    for(int j=0;j<=N+1;++j) {
      for(int k=0;k<=N+1;++k) {
        for(int l=0;l<=N+1;++l) {
          dp[i][j][k][l] = -1;
        }
      }
    }
  }
  xs[N]=0;
  ys[N]=0;
  xs[N+1]=W+1;
  ys[N+1]=H+1;
  sort(xs, xs+N+2);
  sort(ys, ys+N+2);
  for(int i=0;i<N;++i) {
    ps[i].first=lower_bound(xs,xs+N+2,ps[i].first)-xs;
    ps[i].second=lower_bound(ys,ys+N+2,ps[i].second)-ys;
  }

  printf("%d\n", dfs(0,0,N+1,N+1));

  return 0;
}

メモ化再帰直感的でいいですね!

ABC017C解いてみた

一つ取らない宝石を決めた時、もっともスコアが良い取り方はその宝石を取らない区間を持つ遺跡をできるだけ訪れた時だから、これは遺跡で集められる宝石の右端がその宝石より小さい遺跡すべてと、左端がその宝石より大きい遺跡すべてを訪れれば良い。遺跡で集められる宝石の両端でソートして点数の累積和を調べておけば、これはO(log(n))でもとまるから、全体ではO(Mlog(n))でもとまる。
詰まったところ
std::pairの比較でデフォルトの比較演算子ではstd::pairのfirstとsecondをともに利用して辞書順にするということをやっていた。これはstd::pairのfirstだけで比較したい時たまに面倒くさいことになるので下記のような関数を用意しておけば良い。

#include <cstdio>
#include <utility>
#include <algorithm>
#include <functional>

using namespace std;

typedef pair<int,int> P;

bool compOnFirst(const P& a, const P&b) {
  return a.first < b.first;
}

int N,M;
P ls[100010];
P rs[100010];
int INF=5000*200010;
int main() {
  scanf("%d%d", &N, &M);
  for(int i=0;i<N;++i) {
    int l,r,s;
    scanf("%d%d%d", &l,&r,&s);
    ls[i] = P(l,s);
    rs[i] = P(r,s);
  }
  sort(ls, ls+N, compOnFirst);
  sort(rs, rs+N, compOnFirst);
  for(int i=0;i<N-1;++i) {
    ls[i+1].second += ls[i].second;
    rs[i+1].second += rs[i].second;
  }
  int score=-1;
  for(int i=1;i<=M;++i) {
    int current = 0;
    auto last=upper_bound(rs, rs + N, P(i - 1,0), compOnFirst);
    if(last != rs) {
      current += (last-1)->second;
    }
    auto first = lower_bound(ls, ls + N, P(i + 1,0), compOnFirst);
    if(first!=(ls+N)) {
      current += (ls + N - 1)->second - (first - 1)->second;
    }

    score = max(score, current);
  }
  printf("%d\n", score);
  return 0;
}

ABC003D解いてみた

ARCは難しすぎるのでABCからやることにしました。ABC003Dが難しく、満点解答は思いつかなかったので、解答を見ました。包除原理というやつです。
今回のでは、A_1をXY区画の左端にものがない並べ方の集合、A_2をXY区画の右端にものがない並べ方の集合、A_3をXY区画の上端にものがない並べ方の集合、A_4をXY区画の下端にものがない並べ方の集合として包除原理を適用してwikiの通りの公式に代入します。そして下のコードになりました。ちなみにMODが10^9ほどまでになるので、intで途中計算すると解答が合わなくなります。
下記のコードで、from~toを二つ目のコードと置き換えたものが正解のコードです

#include <cstdio>
#include <cstring>
#define MOD (1000000000 + 7)
using namespace std;

class FactorialMOD {
  static const int MAX_N = 1000;
  typedef long long MODINT;
public:
  MODINT facTable[MAX_N+10];
  MODINT invTable[MAX_N+10];

  void generate(int n, MODINT p) {
    memset(facTable, 0, sizeof(facTable));
    memset(invTable, 0, sizeof(invTable));
    facTable[0]=1;
    for(int i=1;i<=n;++i) {
      facTable[i] = (facTable[i-1] * i) % p;
    }

    MODINT power = facTable[n];
    MODINT res = 1;
    MODINT index = p-2;

    for(int i=0;(index>>i) != 0;++i) {
      if( ((index >> i) & 1) == 1) {
        res = (res * power) % p;
      }
      power = (power*power) %p;
    }

    invTable[n] = res;
    for(int i=n;i>=1;--i) {
      invTable[i-1] = (invTable[i] * i) % p;
      if((invTable[i] * facTable[i]) %p != 1) printf("Error");
    }

  }

  MODINT factorial(int n) {
    return facTable[n];
  }

  MODINT inverseFactorial(int n) {
    return invTable[n];
  }
};

FactorialMOD factorialMOD;

long long combination(int n,int r) {
  if(n<r) return 0;
  return (((factorialMOD.factorial(n) % MOD) * factorialMOD.inverseFactorial(r) % MOD) * factorialMOD.inverseFactorial(n-r)) % MOD;
}

int main() {
  int R,C,X,Y,D,L;
  scanf("%d%d%d%d%d%d",&R,&C,&X,&Y,&D,&L);
  factorialMOD.generate(1000, MOD);
  long long temp=combination(X*Y, D+L);
  long long temp1a=(combination((X-1)*Y, D+L) * 2) % MOD;
  long long temp1b=(combination(X*(Y-1), D+L) * 2) % MOD;
  long long temp2a=(combination((X-1)*(Y-1), D+L) * 4) % MOD;
  long long temp2b=combination((X-2)*Y, D+L) % MOD;
  long long temp2c=combination(X*(Y-2), D+L) % MOD;
  long long temp3a=(combination((X-2)*(Y-1), D+L) * 2) % MOD;
  long long temp3b=(combination((X-1)*(Y-2), D+L) * 2) % MOD;
  long long temp4=(combination((X-2)*(Y-2), D+L) ) % MOD;
  long long num = combination(D+L, L);
//--from
  temp = (temp - ((temp1a + temp1b) % MOD - ((temp2a + temp2b) % MOD + temp2c) % MOD + (temp3a + temp3b) % MOD -
                  temp4 % MOD)) % MOD;
//--to
  long long answer = ((((R-X+1) * (C-Y+1) *temp ) % MOD) *num)%MOD;
  printf("%lld\n", (answer + MOD)%MOD);

  return 0;
}

ところが、これだとACにはならない(0点)。正解は上記のコードのfrom~toを下のコードと置き換えたものになります。

  if(X*Y > D+L) {
    temp = (temp - ((temp1a + temp1b) % MOD - ((temp2a + temp2b) % MOD + temp2c) % MOD + (temp3a + temp3b) % MOD -
                    temp4 % MOD)) % MOD;
  }

もしくはこう

  if(X==1 && Y ==1) temp4 = 0;
  temp = (temp - ((temp1a + temp1b) % MOD - ((temp2a + temp2b) % MOD + temp2c) % MOD + (temp3a + temp3b) % MOD -
                  temp4 % MOD)) % MOD;

つまり、X==1でY==1の時の端にものがない場合の数の計算ので、第一引数が-1*-1=1となってしまい{}_1C_1で0にならず場合の数が1減ってしまうのが原因です。これに本番気づく人は相当すごいと思う(*_*)。
教訓:マイナスは本当に気をつける

セグメント木でなぜかすごい詰まったところ

セグメント木で凄まじく詰まったためメモをしておく
下記のコードで、呼び出しの時、calcMin(a,b,0,0,n)ではなくcalcMin(a,b,0,0,N)でなければならない。要するに、セグメント木の実際に使う範囲を指定するのではなく、実際のセグメントのサイズで呼び出さないと正しい結果はでないです。

class SegmentTree {
public:
  long long Storage[MAX_L*2+10];
  int N;
public:
  void init(int n) {
    N=1;
    while(N<n) N*=2;

    for(int i=0;i<N*2;++i) {
      Storage[i]=INF;
    }

    updateLeaf(0, 0);
  }

  void updateLeaf(int i, int value) {
    i += N-1;
    Storage[i]=value;
    while(i>0) {
      i = (i-1) / 2;
      Storage[i] = min(Storage[i*2+1], Storage[i*2+2]);
    }
  }

  long long int getLeaf(int i) {
    i += N -1;
    return Storage[i];
  }

  long long calcMin(int a,int b,int k,int l, int r) {
    if(b<=l || a>=r) return INF;
    if(a<=l && b>=r) {
      return Storage[k];
    } else {
      long long tl = calcMin(a,b,k*2+1,l,(l+r)/2);
      long long tr = calcMin(a,b,k*2+2,(l+r)/2,r);
      return min(tl,tr);
    }
  }
};

AGC018受けてみた

AGC018受けました!
結果はAの一問しかできずに終わりました(T_T)。
A
二つの数どうしで引き算をして作れるのはその二つの数の最大公約数の倍数なので、すべての数の最大公約数を求めて、その倍数が作れる。

いつかB~Fまで同じようにかけたらいいですね!

ARC021B解いてみた

解説を読んで、自分のやり方と違ったので載せておきます。
xorには結合法則が成り立つことと、自分自身にxorをすると、0になることを利用して、A_0の高次ビットから0と決め打ちして、整合性を確認しながらビットを埋めていけば自然に辞書順で最小となります。

#include <cstdio>
#include <cstring>
#define MAX_L 100000

using namespace std;

int B[MAX_L+10];
int A[MAX_L+10];

int main() {
  int L;
  scanf("%d", &L);

  for(int i=0;i<L;++i) {
    scanf("%d", &B[i]);
  }

  memset(A, 0, sizeof(A));

  for(int i=30;i>=0;--i) {
    int test;
    for(test=0;test<2;++test) {
      int next_bit = test;
      for(int j=0;j<L;++j) {
        int b_bit=(B[j] >>i) & 1;
        next_bit = b_bit xor next_bit;
      }
      if(next_bit == test) {
        break;
      } else {
        if(test == 1) {
          printf("-1\n");
          return 0;
        }
      }
    }
    A[0] |= (test<<i);
  }

  for(int i=1;i<L;++i) {
    A[i] = A[i-1] xor B[i-1];
  }

  for(int i=0;i<L;++i) {
    printf("%d\n", A[i]);
  }
  return 0;
}

ARC018C解いてみた

見てもわからず、答えを見て実装してみました。
なお、この手のx_i=(x_{i-1} + a) % pの漸化式による、乱数生成法を線形合同法と呼びます。

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <utility>
#include <algorithm>

#define AT(x,y) ((x) * M + y)

using namespace std;

typedef pair<int,int> P;
typedef pair<int,P> PP;

PP G[1000*1000+10];
vector<PP> sortedG[1000+10];

int main() {
  int N,M;
  int x_0,a,p;

  scanf("%d%d", &N,&M);
  scanf("%d%d%d", &x_0, &a, &p);

  for(int i=0;i<N;++i) {
    for(int j=0;j<M;++j) {
      if(i==0 && j==0) {
        G[AT(i,j)] = PP(x_0, P(i,j));
      } else if(j==0) {
        G[AT(i,j)] = PP((G[AT(i-1,M-1)].first + a) % p,P(i,j));
      } else {
        G[AT(i,j)] = PP((G[AT(i,j-1)].first + a) % p, P(i,j));
      }
      //printf("%d ", G[AT(i,j)].first);
    }
    //printf("\n");
  }

  sort(G, G+(N*M));

  int work = 0;

  for(int i=0;i<N;++i) {
    for(int j=0;j<M;++j) {
      sortedG[i].push_back(PP(G[AT(i,j)].second.second, G[AT(i,j)].second));
    }
    sort(sortedG[i].begin(), sortedG[i].end());

    for(int j=0;j<M;++j) {
      work += abs(sortedG[i][j].second.second - j) + abs(sortedG[i][j].second.first - i);
    }
  }

  printf("%d\n", work);


  return 0;
}