yukicoder contest 234 - tekiheiの日記

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