SRM 551

結果報告

250-450-1000のセット。

Level	ProblemName	Status	Point
Easy	ColorfulChocolates	FailedSystemTest(practiced)	0.0
Medium	ColorfulWolves	Opened(practiced)	0.0
Hard	--	Unopened	0.0

青コーダー降格しました。
と言うか問題文読み間違えまくるわ凡ミスするわダメポ。
最近黄色コーダーに残留できればいいや、くらいの気分になっていたのも反省。気を引き締めろってことでしょう。

Easy ColorfulChocolates

問題

色分けされたチョコレートが一列に並んでおり、その配置がA〜Zを用いたstringとして与えられる。アルファベット一つがひとつの色を表す。
maxSwapsというスワップ回数が規定されており
このスワップ回数の中で、最大どのくらいの同色チョコレートを連続して並べることができるか？

考えたこと

（ここから誤答）
長さlのとある領域を考えて、そこに何らかの色をswapで持ってこれるかどうか調べれば良いんじゃないの？
つまり、ある色Cで、色Cのチョコレートがl個以上あり、
領域中の色Cのチョコレートの数＋maxSwaps >= l だったら、l個のチョコレートを並べることができる。
これをlを増やしながら判定し続けていけば良いだろう。
かいた。
あれ、サンプルあわない？
（ここまで誤答）
……
………
swapって隣り合わせのチョコの入れ替えしかできないのかよ

という訳で考えなおす。
しかしそうするとどうしたら良いんだろうな…？

とりあえず、色を固定して考える。
色Aが左から0番目、3番目、5番目、8番目、13番目…という風に存在した場合
これらの中からl個を隣り合わせにしようとしたら、l個の連続した（？）Aを使う。
例えば、３個のAを隣り合わせにしようとするなら、
0,3,5番目を使うか、3,5,8番目を使うか、5,8,13番目を使う…という感じ。
この時のswap回数は、真ん中の場所に集めるようにswapさせた方が一番良い。
（偶数個の場合は、真ん中のどちらか）
そんな感じで実装しよう。

うわー、サンプル通ったけどぐちゃぐちゃ過ぎわろす…でも時間無いし提出するよ。

提出したよ。

……System Test Failed＼(^o^)／

方針は良かったっぽいのだけれど、
[a, a+length)の中点を(a+length)/2としていた点と、
何故かZの探索漏れがあった事が原因でした。

コード

相変わらずスパゲッティ。
わざわざ真ん中に集める…というごちゃごちゃしたこと考えなくても、
何処か一つに集める、としたほうがミス少なかったかもしれない。

    int counts[50];
    int mswp;
    vector<int> pos[30];
    
  bool possible( string chocolates, int range ){
    int size = chocolates.size();
    //cout << range << endl;
    for( int k = 0 ; k <= 'Z'-'A' ; k++ ){
      if((int) pos[k].size() >= range ){
        //cout << (char)(k+'A') << endl;
        for( int l = 0 ; l+range-1 < (int)pos[k].size(); l++ ){
          int middle = l+(range)/2;
            int dist = 0;
            for( int r=0; r < range; r++ ){
              dist+= abs(pos[k][l+r]-pos[k][middle])-abs((l+r)-middle);
            }
            //cout << endl;
            //cout << dist<<endl;
            if( dist <= mswp ) return true;
          if( range%2==1){
            middle--;
            int dist = 0;
            for( int r=0; r < range; r++ ){
              dist+= abs(pos[k][l+r]-pos[k][middle])-abs((l+r)-middle);
            }
            if( dist <= mswp ) return true;
          }
        }
      }
    }
    return false;
  }
  int maximumSpread(string chocolates, int maxSwaps) {
    int result=0;
    mswp=maxSwaps;
    int size = chocolates.size();
    for( int k = 0 ; k <= 'Z'-'A' ; k++ ){
      pos[k].clear();
    }
    for( int k = 0 ; k < size; k++ ){
      pos[chocolates[k]-'A'].push_back( k ); 
    }
    for( result = 1 ; result < size; result++){
      if( !possible( chocolates, result+1) )break;
    }
    return result;
  }

Medium ColorfulWolves

問題

