2020-02-12

ARC077E guruguru(700)

いもす法

考察

まずは愚直解を考えます。 $x$ を全探索してみます。明るさを $a_i$ から $a_{i+1}$ に変更するときの操作回数は、 $f(s,t)$ を明るさを $s$ から $t$ に変更するときの操作回数の最小値として、 $\min(f(a_{i},a_{i+1}),1+f(x,a_{i+1}))$ です。 $f(s,t)$ は $O(1)$ で計算できるので、全体の計算量は $O(NM)$ です。

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

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

   auto f=[&](int s,int t){ return (t-s+M)%M; };
   lint ans=N*M;
   for(int x=0;x<M;x++){
      lint sum=0;
      for(int i=0;i<N-1;i++){ sum+=min(f(a[i],a[i+1]),1+f(x,a[i+1])); }
      ans=min(ans,sum);
   }
   cout<<ans<<endl;
   return 0;
}

次に高速化を考えます。 $sum_x$ を、お気に入りの明るさを $x$ にしたときの操作回数の合計とします。明るさを $a_{i}$ から $a_{i+1}$ に変更するとき、各 $x$ に対して $sum_x$ にいくら足すかを考えます。

[1] $a_{i} \lt a_{i+1}$ のとき
明るさを $x$ に変更するほうが良いのは $a_{i} \lt x \le a_{i+1}$ の場合だけです。よって $sum_{x}$ には \begin{array}{ll} a_{i} \lt x \le a_{i+1}のとき \quad & 1+(a_{i+1}-x) \\ それ以外のとき & a_{i+1}-a_{i} \\ \end{array} を足せばよいです。
f:id:tekihei:20200212165017j:plain

これらは $x$ の一次関数になっているので、いもす法でできます。どのようにするかというと、例えばインデックスが $x$ のところに $a_{1}x+b_1$ と $a_{2}x+b_{2}$ を足すとすると、これらの合計は $(a_1+a_2)x+(b_1+b_2)$ です。よって、単に1次の係数の和と0次の係数の和を計算しておけば、合計でいくら足したかを求めることができます。

[2] $a_{i} \gt a_{i+1}$ のとき
場合分けが少し厄介ですが、頑張るとできます。もっと楽な方法があるので、説明は省略します。

#include<bits/stdc++.h>
using namespace std;
 
using lint=long long;
 
int main()
{
   int N,M; cin>>N>>M;
   vector<int> a(N);
   for(int i=0;i<N;i++) cin>>a[i],a[i]--;
 
   vector<lint> imos0(M+1);
   vector<lint> imos1(M+1);
   auto add=[&](int l,int r,int a,int b)
   {
      // for x in [l,r] add ax+b
      if(l>r) return;
      imos1[l]+=a; imos1[r+1]-=a;
      imos0[l]+=b; imos0[r+1]-=b;
   };
   for(int i=0;i<N-1;i++){
      int s=a[i],t=a[i+1];
      if(s<t){
         add(0,s,0,t-s);
         add(s+1,t,-1,t+1);
         add(t+1,M-1,0,t-s);
      }else{
         add(0,t,-1,t+1);
         add(t+1,s,0,M+t-s);
         add(s+1,M-1,-1,M+t+1);
      }
   }
   for(int i=1;i<M;i++){
      imos0[i]+=imos0[i-1];
      imos1[i]+=imos1[i-1];
   }
   lint ans=(lint)N*M;
   for(int i=0;i<M;i++){ ans=min(ans,imos1[i]*i+imos0[i]); }
   cout<<ans<<endl;
   return 0;
}

楽な実装方法(円環は2周持つ)

添字が循環する場合は2周持っておくと実装が楽になることがあります。今回の場合は、 $sum_{x}$ と $sum_{x+M}$ の和がお気に入りを $x$ にしたときの操作回数の合計だと思うことにします。そうすると、0をまたいでいたせいで厄介になっていた場合分けがなくなって楽になります。
f:id:tekihei:20200212165601j:plain

#include<bits/stdc++.h>
using namespace std;
 
