AtCoder Beginner Contest 061

abc061.contest.atcoder.jp

迷路くんとvirtual contestでDをやったのでついでに書きます(part2)

A - Between Two Integers

問題

abc061.contest.atcoder.jp

解法

問題文にある通り、 かどうかを判定すればいいです。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;

  cout << (a <= c && c <= b ? "Yes" : "No") << endl;
}

B - Counting Roads

問題

abc061.contest.atcoder.jp

解法

都市 と 都市 にはそれぞれ 番目の道路が伸びているので、素直にそれをカウントすればいいです。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;

  vector<int> cnt(n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    cnt[a - 1]++;
    cnt[b - 1]++;
  }

  for (int i = 0; i < n; ++i) {
    cout << cnt[i] << endl;
  }
}

C - Big Array

問題

abc061.contest.atcoder.jp

解法

問題文の通りに配列を確保していたらパソコンが爆発してしまうので、値と個数だけで管理することを考えます。

pairの第一引数に値、第二引数に個数を持って昇順にソート、あとは第二引数を辿っていきながら 個に到達した時の第一引数を出力すればいいです。

コード

#include <bits/stdc++.h>
using namespace std;

using lint = long long;

int main() {
  lint n, k;
  cin >> n >> k;

  vector<pair<lint, lint>> v;
  for (int i = 0; i < n; ++i) {
    lint a, b;
    cin >> a >> b;

    v.push_back(make_pair(a, b));
  }

  sort(v.begin(), v.end());

  lint idx = 1;
  lint ans = 0;
  for (int i = 0; i < n; ++i) {
    if (idx <= k && k < idx + v[i].second) ans = v[i].first;
    idx += v[i].second;
  }

  cout << ans << endl;
}

D - Score Attack

問題

abc061.contest.atcoder.jp

解法

コストの正負を反転させると最短経路問題に帰着できる。

負の閉路(=スコアが inf になる)の検出、最短経路、負のコストなどを考えると Bellman-Ford 法で処理したい気持ちになる。

Nにたどり着けない負の閉路はスコアに関わらないので、

N回目のループで最短経路の更新があったら負の閉路が存在

↓

N回目のループで頂点Nへの最短経路の更新があったら負の閉路が存在　

とすると解ける。*1

これはN回目のループでNだけ見れば済むのでそんなに書き換えなくても良いので楽。

コード

#include <bits/stdc++.h>
using namespace std;

using lint = long long;

struct edge {
  int to, cost;
  edge() {}
  edge(int a, int b) :to(a), cost(b) {}
};

const lint inf = 1001001001001001001;
vector<vector<edge>> G;
vector<lint> d;

bool bellman_ford(int n, int s = 0) {
  d = vector<lint>(n, inf);
  d[s] = 0;

  for (int i = 0; i < n; ++i) {
    for (int v = 0; v < n; ++v) {
      for (int j = 0; j < G[v].size(); ++j) {
        edge e = G[v][j];
        if (d[e.to] > d[v] + e.cost) {
          d[e.to] = d[v] + e.cost;
          if (i == n - 1 && e.to == n - 1) return true;
        }
      }
    }
  }

  return false;
}

int main() {
  int n, m;
  cin >> n >> m;

  G.resize(n);

  for (int i = 0; i < m; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    a--; b--;

    G[a].push_back(edge(b, -c));
  }

  if (bellman_ford(n)) puts("inf");
  else cout << -d.back() << endl;
}

*1:これに気がつかず結構苦労しました