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;
}