超初心者が競プロに挑む

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

ARC075Eメモ

配列A[i]がある時、A[i]<A[j]となる(i,j) (i<j)のペアの数え上げ方。
A[i]を座標圧縮して、B[i]として、B[i]の出現回数をBinaryIndexedTreeに保存しつつiを0からN-1まで巡回して下記のように数え上げる。全体でNlogN

BIT = createBinaryIndexedTree(N)
answer = 0
for i in 0..N-1
  answer += BIT.sum(0, B[i])
  BIT.add(B[i], 1)
求めたい答え=answer

ARC073Eメモ

ARC073Eで気になるところをメモ
A,Bという同じ長さの配列がある時に、あるiでA[i]とB[i]を入れ替えるという操作を繰り返して
A中の最大値と最小値の差を最小化するという時のアルゴリズムのこと

A=[8,4,4,4,1]
B=[4,0,0,0,4]
Aの最大値と最小値の差は8-1=7

A=[4,4,4,4,4]
B=[8,0,0,0,1]
Aの最大値と最小値の差は4-4=0
みたいにすること
こういうことは、「⓵各iに対するA[i]とB[i]のペアについてA[i]がB[i]以下になるように入れ替え⓶配列Aの中で最小値をとるA[i]がB[i]よりも小さかったら入れ替える」という操作の繰り返しをして、探すことができる。
1
A=[4,0,0,0,1]
B=[8,4,4,4,4]
2
A=[4,4,4,4,1]
B=[8,0,0,0,4]

A=[4,4,4,4,4]
B=[8,0,0,0,1]
終了
でこれはset(ヒープ)を使ってN logNで可能。
⓵の操作のあと、MAX(A)-min(A)が変化するのは⓶の操作をした時のみなので、これで必ず最小となるものを求められる。仮に、最小でないもので入れ替えをしてもmin(A)は変わらないし、MAX(A)が小さくなることはありえなく、その後⓶の操作をしなければならないので、結局⓶の操作だけで十分。疑似コードは以下のような感じ。

H = 昇順ヒープ
DifMin = 適当に大きな値
for i in 1..N:
  H.push({A[i],i})
while True:
  DifMin = min(DifMin, H.last.first - H.begin.first)
  if H.beginが交換をしても効果がない:
    break
  i = H.begin.second
  H.erase( H.begin.first )
  H.push( {B[i], i})
求めたい値=DifMin

ARCとかの解説を読むと、こうゆう「これくらいできるでしょ😐」ってサラッて書かれている場所こそよくわからなかったりするんですよね😞

ABC022C解いてみた

ワーシャルフロイド法は初めてでした。

#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#define MAX_V 305
#define INF (300*100000*10)
using namespace std;

int N, M;

int d[MAX_V][MAX_V];

typedef pair<int,int> P;

int costs[MAX_V];

int main() {
  for(int i=0;i<MAX_V;++i)
    for(int j=0;j<MAX_V;++j)
      d[i][j] = i == j ? 0 :INF;
  for(int i=0;i<MAX_V;++i)
    costs[i] = INF;
  scanf("%d%d", &N, &M);
  for(int i=0;i<M;++i) {
    int u,v,l;
    scanf("%d%d%d", &u, &v, &l);
    if(u==1||v==1) {
      costs[u-1]=l;
      costs[v-1]=l;
    } else {
      d[u - 1][v - 1] = l;
      d[v - 1][u - 1] = l;
    }
  }
  for(int i=0;i<N;++i) {
    for(int j=0;j<N;++j) {
      for(int k=0;k<N;++k) {
        d[j][k] = min(d[j][k],d[j][i]+d[i][k]);
      }
    }
  }
  int minCost = INF;
  for(int i=1;i<N;++i) {
    for(int j=i+1;j<N;++j) {
      if (costs[i]!=INF && costs[j]!=INF) {
        minCost = min(minCost, costs[i]+costs[j]+d[i][j]);
      }
    }
  }
  if (minCost==INF) {
    printf("-1\n");
  } else {
    printf("%d\n", minCost);
  }
  return 0;
}

ABC023D解いてみた

ABC023Dを解いてみました。
まずlogの計算で詰まってしまった(*_*)。最大で O(N log ( N) log (H + NS)) の計算量となるはずですが、するとN=10^5 S,H=10^9を代入してlog_2 10=0.3で計算すると O( 10^5 10^{1.5} 10^{4.5})=O(10^{11})で終わるわけねーだろ😡って思い込んでいたんですが、logの計算間違えてましたね😭。正しくは O( 10^5 \times 1.5 \times 4.5)=O(6 \times 10^5)ということで、logは要注意。
追記
なんかいろいろと勘違いしてました。log_2 10=3.3 O( 10^5 \times 16.5 \times 49.5)=O(10^8)ですね。対数は本当難しい。
下記のコードでは通りません

#include <algorithm>
#include <cstdio>
#define MAX_N  100000
 
using namespace std;
 
int N;
int H[MAX_N];
int S[MAX_N];
long long temp[MAX_N];
 
bool isOK(long long point) {
  for(int i=0;i<N;++i) {
    temp[i] = (point-H[i]) / S[i];
    //--from
    if (temp[i]<0) return false;
   //--to
  }
  sort(temp, temp+N);
 
  for(int i=0;i<N;++i) {
    if (temp[i]<i) {
      return false;
    }
  }
  return true;
}
 
