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

夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

難問回

今回は全体見ても難問回でした。
結果は以下
oxx-
1024->1058(+34)
それにしてもSystemTestが異常に早かった←

(過去問)CreateGroups

-1の判定が割り算で最初やっていておかしくなってたので、掛け算になおしました。
1WA

class CreateGroups {
public:
    int minChanges( vector <int> groups, int minSize, int maxSize ) {
        int sz=groups.size();
        int less=0, more=0, sum=0;
        for (int i=0; i<sz; i++) {
            if (groups[i]<minSize) less+=minSize-groups[i];
            if (groups[i]>maxSize) more+=groups[i]-maxSize;
            sum+=groups[i];
        }
        if (sum<minSize*sz||maxSize*sz<sum) return -1;
        return max(more,less);
    }
};

(Easy)UnsortedSequence

ソートしていない数列を返す摩訶不思議な問題です。
英語むずかしくて、問題がわかりにくいのですが、返すのはソートしていない数列の辞書順最小、つまり最大値とその次にでかい値がソート列から一個だけいれかわったものです。
あとは普通にソートしてやるだけです。

class UnsortedSequence {
public:
   vector <int> getUnsorted( vector <int> s ) {
    vector<int> empty;
    if (s.size()==1) return empty;
    sort(s.begin(), s.end());
    bool flag=true;
    int most=s[s.size()-1];
    for (int i=s.size()-2; i>=0; i--) {
        if (most!=s[i]) {
            swap(s[i],s[i+1]);
            flag=false;
            break;
        }
    }
    if (flag) return empty;
    else return s;
   }
};

Medium

かなり難しいDPです。
DPということはわかったんですがまったく漸化式わかりませんでした。
他人のコードみても理解できてません(汗)
問題はN曲をP曲のプレイリストにするとき、かならず最低一回ずつ流れて、かつ同じ曲は間にM曲別の曲がはさまってないと流してはならないという規則にしたがい作れるプレイリストの場合の数をmodとって求めます。
漸化式は以下のようになるようです。

f(i,j):=i曲のプレイリストをj曲で構成するときの場合の数
f(0,0)=1
f(i,j)=(f(i-1,j-1)*(N-j+1)%MOD+f(i-1,j)*max(j-M,0)%MOD)%MOD

どういうことでしょう?
追記: それなりに考えてみたのでまとめます。
まずf(i,j)の解釈はN曲のうちj曲だけ使ってと考えるべきであるようです。
そしてf(i-1,j-1)*(N-j+1)の項はこの解釈でいくとプレイリストのリミットと曲のリミットを増やした時、それまでに使ってない曲のいずれか一曲を使えばいいのでこの式はたしかに成り立っています。よりわかりやすく変形するとこれはつまりf(i-1,j-1)*(N-(j-1))を表しているようです。
次にf(i-1,j)*max(j-M,0)についてですが、これはリミットが増え、使う曲数が変わっていないので、j曲のなかのいずれかをもう一回使うことになります。しかしながら、そのうちのM曲は再度使用できない状況にあるのでj-M曲だけ再利用でき、またj

Hard

最小全域木の応用っぽい問題。
閉路判定Union-Findとか思っていたんですがどうやら単純にDFSでやるそうで・・・
まぁ力不足でこれは解けませんでした。

広告を非表示にする