2020-01-21

Codeforces 1288C Two Arrays (R1600)

数え上げ

codeforces.com

問題

整数 $N,M$ が与えられます。長さ $N$ の数列 $a,b$ のペアであって、次の条件を満たすものの個数を求めてください。

$1 \le a_i,\ b_i \le M\ (1 \le i \le N)$
$a_i \le a_{i+1}\ (1 \le i \le N-1)$
$b_i \ge b_{i+1}\ (1 \le i \le N-1)$
$a_i \le b_i\ (1 \le i \le N)$

制約

$1 \le N \le 10$
$1 \le M \le 1000$

考察

条件を図にすると、赤の□で囲んだ部分の不等号が無くても十分だと分かります。 f:id:tekihei:20200121211206j:plain
よって、以下の条件を満たす $a,b$ の個数を数えれば良いです。

$1 \le a_1 \le a_2 \le \cdots \le a_N \le b_N \le b_{N-1} \le \cdots \le b_1 \le M$

これは $M$ 種類のものから重複を許して $2N$ 個取る場合の数に等しく、 $\binom{M+2N-1}{2N}$ 通りです。

#include<bits/stdc++.h>
using namespace std;

using Lint=long long;
template<int mod> class ModInt
{
 private:
    Lint val;
 public:
    Lint value(){ return val; }
    ModInt(Lint x=0){ val=x%mod; }
    ModInt pow(int n){
        ModInt res(1),x(val);
        while(n>0){ if(n&1) res*=x; x*=x; n>>=1; }
        return res;
    }
    ModInt inv(){ return pow(mod-2); }
    ModInt& operator+=(ModInt rhs){ val+=rhs.val; if(val>=mod) val-=mod; return *this; }
    ModInt& operator-=(ModInt rhs){ val+=mod-rhs.val; if(val>=mod) val-=mod; return *this; }
    ModInt& operator*=(ModInt rhs){ val=val*rhs.val%mod; return *this; }
    ModInt& operator/=(ModInt rhs){ *this*=rhs.inv(); return *this; }
    ModInt operator+(ModInt rhs){ return ModInt(val)+=rhs; }
    ModInt operator-(ModInt rhs){ return ModInt(val)-=rhs; }
    ModInt operator*(ModInt rhs){ return ModInt(val)*=rhs; }
    ModInt operator/(ModInt rhs){ return ModInt(val)/=rhs; }
};
using mint=ModInt<1000000007>;