using lint=long long;
 
int main()
{
   int N,M; cin>>N>>M;
   vector<int> a(N);
   for(int i=0;i<N;i++) cin>>a[i],a[i]--;
 
   vector<lint> imos0(2*M+1),imos1(2*M+1);
   auto add=[&](int l,int r,int a,int b)
   {
      imos1[l]+=a; imos1[r+1]-=a;
      imos0[l]+=b; imos0[r+1]-=b;
   };
 
   for(int i=0;i<N-1;i++){
      int s=a[i],t=a[i+1];
      if(t<s) t+=M;
      add(s+1,t,-1,t+1);
      add(t+1,s+M,0,t-s);
   }
   for(int i=1;i<2*M;i++) imos0[i]+=imos0[i-1],imos1[i]+=imos1[i-1];
 
   lint ans=(lint)N*M;
   for(int i=0;i<M;i++){
      lint sum=(imos1[i]*i+imos0[i])+(imos1[i+M]*(i+M)+imos0[i+M]);
      ans=min(ans,sum);
   }
   cout<<ans<<endl;
   return 0;
}

まとめ

円環は2周もつ
区間に1次関数を足すのはいもす法でできる(1次の係数の和と0次の係数の和をもっておく)

感想

円環が辛かったですが、2周持つと実装がきれいになってすごいなぁと思いました。

2020-02-02

Bitwise ORの最大化・最小化

ビット演算

以下の問題を解いていたときに考えたことです。

atcoder.jp

この問題はbitwise orとしてありうるものを数える問題ですが、今回は最小値と最大値を求めることを考えます。

問題

整数 $A,B$ が与えられます。 $A$ 以上 $B$ 以下の整数から1個以上選んで、それらのbitwise orを取ってできる整数としてありうるもののうち、最大値と最小値を求めてください。

制約

$1 \le A \le B \lt 2^{60}$ (元の問題と同じ制約にしています)

考察

$A = B$ のときは $A$ しか作れないのでどちらも $A$ です。以下では $A \lt B$ の場合を考えます。

最小値について
bitwise ORを取ることによって数が小さくなることはないので、 $1$ 個だけ選ぶ場合を考えれば良いです。この場合の最小値は明らかに $A$ です。

最大値について
bitwise ORを取ることによって数が小さくなることはないので、答えは $A$ から $B$ までの全ての数のbitwise ORです。これを求めることを考えます。 $A$ と $B$ が上位 $k$ 桁まで一致していたとします。そうすると $A$ 以上 $B$ 以下の全ての数の上位 $k$ 桁もこれに等しいので、答えの上位 $k$ 桁はこれと等しいです。
f:id:tekihei:20200202142548j:plain

残りの桁はどうなっているでしょうか。実は(?)残りの桁は全て $1$ になっています。なぜなら $B$ の上から $k-1$ 番目の桁は $1$ で、さらに $A$ と $B$ の間に $k-2$ 桁以下の桁が全て $1$ となるような数が存在するからです。
f:id:tekihei:20200202142620j:plain

実装

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

using lint=long long;

int main()
{
   lint A,B; cin>>A>>B;
   if(A==B){ cout<<A<<' '<<B<<endl; return 0; }

   lint mn=A,mx=B;
   const int LOG=60;
   for(int i=LOG-1;i>=0;i--){
      if((A>>i&1)!=(B>>i&1)){
         for(int j=i-1;j>=0;j--) mx|=1LL<<j; 
         break;
      }
   }
   cout<<mn<<' '<<mx<<endl;
   return 0;
}

感想

どちらもbitwise ORを取って数が小さくなることはないという事実から分かるのが面白いと思いました。元の問題ではbitwise ORの最小値と最大値を求めることを何度かする必要があるので、一番小さい数が最小値、全部のORが最大値になるということが分かっていれば少し見通しが良くなるかなと思いました。

2020-01-30

AGC015D A or...or B Problem(900)

ビット演算数え上げ

atcoder.jp

問題

