AtCoderログ：ABC265

ABC265に参加しました

今回はA, B, Cの3完でした。
A: 3分
B: 8分
C: 19分

今回のコンテストでのレート変動

189→243（パフォーマンス：739）

A問題-Apple

単純に解くとREになる罠でした。
あくまで最小値を取る必要がありました。

// 提出コード
int main() {
  int x, y, n;
  cin >> x >> y >> n;
  int res = x * n;
  int Y = n / 3;
  int X = n % 3;
  res = min(res, y * Y + x * X);
  cout << res << endl;
  return 0;
}

B問題-Explore

ボーナス部屋をmapで持っておくことでO（1）で持ち時間の増加を行えます。
あとは問題文の通りにシミュレーションしていくのみです。

// 提出コード
int main() {
  long long n, m, t, x, y;
  cin >> n >> m >> t;
  vector<long long> a(n + 1);
  map<long long, long long> mp;
  rep3(i, 1, n) cin >> a[i];
  rep(i, m) {
    cin >> x >> y;
    mp[x] = y;
  }
  rep3(i, 1, n) {
    if (mp.count(i)) t += mp[i];
    t -= a[i];
    if (t <= 0) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}

C問題-Belt Conveyor

B問題と同様にシミュレーションの問題でした。特定のアルゴリズムを使用する必要は多分なかったと思います。
自分の場合は各マスの文字と通ったことがあるかどうかをpairで所持しました。

// コンテスト後にリファクタしたコード
int main() {
  int h, w;
  cin >> h >> w;
  vector<vector<pair<char, bool>>> v(h, vector<pair<char, bool>>(w));
  char g;
  rep(i, h) {
    rep(j, w) {
      cin >> g;
      v[i][j] = make_pair(g, false);
    }
  }
  bool flag = true;
  int i = 0, j = 0;
  while (flag) {
    if (v[i][j].first == 'U' && i != 0) i = i - 1;
    else if (v[i][j].first == 'D' && i != h - 1) i = i + 1;
    else if (v[i][j].first == 'L' && j != 0) j = j - 1;
    else if (v[i][j].first == 'R' && j != w - 1) j = j + 1;
    else break;
    if (v[i][j].second) {
      cout << -1 << endl;
      return 0;
    } else v[i][j].second = true;
  }
  cout << i + 1 << " " << j + 1 << endl;
  return 0;
}

// 提出したコード
int main() {
  int h, w;
  cin >> h >> w;
  vector<vector<pair<char, bool>>> v(h, vector<pair<char, bool>>(w));
  char g;
  rep(i, h) {
    rep(j, w) {
      cin >> g;
      v[i][j] = make_pair(g, false);
    }
  }
  bool flag = true;
  int i = 0, j = 0;
  while (flag) {
    if (v[i][j].first == 'U' && i != 0) {
      i = i - 1;
      if (v[i][j].second) {
        cout << -1 << endl;
        return 0;
      }
      v[i][j].second = true;
    } else if (v[i][j].first == 'D' && i != h - 1) {
      i = i + 1;
      if (v[i][j].second) {
        cout << -1 << endl;
        return 0;
      }
      v[i][j].second = true;
    } else if (v[i][j].first == 'L' && j != 0) {
      j = j - 1;
      if (v[i][j].second) {
        cout << -1 << endl;
        return 0;
      }
      v[i][j].second = true;
    } else if (v[i][j].first == 'R' && j != w - 1) {
      j = j + 1;
      if (v[i][j].second) {
        cout << -1 << endl;
        return 0;
      }
      v[i][j].second = true;
    } else flag = false;
  }
  cout << i + 1 << " " << j + 1 << endl;
  return 0;
}

D問題-Iroha and Haiku (New ABC Edition)

累積和を用いるであろうことは分かりましたが、二分探索で解ける事には気付きませんでした。
ここら辺を解けるようになっていきたいですね...

感想

茶diffをしっかり解けるようにしていきたいと改めて感じました。ABC-B埋めと並行してC問題も少しずつ進めていこうと思います。