template<typename T> class BiCoef
{
 public:
    vector<T> fact,ifact,inv;
    BiCoef(int N):fact(N+1),ifact(N+1),inv(N+1){
        fact[0]=ifact[N]=inv[0]=1;
        for(int i=1;i<=N;i++) fact[i]=fact[i-1]*i;
        ifact[N]/=fact[N];
        for(int i=N-1;i>=0;i--) ifact[i]=ifact[i+1]*(i+1);
        for(int i=1;i<=N;i++) inv[i]=ifact[i]*fact[i-1];
    }
    T comb(int n,int k){
        if(n<0 or k<0 or n<k) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};

int main()
{
   int M,N; cin>>M>>N; // max value, length
   BiCoef<mint> bc(M+2*N);
   cout<<bc.comb(M+2*N-1,2*N).value()<<endl;
   return 0;
}

感想

$N$ の制約が小さいのが怪しいと思っていたので $O(1)$ だとは思いませんでした。 $b$ も広義単調増加だとこれと同じようにはできませんが、DPを累積和で高速化して $O(NM^{2})$ で出来そうです。

2020-01-18

yukicoder contest 234

yukicoder.me

A.じゃんけん

表を書くとあいこになるのは $X=0,4,10$ のときだと分かります。

B.数列変換マシン

$y_{i}=\dfrac{\sum x_{i}-x_{i}}{N-1}$ より $x_{i}=\sum x_{i}-(N-1)y_{i}$ なので、 $\sum x_{i}$ を求めれば良いです。ここで例えば $N=3$ のとき、 $$ y_{1}=\dfrac{x_{2}+x_{3}}{2},\ y_{2}=\dfrac{x_{1}+x_{3}}{2},\ y_{3}=\dfrac{x_{1}+x_{2}}{2} $$ の辺々を加えると、 $y_{1}+y_{2}+y_{3}=x_{1}+x_{2}+x_{3}$ が成り立つことが分かります。一般の場合も、右辺の $x_{i}$ について $\frac{x_{i}}{N-1}$ が $N-1$ 回足されるので $\sum y_{i} = \sum x_{i}$ が成り立ちます。よって $x_{i}=\sum y_{i}-(N-1)y_{i}$ です。

#include<bits/stdc++.h>
using namespace std;

using Lint=long long;

int main()
{
   int N; cin>>N;
   vector<int> y(N);
   for(int i=0;i<N;i++) cin>>y[i];

   int S=accumulate(y.begin(),y.end(),0);
   for(int i=0;i<N;i++){
      cout<<S-(N-1)*y[i]<<(i==N-1? '\n':' ');
   }
   return 0;
}

C.いたずらっ子

マス $(i,j)$ に来る経路は $(i-1,j)$ または $(i,j-1)$ のどちらかを通るので、dpできそうです。 $$ dp[i][j]:=マス(i,j)に来るまでにかかる移動時間の最小値 $$ とすると、
[1] $(i,j)$ にいたずらっ子がいない場合 $$ dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1 $$ [2] $(i,j)$ にいたずらっ子がいる場合 $$ dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1+(戻ってくるまでにかかる時間の最小値) $$ です。 $(i,j)$ に来れるということは、いたずらっ子がいない(orいなくなった)マスのみを通って $(i,j)$ に来れるということなので、 (戻ってくるまでにかかる時間の最小値)は $i+j$ です。

#include<bits/stdc++.h>
using namespace std;

using Lint=long long;
const int INF=1e9;

int main()
{
   int H,W; cin>>H>>W;
   vector<string> s(H);
   for(int i=0;i<H;i++) cin>>s[i];

   vector<vector<int>> dp(H,vector<int>(W,INF));
   dp[0][0]=0;
   for(int i=0;i<H;i++) for(int j=0;j<W;j++){
      if(i>0) dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
      if(j>0) dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
      if(s[i][j]=='k') dp[i][j]+=i+j;
   }
   cout<<dp[H-1][W-1]<<endl;
   return 0;
}

4方向に進める場合はどうやって解くのでしょうか(誤読していました)。ダイクストラで出来そうだと思いましたが、戻ってくるまでにかかる時間の最小値がよく分からず、詰まってしまいました。

D.選び方のスコア

$a$ は昇順ソートされているものとします。偶数個のときの中央値が厄介なので、まずは奇数個選ぶときを考えます。

[1]選ぶ個数が奇数個のとき

中央値になる要素を全探索します。ある要素 $m$ が中央値となるのは、 $m$ の左右から同じ個数を選んだときです。また、左右から $i$ 個ずつ選んだときのスコアは、 $(選んだ数の和)- m \times 2i$ なので、大きい方から $i$ 個ずつ選ぶのが最適です。

すべての $m$ に対して $i$ を全探索すると $O(N^{2})$ で間に合いません。ここで、 $i$ を一つずつ増やしていったときのスコアの差分に注目すると、増えることがないことが分かるので、これが正の間だけ足していけば良いです。このような境界は二分探索で求められるので、 $O(NlogN)$ で間に合います。

[2]選ぶ個数が偶数個のとき

選んだ数のうち、中央の２つの数を左から順に $m_1$ 、 $m_2$ とします。このとき、実は $m_2$ を選ばなかった場合のスコアが悪くなることはないです。なぜかというと、中央の２つの数の寄与を別に考えると、スコアは( $S,cntをそれぞれ他に選んだ数の和と個数とします$ ) $$ \left(m_1-\dfrac{m_1+m_2}{2}\right)+\left(m_2-\dfrac{m_1+m_2}{2}\right)+S-\dfrac{m_1+m_2}{2} \times cnt =S-\dfrac{m_1+m_2}{2} \times cnt $$ から
$$ (m_1-m_1)+S-m_1 \times cnt = S-m_1 \times cnt $$ に変化し、 $m_1 \le \dfrac{m_1+m_2}{2}$ だからです。よって偶数個選ぶ場合は考えなくて良いです。

#include<bits/stdc++.h>
using namespace std;

using Lint=long long;

int main()
{
   int N; cin>>N;
   vector<int> a(N);
   for(int i=0;i<N;i++) cin>>a[i];
   sort(a.begin(),a.end());

   vector<Lint> sum(N+1);
   for(int i=0;i<N;i++) sum[i+1]=sum[i]+a[i];

   Lint ans=0;
   for(int i=0;i<N;i++){
      int L=i,R=N-(i+1);
      int ok=0,ng=min(L,R)+1;
      while(ng-ok>1){
         int mid=(ok+ng)/2;
         if(a[i-mid]+a[N-mid]-2*a[i]>0) ok=mid;
         else ng=mid;
      }
      ans=max(ans,(sum[i]-sum[i-ok])+(sum[N]-sum[N-ok])-2LL*ok*a[i]);
   }
   cout<<ans<<endl;
   return 0;
}

奇数個のときの愚直解を書いてサンプルがあったのでもしかしたら、、、と思ったらそうでした。

E.余興

$O(N^{3})$ の愚直解は分かりました。またあとでやります。

感想

Dが面白かったです。最近競プロから離れ気味なのでちょっとずつがんばります。

2019-12-31

2019年の振り返り&2020年の目標

2019年を軽く振り返ろうと思います。

1月~3月

受験があったらしいです。この時期が今年だったと感じられないくらい昔に感じます。センター試験が終わった頃に、何かやりたいなぁと思って、競技プログラミングを再開することにしました。競技プログラミングは高2のときに一年くらいやっていました。高3になってやめて、自分の中で完全に忘れていたのですが、再開してみると楽しかったです。

4月~6月

大学に入学して、一人暮らしを始めました。引っ越してきたときから目がかゆくて、何事かと思ったら花粉症でした。飛散量が多いときだけ発症するタイプもあるみたいなので、地元より飛散量が多かったのかなと思います。大学も一人暮らしも、最初は初めてやることばかりだったので疲れました。

7月~9月

7月はICPC国内予選がありました。8月と9月は夏休みでした(長い)。夏休みは最初の一ヶ月はずっとゲームをしていました。流石に色々やばいと思ったので生活を見直した結果、競技プログラミングと筋トレをすることにしました。なお、継続はできていない模様です。

10月~12月

この頃はそこそこ高いモチベーションを保って競技プログラミングをしていました。アジア大会に向けてチーム練習をしていて、これが楽しかった記憶があります。アジア大会は台湾に行きました。初めて企業コンテストの予選に通過して、本戦に参加しました(日経コン)。このころから問題の解説を書き始めました。解説を書くとよく分かってないままの状態を避けることができるので、続けていきたいです。

一年を通して

AtCoder水色から青色になりましたが、実力は4月頃からほとんど変わっていないと思います(かなしい)。単純に問題を解くスピードが遅い(精進量が少ない)からだと思います。来年はいっぱい問題を解きたいと思います。生活習慣がしばしば壊れていたので健康的な生活をしたいと思います。

解いた問題数

サイト	問題数
TopCoder	1
CodeForces	215
AtCoder	525
AOJ	121
yukicoder	46
Sum	908

そういえばtwitterのパスワードを忘れたのでログインできなくなりました()　もうログインできない気がするので別のアカウントを作るかもしれません。

2020年の目標

	☆	☆☆	☆☆☆
生活習慣	寝る前にスマホを見ないマルチタスクをしない	運動をする
競プロ	蟻本を読破する解説を書く(コンテストの解説+α)	年間600AC	AtCoder黄色 Codeforces薄橙
その他	単位を落とさない

頭回ってないのであとで追加すると思います(1/5(日)まで)。月の始まりと終わりに目標と振り返りみたいな記事を書きたいと思います。今年はいい一年でした。来年もいい一年にできればなと思います。

2019-12-23

AGC006C Rabbit Exercise(800)

期待値

atcoder.jp

考察

うさぎ $j$ がジャンプする前後の座標の期待値の変化を考えます( $2 \le j \le N-1$ )。うさぎ $j$ のジャンプ前後のうさぎ $i(1 \le i \le N)$ の座標をそれぞれ $X_{i}, X_{i}'$ とします(これらは確率変数です)。
(1) $i=j$ のとき(うさぎ $i$ がジャンプする場合)
点 $x$ の点 $y$ に関して対象な点の座標を $f(x,y)$ で表すとすると、 \begin{eqnarray} E(X_{i}') &=& \displaystyle \sum_{x_{i}} \sum_{x_{i-1}} f(x_{i},x_{i-1}) \cdot P(X_{i}=x_{i},X_{i-1}=x_{i-1}) \cdot \frac{1}{2} + \sum_{x_{i}} \sum_{x_{i+1}} f(x_{i},x_{i+1}) \cdot P(X_{i}=x_{i},X_{i+1}=x_{i+1}) \cdot \frac{1}{2} \\ &=& \displaystyle \frac{1}{2} \sum_{x_{i}} \sum_{x_{i-1}} f(x_{i},x_{i-1}) \cdot P(X_{i}=x_{i},X_{i-1}=x_{i-1})+ \frac{1}{2} \sum_{x_{i}} \sum_{x_{i+1}} f(x_{i},x_{i+1}) \cdot P(X_{i}=x_{i},X_{i+1}=x_{i+1}) \\ &=& \displaystyle \frac{1}{2} E(f(x_{i},x_{i-1}))+ \frac{1}{2} E(f(x_{i},x_{i+1})) \\ &=& \frac{1}{2} E(2x_{i-1}-x_{i}) + \frac{1}{2} E(2x_{i+1}-x_{i}) \\ &=& \frac{1}{2}(2E(x_{i-1})-E(x_{i})) + \frac{1}{2}(2E(x_{i+1})-E(x_{i})) \\ &=& E(x_{i-1})+E(x_{i+1})-E(x_{i}) \end{eqnarray} 1行目は期待値の定義です(とりうる値 $\times$ 確率の総和)。2行目の $\frac{1}{2}$ の後ろはそれぞれ $f(x_{i},x_{i-1})$ と $f(x_{i},x_{i+1})$ の期待値の定義になっています。最後のほうは期待値の線形性を用いて変形しています。

(2) $i \neq j$ のとき
$X_{i}$ と $X_{i}'$ の確率分布は等しいので、期待値も等しいです。つまり $E(X_{i}')=E(X_{i})$ です(動かないので、それはそう?)。

(1)と(2)をまとめると、 $$ E(X_{i}')=\left\{ \begin{array}{ll} E(X_{i-1})+E(X_{i+1})-E(X_{i}) & (i=j) \\ E(X_{i}) & (i \neq j) \end{array} \right. $$

ジャンプする前のうさぎの位置の期待値はもとの座標に等しいので、結局以下の問題を解けば良いです。

$N$ 要素の数列 $(x_1, x_2, ... ,x_n)$ がある。 $j回目(1 \le j \le M)$ の操作では $i=a_{j}$ として $x_{i}$ を $x_{i-1}+x_{i+1}-x_{i}$ に置き換える。 $M$ 回の操作を $1$ セットとして $K$ セット行うとき、最終的な数列を求めよ。

操作を行列の積で表すことを考えます。例えば $N=5$ で $a_{i}=3$ だった場合、以下のように表せます。 $$ \begin{pmatrix} x_1' \\ x_2' \\ x_3' \\ x_4' \\ x_5' \\ \end{pmatrix}= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & -1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ \end{pmatrix} $$

よって、このような $M$ 個の行列の積を求めて $K$ 乗すれば、 $K$ セットの操作を表す行列が求まるので、最終的な数列を求められます。計算量は $O(N^{3}(M+\log K))$ です。これは少し改良することができます。上のような行列を左からかけることは「 $a_{i}行目を-1倍して、a_{i}-1行目とa_{i}+1行目をa_{i}行目に加える$ 」ことに相当します。よって $M$ 個の行列の積を求めるところを $O(N^{3}M)からO(NM)$ に改良することができます(TLEすることに変わりはないですが)。

#include<bits/stdc++.h>
using namespace std;

using Lint=long long;

template<class T> class Matrix
{
 public:
    vector<vector<T>> A;
    Matrix(int n):A(n,vector<T>(n)){}
    Matrix(int n,int m):A(n,vector<T>(m)){}

    vector<T>& operator[](int i){ return A[i]; }
    int height(){ return A.size(); }
    int width(){ return A[0].size(); }
    static Matrix I(int n){
        Matrix mat(n);
        for(int i=0;i<n;i++) mat[i][i]=1;
        return mat;
    }

    Matrix& operator+=(Matrix& B){
        int H=height(), W=width();
        for(int i=0;i<H;i++) for(int j=0;j<W;j++)
            A[i][j]+=B[i][j];
        return *this;
    }
    Matrix& operator-=(Matrix& B){
        int H=height(), W=width();
        for(int i=0;i<H;i++) for(int j=0;j<W;j++)
            A[i][j]-=B[i][j];
        return *this;
    }
    Matrix& operator*=(Matrix& B){
        int H=height(), W=B.width(), K=width();
        vector<vector<T>> C(H,vector<T>(W));
        for(int i=0;i<H;i++) for(int j=0;j<W;j++)
            for(int k=0;k<K;k++) C[i][j]+=A[i][k]*B[k][j];
        A.swap(C);
        return *this;
    }
    Matrix operator+(Matrix& B){ return Matrix(*this)+=B; }
    Matrix operator-(Matrix& B){ return Matrix(*this)-=B; }
    Matrix operator*(Matrix& B){ return Matrix(*this)*=B; }
    Matrix pow(Lint K){
        Matrix res=Matrix::I(height());
        Matrix B=*this;
        while(K>0){
            if(K&1) res*=B; B*=B; K>>=1;
        }
        return res;
    }
};

int main()
{
   int N; cin>>N;
   vector<int> x(N);
   for(int i=0;i<N;i++) cin>>x[i];
   Lint M,K; cin>>M>>K;
   vector<int> a(M);
   for(int i=0;i<M;i++) cin>>a[i],a[i]--;

   assert((Lint)N*M+N*N*N<=(Lint)1e7); // これくらいまでは解ける?
   Matrix<Lint> A=Matrix<Lint>::I(N);
   for(int i=0;i<M;i++){
      for(int j=0;j<N;j++) A[a[i]][j]*=-1;
      for(int j=0;j<N;j++) A[a[i]][j]+=A[a[i]-1][j];
      for(int j=0;j<N;j++) A[a[i]][j]+=A[a[i]+1][j];
   }
   A=A.pow(K);

   Matrix<Lint> ans(N,1);
   for(int i=0;i<N;i++) ans[i][0]=x[i];
   ans=A*ans;
   for(int i=0;i<N;i++) cout<<ans[i][0]<<endl;
   return 0;
}

このままでは間に合わないので、別の方法を考えます。

「 $x_{i}$ を $x_{i}'=x_{i-1}+x_{i+1}-x_{i}$ に置き換える」という操作について考えてみます。 $x_{i-1}+x_{i+1}-x_{i}$ は $f(x_{i},x_{i-1})$ と $f(x_{i},x_{i+1})$ の中点です。よって図に書くと以下のようになります。

f:id:tekihei:20191225130254p:plain

ここで $x_{i-1}$ と $x_{i}'$ の距離はいくつになっているでしょうか？ $x_{i}'$ は中点なので、 $f(x_{i},x_{i-1})$ と $x_{i}'$ の距離は(赤)+(黄)です。よって $x_{i-1}$ と $x_{i}'$ の距離は(黄)になっていることが分かります。同様にして $x_{i}'$ と $x_{i+1}$ の距離が(赤)になっていることも分かります。

f:id:tekihei:20191225130301p:plain

以上よりこの操作は階差を交換する操作と言い換えることができそうです。実際 $d_{i} :=x_{i+1}-x_{i}$ とおくと
\begin{eqnarray} d_{i}' &=& x_{i+1}'-x_{i}' &=& x_{i+1}-(x_{i-1}+x_{i+1}-x_{i}) &=& x_{i}-x_{i-1} &=& d_{i-1} \\ d_{i-1}' &=& x_{i}'-x_{i-1}' &=& (x_{i-1}+x_{i+1}-x_{i})-x_{i-1} &=& x_{i+1}-x_{i} &=& d_{i} \end{eqnarray} より、(大小関係が図のようになっていない場合も)階差の交換と言い換えられることが分かります。

実際に階差の値を交換すると $O(MK)$ ですが、添字を交換することにすると、操作を $1$ から $N-1$ の置換で表すことができるので、置換の累乗で $O(M+N\log K)$ に高速化できます。あとは最終的な階差からもとの数列を復元することで答えを求められます。

#include<bits/stdc++.h>
using namespace std;

using Lint=long long;

class Permutation
{
 private:
   vector<int> A;
 public:
   Permutation(int n):A(n){}
   int& operator[](int i){ return A[i]; }
   int size(){ return A.size(); }
   static Permutation I(int n){
      Permutation res(n);
      for(int i=0;i<n;i++) res[i]=i;
      return res;
   }

   Permutation& operator*=(Permutation& B){
      vector<int> C(size());
      for(int i=0;i<size();i++) C[i]=B[A[i]];
      A.swap(C);
      return *this;
   }
   Permutation operator*(Permutation& B){ return Permutation(*this)*=B; }
   Permutation pow(Lint K){
      Permutation res=Permutation::I(size());
      Permutation B=*this;
      while(K>0){ if(K&1) res*=B; B*=B; K>>=1; }
      return res;
   }
};

int main()
{
   int N; cin>>N;
   vector<int> x(N);
   for(int i=0;i<N;i++) cin>>x[i];
   int M; cin>>M;
   Lint K; cin>>K;
   vector<int> a(M);
   for(int i=0;i<M;i++) cin>>a[i],a[i]--;

   const int sz=N-1;
   vector<int> d(sz);
   for(int i=0;i<sz;i++) d[i]=x[i+1]-x[i];

   Permutation p=Permutation::I(sz);
   for(int i=0;i<M;i++){
      swap(p[a[i]-1],p[a[i]]);
   }
   p=p.pow(K);

   vector<Lint> ans(N);
   ans[0]=x[0];
   for(int i=0;i<sz;i++){
      ans[i+1]=ans[i]+d[p[i]];
   }
   for(int i=0;i<N;i++) cout<<ans[i]<<endl;
   return 0;
}

まとめ

期待値
行列の累乗は $O(N^{3} \log K)$ 、置換の累乗は $O(N \log K)$
図を書く

感想

結局対称な座標の中点にジャンプするとしてもよいみたいですが、式を書かないと理解できませんでした。期待値に確率をかけることに違和感を感じていましたが、期待値は $(とりうる値)\times(確率)$ の総和なので、この確率のほうに確率をかけていると考えるといい気がします。期待値と置換はまだあまり理解していないので他の問題も解こうと思います。

2019-12-23

ABC148 参加記録

atcoder.jp 1679->1673(-6) 厳しいですね

C. Snack

$lcm(A,B)$ を求めればよいです。 $A \times B = gcd(A,B) \times lcm(A,B)$ より、 $lcm(A,B)=A \times B \div gcd(A,B)$ です。 $gcd$ はC++であれば__gcd(組み込み関数?)を使って求められます。

#include<bits/stdc++.h>
using namespace std;

using Lint=long long;

Lint lcm(int a,int b)
{
   return (Lint)a*b/__gcd(a,b);
}

int main()
{
   int a,b; cin>>a>>b;
   cout<<lcm(a,b)<<endl;
   return 0;
}

D. Brick Break

消す個数の最小値を求める代わりに、残す個数の最大値を求めることにします。そうすると求めるものは、「 $a$ に部分列として含まれる、 $1,2,...$ というような列のうち、長さが最大のものの長さ」です。要するに、左から順番に $1,2,...$ と選んでいったとき、最大でいくつ選べるかということです。これは、次の数を選べる範囲でもっとも左から選ぶことを繰り返せばよいです。~~なぜならば、最も左にあるものを $x$ としたとき、 $x$ を選ばないような最適解が存在するならば、 $x$ を選ぶような最適解も存在するからです。~~直感的には、もっとも左にあるものを選んで損をすることはないからです。

#include<bits/stdc++.h>
using namespace std;

int main()
{
   int N; cin>>N;
   vector<int> a(N);
   for(int i=0;i<N;i++) cin>>a[i];

   int cur=0;
   for(int i=0;i<N;i++){
      if(a[i]==cur+1) cur++;
   }
   cout<<(cur==0? -1:N-cur)<<endl;
   return 0;
}

コンテスト中はDPを書きました。

#include<bits/stdc++.h>
using namespace std;

int main()
{
   int N; cin>>N;
   vector<int> a(N);
   for(int i=0;i<N;i++) cin>>a[i];

   if(count(a.begin(),a.end(),1)==0){
      cout<<-1<<endl;
      return 0;
   }

   const int MAX=*max_element(a.begin(),a.end());
   vector<bool> dp(MAX+1);
   // dp[i]:=(今見ているところまでで)1,2,...iを部分列として含んでいるか
   dp[0]=true;
   for(int i=0;i<N;i++){
      if(dp[a[i]-1]) dp[a[i]]=true;
   }
   int ans=0;
   for(int i=1;i<=MAX;i++) if(dp[i]) ans=i;
   cout<<N-ans<<endl;
   return 0;
}

E. Double Factorial

まず末尾の $0$ の個数というのは、 $10$ を因数としていくつ持つかということです。因数の $10$ の個数は $min(2の個数,5の個数)$ なので、これを数えればよいです。 $N!$ が素因数 $p$ をいくつ持つかは以下の式で計算できます。

$N!$ が持つ素因数 $p$ の個数は $\ \displaystyle \lfloor \frac{N}{p} \rfloor + \lfloor \frac{N}{p^{2}} \rfloor + \lfloor \frac{N}{p^3} \rfloor+ \cdots$

これはこの問題の解説動画で見た記憶があります。
もとの問題に戻ります。 $N$ の偶奇で場合分けをします。

$N$ が奇数の場合
$2$ の個数が $0$ なので答えは $0$ です。
$N$ が偶数の場合
$2$ の個数は $N!$ の場合と同じです(奇数は $2$ で割れないので、無くても変わらない)。 $5$ の個数については、 $f(N)$ を $2$ で何度か割ることによって $(N/2)!$ の場合に帰着できるので求まります。

#include<bits/stdc++.h>
using namespace std;

using Lint=long long;

Lint calc(Lint N,Lint p)
{
   // N!が素因数pをいくつ含むか
   Lint res=0;
   while(N/p>0){ res+=N/p; N/=p; }
   return res;
}

Lint func(Lint N)
{
   if(N<=1) return 0;
   if(N%2==1) return 0;
   else{ return min(calc(N,2),calc(N/2,5)); }
}

int main()
{
   Lint N; cin>>N;
   cout<<func(N)<<endl;
   return 0;
}

上の実装では $N$ を $p^{k}$ で割った結果と、 $N$ を $p$ で $k$ 回割った結果が等しいことを利用しています。これは $p$ 進法で考えると分かります(前者が $k$ 個右シフトしていて、後者は $1$ 個の右シフトを $k$ 回しているため)。実際に $p^{k}$ を計算してオーバーフローしたことがあるので、こうしています。

F. Playing Tag on Tree

めっちゃ解かれているのでおそらくdfsするだけでいいんだろうなぁと思いました(最悪)。直感的には追いつかれないところで一番遠いところに逃げるのが最適だろうと分かりますが、、、

#include<bits/stdc++.h>
using namespace std;

using Graph=vector<vector<int>>;

int main()
{
   int N,T,A; cin>>N>>T>>A;
   T--; A--;
   Graph G(N);
   for(int i=0;i<N-1;i++){
      int a,b; cin>>a>>b;
      a--; b--;
      G[a].push_back(b);
      G[b].push_back(a);
   }
   vector<int> dist(N);
   function<void(int,int)> dfs=[&](int v,int p)
   {
      for(int u:G[v]) if(u!=p){
         dist[u]=dist[v]+1;
         dfs(u,v);
      }
   };

   vector<int> distT(N);
   dist[T]=0; dfs(T,-1); distT=dist;
   vector<int> distA(N);
   dist[A]=0; dfs(A,-1); distA=dist;
   int ans=-1;
   for(int i=0;i<N;i++) if(distT[i]<distA[i]){
      ans=max(ans,distA[i]-1);
   }
   cout<<ans<<endl;
   return 0;
}

感想

ちゃんと理解したら別の記事に書こうと思います。今回はみんな速すぎてビックリしました。

2019-12-22

Codeforces Round #609(Div.2) 参加記録

codeforces.com

1733->1841(+108)
証明: ACをしました

A. Equation

問題

整数 $n$ が与えられます。 $a-b=n$ を満たすような合成数 $a,b$ を求めてください。

制約

$1 \le n \le 10^{7}$
$2 \le a,b \le 10^{9}$

考察

$9n$ と $8n$ を出力すれば良いです。これらは合成数で、制約を満たします。

B. Modulo Equality

問題

$n$ 要素の数列 $a,b$ が与えられます。 $a$ の各要素を $mod\ m$ で $x$ 加算してから並べ替えて $b$ に一致させたいです。このことができる最小の $x$ を求めてください。

制約

$1 \le n \le 2000$
$1 \le m \le 10^{9}$
$0 \le a_{i},b_{i} \lt m\ (1 \le i \le n)$

考察

$a_{1}$ を $b$ の要素のいずれかに一致させなければならないので、これを全探索します。 $b_{i}$ に一致させるときは、 $a_{i}+x \equiv b_{i}(mod\ m)$ を満たす最小の $x$ を選べばよいです。試すべき $x$ の候補が $n$ 通りあって、判定(ソートの部分)に $O(nlogn)$ かかるので計算量は $O(n^{2}logn)$ です。

#include<bits/stdc++.h>
using namespace std;

int main()
{
   int N,M; cin>>N>>M;
   vector<int> a(N),b(N);
   for(int i=0;i<N;i++) cin>>a[i];
   for(int i=0;i<N;i++) cin>>b[i];
   sort(b.begin(),b.end());

   int ans=M;
   for(int i=0;i<N;i++){
      int x=(b[i]-a[0]+M)%M;
      vector<int> c(N);
      for(int j=0;j<N;j++) c[j]=(a[j]+x)%M;
      sort(c.begin(),c.end());
      if(c==b) ans=min(ans,x);
   }
   cout<<ans<<endl;
   return 0;
}

C. Long Beautiful Integer

問題

$n$ 桁の整数 $x$ と正整数 $k$ が与えられます。次の条件を満たす $x$ 以上の整数 $y$ のうち、最小のものを求めてください。
条件: 任意の $i(1 \le i \le |y|-k)$ について $y_{i}=y_{i+k}$ が成り立つ。

制約

$2 \le n \le 2 \times 10^{5}$
$1 \le k \le n$
$x_{1} \neq 0,\ 0 \le x_{i} \le 9(1 \le i \le n)$

考察

条件から、先頭 $k$ 桁を決めると残りの桁も決まることが分かります(先頭 $k$ 桁を繰り返した形になります)。また答えは $x$ 以上でなので、答えの先頭 $k$ 桁は、 $x$ の先頭 $k$ 桁以上でなければなりません。よって、 $x$ の先頭 $k$ 桁を繰り返した数が $x$ 以上であれば、それが答えです。そうでなければ、条件を満たす数うち、次に大きいものは( $x$ の先頭 $k$ 桁+1)を繰り返した数です。これは $x$ より大きいので、これが答えになります。

#include<bits/stdc++.h>
using namespace std;

int main()
{
   int N,K; cin>>N>>K;
   string x; cin>>x;

   string ans;
   for(int i=0;i<N;i++) ans+=x[i%K];
   if(ans>=x){
      cout<<N<<endl<<ans<<endl;
      return 0;
   }
   for(int i=K-1;i>=0;i--){
      if(ans[i]=='9') ans[i]='0';
      else{
         ans[i]++; break; 
      }
   }
   for(int i=K;i<N;i++) ans[i]=ans[i%K];
   cout<<N<<endl<<ans<<endl;
   return 0;
}

繰り上がりに注意しましょう(自省)。

D. Domino for young

問題

$n$ 列の盤面があります。 $i列目(1 \le i \le n)$ の高さは $a_{i}$ です。この盤面に $1 \times 2$ のドミノを重ならないように置くとき、最大でいくつのドミノを置くことができるか求めてください。

制約

$1 \le n \le 3 \times 10^{5}$
$a_{i} \ge a_{i+1}\ (1 \le i \le n-1)$

考察

盤面を市松模様に塗ることで、置けるドミノの個数の上界が分かります( $min(黒の個数,白の個数)$ )。コンテスト中は祈りながら投げました。縦横に2段以上ずれているところを消していけば階段状になるみたいで(ここよく分かってないです)、そうなれば色が少ない方を全部埋められます。

#include<bits/stdc++.h>
using namespace std;

using Lint=long long;

int main()
{
   int N; cin>>N;
   vector<int> a(N);
   for(int i=0;i<N;i++) cin>>a[i];

   Lint cntB=0,cntW=0;
   for(int i=0;i<N;i++){
      cntB+=(i%2==0? (a[i]+1)/2:a[i]/2);
      cntW+=(i%2==0? a[i]/2:(a[i]+1)/2);
   }
   cout<<min(cntB,cntW)<<endl;
   return 0;
}

E. K Integers

転倒数+Absolute Minimaだと聞きました。転倒数は理解できておらず、Absolute Minimaはまだやっていないので、両方やってから戻ってこようと思います。

2019-12-19

ARC063E 木と整数(800)

構築グラフ

atcoder.jp

問題

$N$ 頂点の木が与えられます。各頂点に整数を1つ書き込んで、隣接する頂点に書き込まれている数字の差が $1$ になるようにしたいです。すでに $K$ 個の頂点に数字が書き込まれているとき、条件を満たすように数字を書き込むことができるか判定してください。書き込むことができるならば、例をひとつ構成してください。

制約

$1 \le N \le 10^{5}$
$1 \le K \le N$
$0 \le (書き込まれている数字) \le 10^{6}$

考察

まず、条件を満たすように数字を書き込むことができる必要条件を考えてみます。すでに数字が書き込まれている頂点の集合を $S$ とすると、 $u,v \in S$ に対し、以下が成り立っていなければなりません。

(1) $|num_v-num_u| \le dist(u,v)$
(2) $num_v-num_u \equiv dist(u,v)\ (mod 2)$

一つ辺をたどるごとに数字は多くとも1しか増減しないので、(1)が必要です。また、一つ辺をたどるごとに書かれている数字の偶奇が変わるので、(2)が必要です。

逆にこれらの条件が成り立っていれば、以下の方法で構築することができます。
1. 新たに頂点を1つ作り( $s$ とする)、 $s$ から $v \in S$ にコスト $num_{v}$ の辺を張る
2. $s$ からの最短距離を求める(この最短距離を各頂点に書き込む)

このようにして書き込んだ数が条件を満たしていることを確かめましょう。

$v$ への最短距離が $num_{v}$ と一致していることについて
(1)より $num_{v} \le num_{u}+dist(u,v)$ が成り立つので、 $v$ への最短距離は $num_{v}$ になります。
隣接する頂点の最短距離の差が1になることについて
最短距離の性質より、隣接する頂点の最短距離の差は辺の重み(つまり $1$ )以下です。さらに(2)より、始点 $s$ から隣接する頂点へのパスの長さの偶奇が異なることが分かります¹。よって隣接する頂点への最短距離の差は $1$ になります。

これで、(1)(2)が成り立っているならばこの方法で構築できることが分かりました。また、この方法で構築できなければ(1)または(2)が成り立っていないので、条件を満たす数字の書き込み方は存在しません。よってこの方法で構築してみて、条件を満たしているかどうか確かめることでYesかNoか分かります。²

#include<bits/stdc++.h>
using namespace std;
 
using Graph=vector<vector<int>>;
using P=pair<int,int>;
const int INF=1e9;
 
int main()
{
   int N; cin>>N;
   Graph G(N);
   for(int i=0;i<N-1;i++){
      int a,b; cin>>a>>b;
      a--; b--;
      G[a].push_back(b);
      G[b].push_back(a);
   }
   int K; cin>>K;
   vector<int> num(N,-1);
   for(int i=0;i<K;i++){
      int v,p; cin>>v>>p;
      num[v-1]=p;
   }
 
   vector<int> dist(N,INF);
   priority_queue<P,vector<P>,greater<P>> Q;
   for(int i=0;i<N;i++) if(num[i]>=0){
      dist[i]=num[i];
      Q.push({dist[i],i});
   }
   while(!Q.empty()){
      int v=Q.top().second; Q.pop();
      for(int u:G[v]) if(dist[u]>dist[v]+1){
         dist[u]=dist[v]+1;
         Q.push({dist[u],u});
      }
   }
 
   bool ok=true;
   for(int i=0;i<N;i++){
      if(num[i]>=0 and dist[i]!=num[i]) ok=false;
      for(int j:G[i]) if(dist[i]==dist[j]) ok=false;
   }
   cout<<(ok? "Yes":"No")<<endl;
   if(ok) for(int i=0;i<N;i++) cout<<dist[i]<<endl;
   return 0;
}

まとめ

必要条件を考える
隣接する頂点の最短距離の差は辺の重み以下

感想

必要条件は分かりましたが、そこから進みませんでした。数字の差が $1$ 以下⇒最短距離を書き込めば良さそうと反応できれば良かったと思います。

(2)が成り立っていれば、図のように隣り合う頂点を異なる色で塗りつつ、偶数が書き込まれている頂点が白、奇数が書かれている頂点が黒になるようにできると思います。そうすると始点から白い頂点へのパスの長さは偶数、黒い頂点へのパスの長さは奇数になることが分かります。↩
「解が存在するための必要条件が成り立っているならば構築できる方法」で構築できなければ、(その条件が成り立っていないので)解は存在しないということでしょうか(自問)。↩