整数 $A,B$ が与えられます。 $A$ 以上 $B$ 以下の整数から $1$ 個以上選んで、それらのbitwise orを取ってできる整数としてありうるものが何通りあるかを求めてください。

制約

$1 \le A \le B \lt 2^{60}$

考察

$A=B$ の場合は $1$ 通りなので、 $A \lt B$ の場合を考えます。

$AとB$ が上位 $k$ 桁まで一致していたとします。 $A$ 以上 $B$ 以下の数の上位 $k$ 桁はこれと等しいので、bitwise orを取った結果の上位 $k$ 桁も必ずこれに一致します。よって上位 $k$ 桁は無かったことにしても問題ありません。

f:id:tekihei:20200130170228j:plain

上位 $k$ 桁を除くと、 $A \lt B$ より、 $A$ の最上位のビットは $0$ 、 $B$ の最上位のビットは $1$ です。

$A$ 以上 $B$ 以下の整数を最上位のビットが $0$ のグループと、 $1$ のグループに分けてみます。(1)最上位のビットが $0$ のグループから選ぶ場合、(2)最上位のビットが $1$ のグループから選ぶ場合、(3)両方から選ぶ場合、の3通りの場合を考えます。

f:id:tekihei:20200130193823j:plain

最上位のビットが $1$ で、それ以外のビットが $0$ の数を $X$ とすることにします。

(1)最上位のビットが $0$ のグループから選ぶ場合
bitwise orを取ることによって数が小さくなることはないので、最小値は $A$ です。また最上位のビットを立てることはできないので、最大値は $X-1$ です。この間に含まれる数は全て作ることができます(その数自身を選べばよいです)。

(2)最上位のビットが $1$ のグループから選ぶ場合
最小値は $X$ です。すべての数を選んだときに最大になって、これは $B$ の上から $2$ 番目の立っているビット以下を立てた整数です。これを $Y$ とします。 $X$ 以上 $Y$ 以下の整数は全て作ることができます。なぜなら、 $B$ と $X$ の間に、最上位のビットと、( $B$ の $2$ 番目に立っているビット以下の)あるビットのみが立っているような整数が存在するからです。 $X$ とこれらの整数を組み合わせることによって、 $X$ 以上 $Y$ 以下の全ての整数を作ることができます。

f:id:tekihei:20200130200323j:plain

(3)両方から選ぶ場合
まず最小値について考えます。bitwise orを取ることによって数が小さくなることはないので、各グループから一つずつ選ぶ場合を考えれば良いです。最上位のビットが $1$ のグループから選ぶべき整数は $X$ です。もう一方のグループから選ぶ数と $X$ の両方で立っているビットは存在しないので、これらのbitwise orは単純に和になります。よって最小値は $X+A$ だと分かります。また最大値はすべてのビットが立っている数で、これは $2X-1$ です。この間の整数は全て作ることができます( $X$ と $A$ を選ぶ、 $X$ と $A+1$ を選ぶ、 $\cdots\$ 、 $X$ と $X-1$ を選ぶというようにすればよいです)。

以上より、作れる整数の区間は(1) $[A,X-1]$ 、(2) $[X,Y]$ 、(3) $[X+A,2X-1]$ の3つであることが分かりました。あとはこれらの区間の和集合を求めれば良いです。(2)と(3)は交差するときがあるので、場合分けをするか、重複を引く必要があります。

#include<bits/stdc++.h>
using namespace std;
 
using lint=long long;
 
lint get(lint l,lint r){ return r-l+1; }
 
int main()
{
   lint A,B; cin>>A>>B;
   if(A==B){ cout<<1<<endl; return 0; }
 
   const int LOG=60;
   lint X=0,Y=0;
   for(int i=LOG-1;i>=0;i--){
      if((A>>i&1)==(B>>i&1)){
         if(A>>i&1){
            A-=1LL<<i;
            B-=1LL<<i;
         }
      }else{
         X=Y=1LL<<i;
         bool flag=false;
         for(int j=i-1;j>=0;j--){
            if(B>>j&1) flag=true;
            if(flag) Y|=1LL<<j;
         }
         break;
      }
   }
   lint ans=get(A,X-1);
   if(Y<X+A) ans+=get(X,Y)+get(X+A,2*X-1);
   else ans+=get(X,2*X-1);
   cout<<ans<<endl;
   return 0;
}