狼さんは一日一回体毛の色を変えることができる。色の種類はで表すとする。
i色からj色に色チェンジ可能なところはY、不可能なところはNといった形で、vectorによってその遷移規則は決められている。
狼は、翌日複数の色に遷移可能の時、はじめての色で最も番号の小さい色に遷移する。
観察者は、狼さんが色番号0から色番号Cまで遷移する様子を見届けたい。
しかし、狼さんは色番号Cにまで遷移しない場合もある。
観測者は、狼の遺伝子を操作して、幾つかのYをNにする事が可能である。
狼さんがC色になるために必要な最小遺伝子操作数を答えよ。
どう遺伝子操作しても狼さんをC色にできない場合は-1を返せ。

考えたこと

Easyが散々だったしMediumで挽回だ！450だしね！
と思って問題を急いで読む。
……え、なに、0からCまでの最短路を答えるだけ？（←当然間違い）
と思ってダイクストラをサクッと書く。
サンプルあわない＼(^o^)／
ここではじめて、狼の遷移規則が、最も番号の小さい新しい色に遷移する、ということに気づく。
それを反映してみる。
当然色々サンプル合わない……と言うかこの遷移規則なら経路一意じゃね？
問題文読みなおす。
……んー、ちゃんと理解できているのかよくわからない。
とりあえずdfs書けばいいんですか？
かいた。
……あ、はい、TLEですよね、そりゃそうですよね。
→時間切れ

テンパりすぎわろす＼(^o^)／

チャレンジフェーズにて

なんでこんなにみんなMedium解いてるんですか……
診断人さんと相部屋だったのでコードを拝見。

……ワーシャルフロイド……だと……

馬鹿な、最短路で解ける問題じゃなかったはず……写経開始

……
…………
どうやら、iからjに遷移するためには、0からj-1番目までの、iから遷移可能な色の個数分の重みをつける、という方針らしい。
でもこれ、0->5->i->jみたいに遷移する時には、i->5が遷移可能だったとしても、その箇所の遺伝子は操作しないでいいんじゃないの？

わからん……

コンテスト終了後

うーん、やっぱり上述の疑問が解決できない。
"NYNNNN",
"NNYNNN",
"NYNNNY",
"NNNNNN",
"NNNNNN",
"NNNNNN"
これ入れても1が望まれる答えらしいし、やっぱりわからん。

……多分、まだ問題文を読み間違えてるんだよね。多分。
”はじめての色で、最も番号の小さい色に遷移する”っていうのが、
iから遷移できる色が複数ある時、これまでにiから遷移したことの無い色で、最小添字のもの、という意味なんだろうか。
それだと
"NYY",
"YNN",
"NNN"
は答えが0になるはずだよね。0->1->0->2、みたいに遷移できるわけで。

……あれぇ。。。

とりあえずSystemTestの通るサンプルコードは出しておいた。

コード

  int getmin(vector <string> colormap) {
    int result;
    int map[51][51];
    int size = colormap.size();
    for( int i = 0 ; i < size; i++ ){
      int tmp = 0;
      for( int j = 0 ; j < size; j++ ){
        if(colormap[i][j]=='Y'){
          map[i][j] = tmp;
          tmp++;
        }
        else{
          map[i][j] = INT_MAX/2;
        }
      }
    }
    bool arrived[51];
    memset( arrived, false, sizeof( arrived ) );
    priority_queue< pair<int,int> > q;
    q.push( make_pair(0, 0) );
    while( !q.empty() ){
      pair<int,int> p = q.top();
      q.pop();
      int po = p.second;
      int di = p.first;
      if( arrived[po] ) continue;
      arrived[po] = true;
      if( po == size-1 ) return -di;
      for( int k = 0 ; k < size; k++ ){
        if( !arrived[k] && map[po][k]!=INT_MAX/2 ){
          q.push( make_pair( di-map[po][k], k) );
        }
      }
    }
    return result=-1;
  }

うーん、納得いかない

補足

”はじめての色で、最も番号の小さい色に遷移する”の前半を無視して、
"最も番号の小さい色に遷移"と解釈すればこの方針で意味が通るということがわかった。
smallest new とは何だったのか…