long long solve(long long l, long long r) {
  if (l==r-1) {
    return r;
  }
  if(isOK((l+r)/2)) {
    return solve(l, (l+r)/2);
  } else {
    return solve((l+r)/2, r);
  }
}
 
int main() {
  scanf("%d", &N);
  for(int i=0;i<N;++i) {
    scanf("%d%d", &H[i], &S[i]);
  }
 
  printf("%lld\n", solve(1, (1000ll*1000ll*1000ll*1000ll*1000ll)));
 
 
  return 0;
}

なぜか通らない。詰まった原因は上記from~toのところ。ここで、point-H[i]<0になる時は、temp[i]も負になるというつもりで書いたが、実際はS[i]で割っているので場合によっては負の数でも0に潰れて、正しく比較ができなくなってしまう。
よって下記のようなコードを追加するべきだった。

    if (point-H[i] < 0) {
      temp[i] = -1;
    }

ABC021D解いてみた

重複組み合わせですね...。高校の頃ひたすら苦手でした。なんとか解説を理解したので、解答を書いてみた。

#include <cstring>
#include <cstdio>
#define MOD (1000*1000*1000+7)

using namespace std;

class FactorialMOD {
public:
  static const int MAX_N = 200000 + 100;
  typedef long long MODINT;
  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 asMOD(long long  v) {
  return ((v%MOD) + MOD) % MOD;
}

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

int main() {
  int n,k;
  scanf("%d%d", &n, &k);
  factorialMOD.generate(FactorialMOD::MAX_N, MOD);
  printf("%lld\n", asMOD(combination(n-1+k, n-1)));
}

ABC017D解いてみた

ABC017Dを解いてみました。
しゃくとり法+dpみたいなのは初めてで勉強になった。あと、dpを直接配列にしないで関数にしてやると初期条件で楽できるということに気づいた

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

#define MOD (1000*1000*1000 + 7)

using namespace std;

long long asMOD(long long var) {
  return ((var%MOD) + MOD) % MOD;
}

int f[100*1000+10];
long long _dp[100*1000+10];
int N,M;
bool used[100*1000+10];
long long dp(int n) {
  if (n==-1) {
    return 1;
  }
  if (n==-2) {
    return 0;
  }
  return _dp[n];
}
void setDp(int n,long long v) {
  _dp[n] = v;
}
int main() {
  memset(_dp, 0, sizeof(_dp));
  memset(used, 0, sizeof(used));
  scanf("%d%d", &N, &M);
  for(int i=0;i<N;++i) {
    scanf("%d", &f[i]);
  }

  for(int i=0,j=0;i<N;++i) {
    while(used[f[i]]) {
      used[f[j]]=false;
      j++;
    }
    used[f[i]] = true;
    setDp(i, asMOD(dp(i-1) + asMOD(dp(i - 1) - dp(j - 2))));
  }
  printf("%lld\n", asMOD(dp(N-1)-dp(N-2)));

  return 0;
}

ABC025C解いてみた

ゲームの問題は初めてなので解いてみた。ゲーム木と呼ぶらしいですね。こういうの初見で解けるようになりたい。

#include <cstdio>
#include <algorithm>

using namespace std;

int b[2][3];
int c[3][2];
int allscore=0;

int getState(int state,int i, int j) {
  int index=i*3+j;
  return (state>>(index*2)) & 3;
}

int setState(int state, int value,int i, int j) {
  int index=i*3+j;
  return (value << (index*2)) | state;
}

int getMaxScore(int state, int side) {
  bool maximize = side % 2 == 0;
  int buffer = maximize ? -10000: 10000;

  if (side==9) {
    int score=0;
    for(int i=0;i<3;++i) {
      for(int j=0;j<3;++j) {
        if (i!=0) {
          if (getState(state,i,j) == getState(state,i-1,j)) {
            score += b[i - 1][j];
          } else {
            score -= b[i - 1][j];
          }
        }
        if (j!=0) {
          if (getState(state,i,j) == getState(state,i,j-1)) {
            score += c[i][j-1];
          } else {
            score -= c[i][j-1];
          }
        }
      }
    }
    return score;
  }

  for(int i=0;i<3;++i) {
    for(int j=0;j<3;++j) {
      int s=getState(state, i,j);
      if (s!=0) continue;
      if (maximize) {
        buffer = max(buffer, getMaxScore(setState(state,1, i, j),side+1));
      } else {
        buffer = min(buffer, getMaxScore(setState(state,2, i, j),side+1));
      }
    }
  }

  return buffer;
}

int main() {
  for(int i=0;i<2;++i) {
    for(int j=0;j<3;++j) {
      scanf("%d", &b[i][j]);
    }
  }
  for(int i=0;i<3;++i) {
    for(int j=0;j<2;++j) {
      scanf("%d", &c[i][j]);
    }
  }
  for(int i=0;i<2;++i) {
    for(int j=0;j<3;++j) {
      allscore += b[i][j] + c[j][i];
    }
  }
  int score = getMaxScore(0,0);
  printf("%d\n", (allscore + score) /2);
  printf("%d\n", (allscore - score) /2);
  return 0;
}