まとめ

bitwise orを取って小さくなることはない( $a|b \ge a$ )
数え上げで、答えが区間になる

感想

バチャ中に見たときは何をすればいいのか全然分かりませんでした。答えが区間になることが予想できたら、最小値と最大値は何か、その間の数を全部作れるという考察方法を学びました。「最上位のビットで二つのグループに分ける」という考えがどこから出てきたのかがよく分かりませんでしたが、(公式解説にあるように)bitwise orを取った結果が $A$ 以上になると分かったときに、「どこまでなら作れるか」ということを考えたら思いつけるのかなと思いました。

2020-01-26

Codeforces 1285D Dr. Evil Underscores (R1800)

XOR 辞書順分割統治

codeforces.com

問題

要素数 $n$ の数列 $a$ が与えられます。 $\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$ としてあり得る値の最小値を求めてください。

制約

$1 \le n \le 10^{5}$
$0 \le a_i \le 2^{30}-1$

考察

$f(X)= \underset{1 \leq i \leq n}{\max} (a_i \oplus X)$ とします。 $f(X)$ の先頭桁がなるべく小さくなるようにするのがよいので、 $X$ を先頭桁から決めていきます。今 $i$ 桁目を見ているとして、次の3つの場合があります。

(1) $i$ 桁目の数が全て $0$ のとき
$X$ の $i$ 桁目を $0$ にすることで、 $f(X)$ の $i$ 桁目を $0$ にすることができます。

(2) $i$ 桁目の数が全て $1$ のとき
$X$ の $i$ 桁目を $1$ にすることで、 $f(X)$ の $i$ 桁目を $0$ にすることができます。

(3) $i$ 桁目に $0$ と $1$ の両方があるとき
$X$ の $i$ 桁目を $0と1$ のどちらにしても、 $f(X)$ の $i$ 桁目は $1$ になります。 $i$ 桁目が $0$ であるような数の集合を $S$ 、 $1$ であるような数の集合を $T$ とします。 $X$ の $i$ 桁目を $0$ にした場合、 $S$ に含まれる数と $X$ とのxorが最大値になることはないので、次の桁を決めるときは $T$ だけを考えれば良いです。同様に $X$ の $i$ 桁目を $1$ にした場合は、 $S$ だけを考えれば良いです。両方試してよかった方を選びます。

(3)で両方試すと計算量が指数爆発する気がしますが、~~各数が見られる回数は桁数に等しいので~~、図を書くと各桁ごとに $O(n)$ かかっていると分かるので、計算量は $O(n \log \max a_i)$ です。

f:id:tekihei:20200126133147j:plain

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

using Lint=long long;

int rec(int pos,vector<int> &a)
{
   if(pos<0) return 0;
   vector<int> S,T;
   for(auto I:a) (~I>>pos&1? S:T).push_back(I);
   if(S.empty()) return rec(pos-1,T);
   if(T.empty()) return rec(pos-1,S);
   return (1<<pos)+min(rec(pos-1,T),rec(pos-1,S));
}

int main()
{
   int N; cin>>N;
   vector<int> a(N);
   for(int i=0;i<N;i++) cin>>a[i];
   cout<<rec(29,a)<<endl;
}

感想

バチャ中には解けませんでした。この解法も頭を少しよぎりましたが、計算量が指数爆発すると思って除外してしまいました。シンプルな問題設定でとても好きです。

2020-01-25

ACPCVC2020

取り組み方(自分向け)

コンテスト中

なるべく全部の問題に目を通します。問題分が簡潔なものから読んで、できそうだったら考えます。時間がかかりそうor無理そうだったら次の問題に移ります。

コンテスト後

コンテスト中に解けるのは大体0問か1問です。現在の実力を考慮すると、全ての問題を解けるようにするのは時間的にも精神的にも厳しいです。そこで、3問の中から一番惜しかった1問を選んで理解して解説を書くことにしようと思います。

