AtCoder Beginner Contest 160に参加した話。

AtCoder Beginner Contest160に参加。

結果は以下。

Ranking: 885th / 9745
Performance: 1594
Rating: 815 → 929

F問題解きたかった。

A - Coffee

3文字目と4文字目が等しくかつ5文字目と6文字目が等しい時にYes、そうでなければNoを出力する問題。1:15でAC。

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using ll = long long;
#define chmin(i, j) i = min(i, j);
#define chmax(i, j) i = max(i, j);
#define rep(i, n) for(int i=0;i<n;i++)
int main() {
  string s;
  cin >> s;
  if(s[2] == s[3] && s[4] == s[5]) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

B - Golden Coins

現在 $X$ を持っていて両替をすることができる。500円硬貨でhappiness1000、5円硬貨でhappiness5をゲットできる。hapipnessを最大化する。

3:12でAC。

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using ll = long long;
#define chmin(i, j) i = min(i, j);
#define chmax(i, j) i = max(i, j);
#define rep(i, n) for(int i=0;i<n;i++)
int main() {
  long long x;
  cin >> x;
  cout << x / 500 * 1000LL + x % 500 / 5LL * 5 << endl;
  return 0;
}

C - Traveling Salesman around Lake

湖の周りに家が立っている。どこかの家から出発して全ての家を周り切りたい。最短経路を求めよ。

湖の周の長さを $K$ とする。家間の距離で最も長い距離を $d_{max}$ とすると、 $K-d_{max}$ が求める答えである。

7:24でAC。

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using ll = long long;
#define chmin(i, j) i = min(i, j);
#define chmax(i, j) i = max(i, j);
#define rep(i, n) for(int i=0;i<n;i++)
int main() {
  ll k, n;
  cin >> k >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  ll ma = 0;
  for(int i=0;i<n-1;i++) chmax(ma, a[i+1] - a[i]);
  chmax(ma, a[0] + k - a.back());
  cout << k - ma << endl;
  return 0;
}

D - Line++

$1$ から $N$ の頂点が一列に並んでおり、隣通りの頂点は辺で結ばれている。加えて頂点 $X$ と頂点 $Y$ も辺で結ばれている。

この時、 $1 \leq k \leq N-1$ を満たす各 $k$ に対して以下の問に答えよ。

最短距離が $k$ の頂点のペアの数を出力する。

最初どう解くかを考えていて最初にN回ダイクストラを書けば良いと思ったがダイクストラを書けないという絶望に気づいた。絶望しても仕方ないので、他の方法を考える。幅優先探索とかどうだろとか色々考えて、結果もっと簡単にいくのではと考えた。

予想通り簡単な方法が見つかった。頂点 $i$ から頂点 $j$ に最短でいく方法は以下の3通りに限られる。

素直に頂点 $i$ から $j$ に行く方法。
まず頂点 $X$ に行き、頂点 $Y$ に行く。頂点 $Y$ から頂点 $j$ に向かう。
まず頂点 $Y$ に生き、頂点 $X$ に行く。頂点 $X$ から頂点 $j$ に向かう。

この3つのうちの最小値がわかれば良い。

この結果をmapでもvectorでもに格納しておき、最後に順に出力する。

29:36にAC。

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using ll = long long;
#define chmin(i, j) i = min(i, j);
#define chmax(i, j) i = max(i, j);
#define rep(i, n) for(int i=0;i<n;i++)
int main() {
  int n, x, y;
  cin >> n >> x >> y;
  x--;y--;
  vector<vector<int>> dis(n, vector<int>(n, 100100100));
  rep(i, n) {
    for(int j=i+1;j<n;j++) {
      int d = j - i;
      int dd = abs(i - x) + 1 + abs(j - y);
      int ddd = abs(i - y) + 1 + abs(j - x);
      vector<int> dist({d, dd, ddd});
      dis[i][j] = *min_element(dist.begin(), dist.end());
    }
  }
  vector<int> ans(n);
  for(int i=0;i<n;i++) {
    for(int j=0;j<n;j++) {
      if(dis[i][j] == 100100100) continue;
      ans[dis[i][j]]++;
    }
  }
  for(int i=1;i<n;i++) {
    cout << ans[i] << endl;
  }
  return 0;
}

E - Red and Green Apples

赤いリンゴが $A$ 個、緑のリンゴが $B$ 個、そして無色のリンゴが $C$ 個ある。それぞれに美味しさのパラメータ付与されている。無色のリンゴに関しては赤が緑の色を塗ることができる。

赤色のリンゴを $X$ 個、緑のリンゴを $Y$ 個とった時、手に入れた $X+Y$ 個のリンゴの美味しさの合計を最大化したい。最大値を求めよ。

色々やり方あると思うが、僕が取った方法を紹介する。

既に赤色のリンゴのうち選ばれる可能性があるのは美味しさに関して降順に並べて、上から $X$ 個のリンゴまでである。同様に緑のリンゴも上から $Y$ 個を考えれば良い。

無色のリンゴをどのように入れるかというのが問題。結論貪欲にやれば良い。

つまり、赤色のリンゴの中で最も美味しさの小さいものと緑のリンゴの中で最も美味しさの小さいものを比較し、その小さい方と無色のリンゴの中で最も美味しさパラメータの高いリンゴを比較する。もし前者の方が大きければ無色のリンゴをわざわざ使う必要はない。後者の方が大きい時は、無色のリンゴと小さい方をスワップする。

これをスワップの必要がなくなるまでもしくは無色のリンゴがなくなるまで続ける。

最後に残った合計 $X+Y$ のリンゴの美味しさの合計を求めれば良い。

49:40でAC。

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using ll = long long;
#define chmin(i, j) i = min(i, j);
#define chmax(i, j) i = max(i, j);
#define rep(i, n) for(int i=0;i<n;i++)
int main() {
  ll x, y, a, b, c;
  cin >> x >> y >> a >> b >> c;
  vector<ll> p(a);
  vector<ll> q(b);
  vector<ll> r(c);
  rep(i, a) cin >> p[i];
  rep(i, b) cin >> q[i];
  rep(i, c) cin >> r[i];
  sort(p.rbegin(), p.rend());
  sort(q.rbegin(), q.rend());
  sort(r.begin(), r.end());
  vector<int> tp(x);
  vector<int> tq(y);
  rep(i, x) tp[i] = p[i];
  rep(i, y) tq[i] = q[i];
  int pback = x-1;
  int qback = y-1;
  int voi = c-1;
  while(voi != -1 && (pback != -1 || qback != -1)) {
    if(pback == -1) {
      if(tq[qback] >= r[voi]) break;
      else {
        tq[qback] = r[voi];
        voi--;
        qback--;
      }
    }
    else if(qback == -1) {
      if(tp[pback] >= r[voi]) break;
      else {
        tp[pback] = r[voi];
        voi--;
        pback--;
      }
    }
    else {
      ll v = r[voi] - tp[pback];
      ll u = r[voi] - tq[qback];
      if(v <= 0 && u <= 0) break;
      if(v < u) {
        tq[qback] = r[voi];
        qback--;
      }
      else {
        tp[pback] = r[voi];
        pback--;
      }
      voi--;
    }
  }
  ll ans = 0;
  rep(i, x) ans += tp[i];
  rep(i, y) ans += tq[i];
  cout << ans << endl;
  return 0;
}

最後の処理で一個ずつ見ていっているけれど、本当はもっと簡単な方法がある。Editorialを見てもらえれば分かるけれど、 $X+Y$ 個＋無色のリンゴ $C$ 個を一つの配列にまとめてソートして上から $X+Y$ 個が答えになる。無色のリンゴには適当に色を塗る。

このE問題は大体の人が解けてそう。スピードで相当差が出る問題。実際E問題まで解けていて最速の人はパフォーマンス2000を超えていた。そのデータは以下。

atcoder.jp

Ranking：328th / 9745
Performance: 2029

14分でE問題まで解けるのはすごいわ。

F - Distributing Integers

わからんかった。

全体を通して

まあ悪くはなかった。E問題まで解くことはできたし、さらに間違えることがなかったのは良かった。反省点は以下。

超手震えるやばい。慣れるしかない。。
コンパイルするコマンドを何回も打っていて時間の無駄。もっと短縮する方法あるはず。
違うファイルでやっていたからか開くファイルを間違えたりしていた。いっそのこと同じファイルでやるのが良いかもしれない。
HHKBの調子が悪く、Mac内臓のキーボードを使用した。突然キーボードを変えるのはよくない。ずっと内蔵キーボードを使い続けるか、もしくは新しいキーボードを買うのが良いかもしれない。
コンテスト中に新しいアプリの構想が思いついてかなり注意散漫になってた。コンテストに集中。

では。

horoyoisawaのゴミ箱

いろいろ書きます