Single Round Match 445 Div2

すごく久しぶりだ。ここしばらくレンダラーいじったりしてC++に触れていたせいか、だいぶ回復したように思える。後10分くらい回答時間があるけど全部submitしたのですることがない(いや撃墜の準備とかを普通はするんだろうけど)

テストで落ちないことを祈りながらさっさと寝ようかなぁ。

とか言っているうちにコーディングフェーズが終わった。コードと解説を書くことにしよう。

まず300ポイント問題。これはアルファベットa-zで文字列が与えられるので、それの換字暗号のうち辞書順に最も早いものを返せという問題。与えられた文字列を頭から順に見て行って、まだ変換してない時があれば一番若い字に置き換えればいい。

string result(N, '*');の引数を逆にしていて怒られた。

  string encrypt(string message) {
    size_t N = message.size();
    string result(N, '*');
    char to = 'a';
    for(size_t i=0; i<N; i++){
      if(result[i] == '*'){
	char frm = message[i];
	for(size_t j=i; j<N; j++){
	  if(message[j] == frm){
	    result[j] = to;
	  }
	}
	to++;
      }
    }
    return result;
  }

500ポイント問題。座標がいくつか与えられるので、真北にも真南にも真西にも真東にもその与えられた座標の中の点があるような点はいくつあるか答えなさいという問題。

座標が-100..100の整数なので200 * 200で全部試しても40000個。全部試せばいい。40000個の点について毎回最大50個の与えられた頂点をチェックしてもそれでも大したこと無いんだけど、フラグを立てる方を先に思いついたのでそれで書いた。

最初 |= の所を += にしていたのでテストに通らなかった。

  int count(vector <int> xs, vector <int> ys) {
    vector<int> map(40000);
    size_t N = xs.size();
    for(size_t i=0; i<N; i++){
      size_t x = xs[i] + 100, y = ys[i] + 100; // map to 0..200
      for(size_t j = 0; j < x; j++){
        map[j + y * 200] |= 1;
      }
      for(size_t j = x + 1; j <= 200; j++){
        map[j + y * 200] |= 2;
      }
      for(size_t j = 0; j < y; j++){
        map[x + j * 200] |= 4;
      }
      for(size_t j = y + 1; j <= 200; j++){
        map[x + j * 200] |= 8;
      }
    }
    return std::count(map.begin(), map.end(), 15);
  }

1000ポイント問題。n桁の0から初めて、いくつかの0を1に変えるか、いくつかの1を0に変えるか、を繰り返す。ただし同じ数字を繰り返しては行けないし、複数の選択肢があるなら一番小さいものを選ばなければならない。というルールで順番にn桁の数値を作って行く。k個目は何か、という問題。

3桁と4桁のときを紙に書いてみて「常に変わるのは一桁だけだな」と判断(間違い)、実装したらテストケースの最後のものだけ通らない。あれー。

10分ほど悩んでから「1から0に戻すときは1個とは限らない。たくさんまとめて0にすることでより小さくなるならそれが選ばれる」ということに気付く。ということは減らすときにはすでに立っている1のどれを選んで0にするかの全パターンの探索が必要か。コードが面倒だぞ。

そして「って桁数の上限が10ってことは、最大限にビットが立っていても1024通りでいいのか」と気付く。無駄は多いけど気にしないことにした。

  string password(int n, int k) {
    int key = 0;
    vector<int> used;
    used.push_back(key);
    for(int days=1; days < k; days++){
      int minnext = 1024; 
      for(int i=0; i<n; i++){
	int newkey = key ^ (1 << i);
	if(newkey < minnext){
	  if(find(used.begin(), used.end(), newkey) == used.end()){
	    minnext = newkey;
	  }
	}
      }
      for(size_t i=0; i<1024; i++){
	int newkey = key & i;
	if(newkey < minnext){
	  if(find(used.begin(), used.end(), newkey) == used.end()){
	    minnext = newkey;
	  }
	}
      }
      key = minnext;
      used.push_back(key);
    }
    // int to string
    return int2str(key, n);
  }

これでとりあえず3問ともテストには通ったのでsubmit。そして頑張る気力がなくなったのでチャットでまったりと会話したりしていた。このエントリーをここまで書いたところでチャレンジフェーズが終了。とりあえず今のところ撃墜されてはいない。システムテストに通るといいなー。

---

おやー。500ポイントを失敗した。むー、はっ、-100..100だったら200じゃなくて201じゃないか！