問題一覧

2020/02/12(Wed)

	A	B	C
問題	Flip and Rectangles	Fountain Walk	Sandglass
結果	WA		WA

今回の一問: Flip and Rectangles

2020/02/10(Mon)

	A	B	C
問題	Coins	Namori Grundy	Young Maids
結果	AC

今回の一問: Young Maids

2020/02/05(Wed)

	A	B	C
問題	Awkward Response	Mole and Abandoned Mine	Sports Festival
結果		WA

今回の一問: Mole and Abandoned Mine

2020/02/03(Mon)

	A	B	C
問題	Colorful Hats	Connected?	guruguru
結果	AC	-	WA

今回の一問: guruguru tekihei.hatenablog.com

2020/01/29(Wed)

	A	B	C
問題	A or...or B Problem	Mirrored	+/- Rectangle
結果	-	-	AC

今回の一問: A or...or B Problem tekihei.hatenablog.com

2020/01/27(Mon)

	A	B	C
問題	Lotus Leaves	RGB Sequence	Nuske vs Phantom Thnook
結果	-	-	-

今回の一問: RGB Sequence

2020/01/22(Wed)

	A	B	C
問題	Ball Coloring	Closed Rooms	Black and White Tree
結果	WA	-	-

今回の一問: Ball Coloring

2020/01/20(Mon)

	A	B	C
問題	Alice in linear land	Dam	Many Moves
結果	-	-	WA

今回の一問: Many Moves

2020/01/15(Wed)

	A	B	C
問題	Splatter Painting	Ants on a Circle	Piling Up
結果	WA	-	-

2020/01/13(Mon)

不参加

2020/01/08(Wed)

不参加

2020/01/06(Mon)

	A	B	C
問題	Addition and Subtraction Hard	K-th K	Tournament
結果	-	AC	-

2020-01-23

Codeforces 1284C New Year and Permutation (R1700)

数え上げ

codeforces.com

問題

整数 $n,\ m$ が与えられます。長さ $n$ の順列 $p$ のスコアを
$\max \{p_l, \ldots, p_r\}-\min\{p_l, \ldots, p_r\}=r-l$ を満たすような組 $(l,r)\ (1 \le l \le r \le n)$ の個数
とします。長さ $n$ の全ての順列のスコアの合計を $\bmod m$ で求めてください。

制約

$1 \le n \le 250000$
$10^{8} \le m \le 10^{9}$
$m$ は素数

考察

$\max \{p_l, \ldots, p_r\}-\min\{p_l, \ldots, p_r\}=r-l$ という条件について
部分列の長さを $len(=r-l+1)$ 、最小値を $m$ とおきます。この部分列が条件を満たすとすると、最大値は $m+len-1$ です。この部分列の長さを $len$ にするためにはあと $len-2$ 個の要素を追加しなければなりませんが、 $m$ より大きく $m+len-1$ より小さい要素が $len-2$ 個しか残っていないので、追加する数は一意に定まります。結局この条件は、 $p[l,r]$ が連続する整数からなる、という条件だと分かります。

全ての順列について部分列の個数を数える代わりに、各部分列が何回数えられるかを考えます。ある部分列が同じ順列に二度以上含まれることはないので、その部分列を含むような順列の個数が求めるものです。

まずは具体的な例で考えてみましょう。例えば $n=7$ のとき、 $a=(2, 3, 5, 4)$ を含む順列がいくつあるかを考えます。これは $a$ の位置が $4$ 通り、各場合について残りの要素の並べ方が $3!=6$ 通りあるので $4 \times 6=24通り$ あることが分かります。

これを全ての条件を満たす部分列について求めて足し合わせたものが答えです。この値は部分列の長さだけによるので、同じ長さの部分列をまとめて数えることができます。長さ $k$ の条件を満たす部分列は $(n-k+1) \times k!$ 通りあるので、結局答えは $\sum_{k=1}^{n} (n-k+1) \times k! \times (n-k+1) \times (n-k+1)!$ です。

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

