読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

yukicoder 197/198

見やすさを維持するのと負担軽減のために問題数が4問以上のときは分割します。

- 197 手品

思いつくのは10秒かからなかったけど実装に10分ぐらいかかった()

  • 問題概要

一列に並んだ3個のハットの中にボールがいくつか配置されていて、K回ハットの位置を交換した後、ハットをオープンする。
交換前と交換後のボールの位置が与えられるのでその状態が実現可能か応えよという問題です。
ハットの交換は隣同士のハットしか不可能です。
こんな感じのミニゲームパワポケ1にあった気がしますね。
確かコップだった気もしますが。

  • 解説

ボールが増えたり減ったりしてたらもちろんアウトです。
xoo,oxxのような場合は真ん中と右で交換を繰り返せば回数が稼げて、oxxやxooの場合もおんなじです。
数が大きいときはこの操作をすれば回数が稼げます。
したがって回数が大きいときはボールの数さえ合っていればどんな交換だって可能となります。
数が小さいときにできないかどうかの制約ができてくるので条件分岐をしましょう。

と思って本番中は条件分岐をして結果ソースコードが長くなりました。
もっと簡単な方法を今さっき思いつきました。
min(K,4)回ぐらい実際に交換するパターンをすべて試してやればよいのです。数が大きいときは4回で実現できるなら絶対に実現できます。たぶん3か2でも大丈夫ですが念のため4です。
bit演算で0のとき左と交換、1のとき右と交換とすれば超簡単に実装できます。

エディタ使わず直接書いたのでちょっと見づらいのはご勘弁を

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(void){
string s,t;
int N;
cin>>s>>N>>t;
N=1<<min(N,4);
bool flag=false;
for(int i=0;i<N;i++){
string u=s;
for(int j=0;(1<<j)<N;j++)
if((1<<j)&i)swap(u[0],u[1]);
else swap(u[2],u[1]);
if(u==t)flag=true;
}
if(flag)cout<<"FAILURE"<<endl;
else cout<<"SUCCESS"<<endl;
return 0;
}

- 198 キャンディー・ボックス2

  • 問題概要

キャンディーがN個の箱にいくつかずつ入っててA君はキャンディーをB個持ってる。
箱からキャンディーをとったり箱に追加したりしてすべての箱に入れるキャンディーを同じにしたい。
1個ずつしか操作できないとして、操作回数は最小で何回になるか応える問題です。

  • 解説

想定解は三分探索でコンテスト中も三分探索っぽいなとは思ったけど三分探索実装したことがなかったので別解法です。
まずすべての箱を先にソートしておきます。
i番目にキャンディー数が少ない箱にもともと入っているキャンディーの数をC_iとすると、
i番目の箱のキャンディーの数をM個にする場合に必要な操作は|M-C_i|回です。
したがってすべての箱のキャンディーの数をM個にする場合に必要な操作は\sum_{i=1}^N |M-C_i|回です。
すべてのMについて調べるとTLEなのでここから分解していきます。
C_j \le M < C_j+1の場合について考えます。上の式の絶対値を外すと、
\sum_{i=1}^N |M-C_i| = \sum_{i=1}^j (M-C_i) + \sum_{i=j+1}^Nj (C_i -M)となります。
さらに、k=N-jとすると、\sum_{i=1}^N |M-C_i|=(j-k)*M - \sum_{i=1}^j C_i + \sum_{i=j+1}^N C_iとなります。
C_j \le M < C_j+1の場合は後半のシグマ部分が固定なので、
操作回数を最小にするにはj-kが負のときはMを大きく、正のときはMを小さくそれぞれMの値をC_j,C_j-1とすればよい。
それを全てのjについて試してやればよい。あとM=C_Nの場合もあるのでそれも追加で試す。
あとは存在するキャンディーの個数が\sum_{i=1}C_i +BなのでM*Nがそれを超えないように調整すればOKです。
よってM=C_i,C_{i+1}-1,\frac{\sum_{i=1}C_i +B}{N}のだいたい20通りについて試してやればOKです。

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>

using namespace std;
#define LL long long

LL B, N, C[10];
LL Csum[10];
int main(void){
    LL res = 10000000000LL;
    cin >> B >> N;
    for (int i = 0; i < N; i++){
        cin >> C[i];
        Csum[i] = C[i];
    }

    sort(C,C+N);
    sort(Csum, Csum + N);
    for (int i = 1; i < N; i++)Csum[i] += Csum[i - 1];
    for (int i = 0; i < N; i++){
        LL m = i + 1;
        LL n = N - m;
        LL x;
        if (C[i] * N > Csum[N - 1] + B)continue;
        if (m - n >= 0)x = C[i];
        else x = min(C[i + 1] - 1, (Csum[N - 1] + B)/N);


        res = min(res, (m - n)*x - (Csum[i]) + (Csum[N - 1] - Csum[i]));
    }

    cout << res << endl;

    return(0);
}