競技プログラミング練習記 No.51【ABC111練習】

初回 -> はじめに

ABC111を解きました。
3完です！
D問題は部分点がもらえるところまで解きました。

問題	時間	アルゴリズム	実行時間
A	2min	-	8ms
B	2min	-	9ms
C	34min	ヒストグラム	26ms
D	54min	-	9ms

まとめ

先にまとめを載せます。これ自体は最後に書いてます。

順番が不要で数字の出現回数が必要な時はヒストグラムを使います。

ヒストグラムはstd::mapに保存するといいですが、場合によってはstd::vectorを使った方がいいです。
実行速度が速くなり、メモリ使用量を抑えられることがあります。

A - AtCoder Beginner Contest 999

  string s;
  cin >> s;
  for(int i = 0; i < 3; ++i)
  {
    if (s[i] == '1') cout<< '9';
    if (s[i] == '9') cout<< '1';

文字列で入力を受け取り、1文字ずつ判定して "1" なら "9"、"9" なら "1" を出力しました。

B - AtCoder Beginner Contest 111

  int n;
  cin >> n;
  for(int i = 111; i <= 999; i += 111)
  {
    if  (n <= i)
    {
      cout << i;
      return;
    }
  }

111から999まで111刻みでループを回し、入力値より以上になった時点の値が答えになります。
境界値に注意です。

C - ////

using P = pair<int, int>;
  int n, v1, v2;
  cin >> n;
  vector<int> hist1(100003, 0);
  vector<int> hist2(100003, 0);
  for(int i = 0; i < n / 2; ++i)
  {
    cin >> v1 >> v2;
    hist1[v1]++;
    hist2[v2]++;
  }

  vector<P> h1{ P(0, -1) };
  vector<P> h2{ P(0, -1) };
  for(int i = 0; i < (int)hist1.size(); ++i)
  {
    if (hist1[i] > 0) h1.emplace_back( P(hist1[i], i) );
  }
  for(int i = 0; i < (int)hist2.size(); ++i)
  {
    if (hist2[i] > 0) h2.emplace_back( P(hist2[i], i) );
  }
  sort(h1.rbegin(), h1.rend());
  sort(h2.rbegin(), h2.rend());

  ll ans = 0;
  int i1 = 0, i2 = 0;
  if (h1[0].second == h2[0].second)
  {
    if (h1[0].first == h2[0].first)
    {
      h1[1] > h2[1] ? i1++ : i2++;
    }
    else
    {
      h1[0] < h2[0] ? i1++ : i2++;
    }
  }
  ans = n - h1[i1].first - h2[i2].first;
  cout << ans;

この問題は偶数番目と奇数番目であること以外の順番は情報として不要ですね。
必要なのは数字の出現回数です。
そういう時はヒストグラムを使います。
偶数番目か奇数番目かの情報はいるので、それぞれ別にヒストグラムを用意します。

偶数番目のヒストグラム
奇数番目のヒストグラム
を作った後、偶数番目と奇数番目のそれぞれで一番出現回数が多かった数字に書き換えればその書き換えた回数が答えになります。
ただ、一つ注意なのが偶数番目と奇数番目で同じ数字に書き換えることはできません。
偶数番目と奇数番目とで出現回数を比較して、全体の書き換える回数が少なくなるように処理します。

はじめはヒストグラムにstd::mapを使っていたのですが、std::vectorを使った方が良い結果になりました。
というのも、std::mapを使う場合に比べてメモリ使用量と実行時間が約半分になりました。
さらに、現時点でC++ (GCC 9.2.1)で解いた人の中で2番目に速いコードになりました。嬉しい。
std::mapのほうが良いと思っていたのでびっくりです。
このあたり、何が良いかは言語の仕様が深く絡んでくるのでよくわかりません。。。

D - Robot Arms

  int n, x, y;
  cin >> n;
  bool odd = true;
  int size = 20;
  vector<string> ans(n);
  for(int i = 0; i < n; ++i)
  {
    cin >> x >> y;
    if (i == 0)
    {
      odd = ((abs(x) + abs(y)) & 1);
      size += odd;
    }
    if (((x + y) & 1) != odd)
    {
      cout << -1;
      return;
    }
    if (abs(x) + abs(y) > 20)
    {
      cout << -1;
      return;
    }

    for(int h = 0; h < abs(x); ++h)
    {
      ans[i] += x < 0 ? 'L' : 'R';
    }
    for(int v = 0; v < abs(y); ++v)
    {
      ans[i] += y < 0 ? 'D' : 'U';
    }

    while (ans[i].length() < size)
    {
      ans[i] += "LR";
    }
  }

  cout << size << endl;
  for(int i = 0; i < size; ++i) cout << 1 << " ";
  cout << endl;
  for(const auto& a : ans)
  {
    cout << a << endl;
  }

入力のx座標 + y座標の偶奇が一致している場合に答えが出せます。
偶奇が一致していなければ表現不可能となり、 -1 を出力して終了です。

部分点の入力はX, Yが[-10, 10] なので、この場合を考えます。
原点からのマンハッタン距離を考えると、最長でも20になります。
マンハッタン距離といえば、長さが1のアームを最大で20個つなげれば同様の表現ができますね。
アームの本数が40以下の任意の数なのでできる解法です。

最短で目的の座標まで移動した後、LRやUDなど、元の位置に戻ってくる操作を繰り返せば答えになります。
なかなか脳筋な解法です笑
マジメに解く方法はわかりませんでした。

以上です。ありがとうございました。