using Lint=long long;

int main()
{
   int n,mod; cin>>n>>mod;
   vector<int> fact(n+1);
   fact[0]=1;
   for(int i=1;i<=n;i++) fact[i]=(Lint)i*fact[i-1]%mod;

   int ans=0;
   for(int k=1;k<=n;k++){
      ans+=(Lint)(n-k+1)*(n-k+1)%mod*fact[k]%mod*fact[n-k]%mod;
      ans%=mod;
   }
   cout<<ans<<endl;
   return 0;
}

感想

「すべての場合について~を求めて足し合わせた結果を求める」という問題は、各要素の寄与を考えるのが典型です。すべての要素について考えられない場合は、うまくまとめて数える必要があります。全探索できるパラメーターを考えたら長さが見つかって、解けました。

2020-01-22

CodeForces 1286A Garland (R1700)

codeforces.com

問題

長さ $N$ の数列 $p$ が与えられます。これは長さ $N$ の順列の一部が欠けたもので、欠けたところは $p_i=0$ になっています。 $p$ が順列になるように復元したときの、 $p$ の複雑さの最小値を求めてください。ここで $p$ の複雑さとは、隣接要素のペアであって、偶奇が異なるようなものの個数とします。

制約

$1 \le N \le 100$
$0 \le p_i \le N\ (1 \le i \le N)$

考察

偶奇だけが重要なので $mod\ 2$ で考えます。まず、 $p$ を $2$ で割った余りで置き換えておきます( $p_i=0$ だったところは $p_i=-1$ とします)。左から順番に復元していくことにします。すると、それまでに使った $0と1$ の個数と、最後の要素の偶奇が同じであれば、後のことを考えるとコストが小さいほうがよいので、次のようなDPが考えられます。

$$ dp[i][j][k]:=左からi個復元して、それまでで0をj個使っていて、最後の要素の偶奇がkのときのコストの最小値 $$ 使った $1$ の個数は $i-j$ なので状態として持たなくて良いです。

$dp[i][j][k]$ からの遷移は

$0$ を置く場合 $$ chmin(dp[i+1][j+1][0],dp[i][j][k]+k) $$
$1$ を置く場合
$$ chmin(dp[i+1][j][1],dp[i][j][k]+(k\ xor\ 1)) $$

です。 $0$ と $1$ が置ける個数はそれぞれ $\lfloor N/2 \rfloor$ と $\lceil N/2 \rceil$ なので、これを超えないようにしなければなりません。

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

const int INF=0x3f3f3f3f;
int dp[110][110][2];

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

   if(N==1){ cout<<0<<endl; return 0; }

   for(int i=0;i<N;i++){
      if(p[i]==0) p[i]=-1;
      else p[i]=p[i]%2;
   }

   memset(dp,INF,sizeof(dp));
   if(p[0]==0 or p[0]==-1) dp[1][1][0]=0;
   if(p[0]==1 or p[0]==-1) dp[1][0][1]=0;

   for(int i=1;i<N;i++) for(int j=0;j<=i;j++) for(int k=0;k<2;k++) if(dp[i][j][k]<INF){
      if((p[i]==0 or p[i]==-1) and j<N/2){
         dp[i+1][j+1][0]=min(dp[i+1][j+1][0],dp[i][j][k]+(k^0));
      }
      if((p[i]==1 or p[i]==-1) and i-j<(N+1)/2){
         dp[i+1][j+0][1]=min(dp[i+1][j+0][1],dp[i][j][k]+(k^1));
      }
   }
   cout<<min(dp[N][N/2][0],dp[N][N/2][1])<<endl;
   return 0;
}

すでに数字が置かれているところも置かれていないとしています(置く数は決まっている)。こうすると最初に $0$ をたくさん使ってしまって、すでに決まっているところで置けないみたいになることがありますが、そのようなところからは遷移しないようにしているので大丈夫です。

感想

すでに置かれているところも新たに置くことにすると実装が軽くなりました。Editorialには貪欲法が書かれていましたがよく分かりませんでした。