AtCoder Beginner Contest 073

abc073.contest.atcoder.jp

そろそろBiginnerをBigginerと入力してしまうのやめたいね

([追記]9/10 2:59　Biginnerですらなくて、Beginnerなので修正しました)

A - September 9

問題

2桁の整数 $N$ が与えられるので、 $N$ に $9$ が含まれるか答えてください。

解法

問題文を読むと、お腹が痛いのでトイレに行った方がいいことがわかる。
こういうのは string でやった方が楽だと知っているので(2桁で固定だからね)

コード

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s;
  cin >> s;
  
  if (s[0] == '9' || s[1] == '9') cout << "Yes" << endl;
  else cout << "No" << endl;
}

問題文の下にある提出フォームで書いてコンパイルもせずに出した　通ったのでよかったね(49sec)

B - Theater

問題

100,000個の席がある。 $N$ 人の団体客がやってきて、 $i$ 番目の人々は $l_i$ 番目から $r_i$ 番目までの連続した席に座った。
合計で何人座ったか。

解法

そろそろお腹が痛いことに気がつける。

問題文をよく読むと、同じ席に座ることはないことがわかるので(それはそう　ああそれはそう　それはそう)、それぞれの団体客は何人なのかは $(r_i - l_i) + 1$ みたいな感じで簡単にもとまる。(閉区間の気持ちになりましょう)

コード

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    int l, r;
    cin >> l >> r;
    
    ans += (r - l + 1);
  }
  
  cout << ans << endl;
}

これも自分を信じて提出フォーム直書きをするといいです(よくはないです)

C - Write and Erase

問題

数列が与えられるので、奇数回出現した数がいくつあるかを求めなさい。

解法

進研ゼミでみた！となれるかがポイント
数列に出てくる数字は明らかに巨大なので、これを配列の添え字に使うみたいな解法は明らかに悪手です

方針はいくつかあって、

その辺に落ちている平衡二分探索木に投げる
sortして前から順番に同じ数字がいくつあるか見ていく

みたいなのがあると思います。

ぼくは平衡二分探索木に投げつけました

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
 
  map<int, int> m;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    m[a]++;
  }
 
  int ans = 0;
  for (auto i : m) {
    ans += i.second % 2;
  }
 
  cout << ans << endl;
}

フォームで書いたら17行目に"ans += m.second % 2"とか書いていてコンパイルエラーを出しました(小声)

D - joisino's travel

問題

$M$ 辺 $N$ 頂点の連結なグラフが与えられます。
$r_1, r_2, ..., r_R$ 番目の頂点全てを通る経路で最短のものを求めてください。

解法

ワーシャルさんとフロイドさんとセールスマンが見える気がする。
この方針だと明らかに400じゃないヤバになるけどとりあえず早く終えたい一心で実装した。

始点は全探索して決め打ち、これで $O(R)$
そこからbitDP(巡回セールスマン問題)で $r_1, r_2, ..., r_R$ 全てを通る最短経路を見つけるといいことがわかる。このパートは合計で $O(R^3 \times 2^R)$
あとは $r_1, r_2, ..., r_R$ の各頂点間の最短経路がほしいので、あらかじめWarshall-Floyd法( $O(N^3)$ )か始点を全探索してからのDijkstra( $O(N^3 \times log N)$ *1 )をしておいておわり。全部で $O(R^3 \times 2^R + N^3)$ 。多分。

今回のRの制約は $1 \leq R \leq 8$ と小さいので、†next_permutation†で順番を全探索しても全く問題ない(ことに後になって気がついた。)

コード

最初の方針　Warshall-Floyd法 + bitDP

#include <bits/stdc++.h>
using namespace std;
 
vector<vector<int>> d(202, vector<int>(202, 1001001001));
vector<int> r;
 
int dp[10][1010];
 
int dfs(int v, int bit) {
  int &res = dp[v][bit];
 
  if (~res) return res;
  res = 1001001001;
 
  for (int i = 0; i < r.size(); ++i) {
    if ((bit >> i) & 1) continue;
    res = min(res, dfs(i, bit + (1 << i)) + d[r[v]][r[i]]);
  }
 
  if (res == 1001001001) res = 0;
  return res;
}
 
int solve() {
  int ans = 1001001001;
 
  for (int i = 0; i < r.size(); ++i) {
    memset(dp, -1, sizeof(dp));
    ans = min(ans, dfs(i, (1 << i)));
  }
 
  return ans;
}
 
int main() {
  int n, m, e;
  cin >> n >> m >> e;
 
  for (int i = 0; i < e; ++i) {
    int a;
    cin >> a;
    r.push_back(a - 1);
  }
 
  for (int i = 0; i < m; ++i) {
    int u, v, c;
    cin >> u >> v >> c;
    u--; v--;
    d[u][v] = c;
    d[v][u] = c;
  }
 
  for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
 
  cout << solve() << endl;
}

さすがにこの重さをフォームで書くのは無謀です

Warshall-Floyd法 + next_permuation

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

inline int in() { int x; cin >> x; return x; }

const int inf = 1001001001;

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

  vector<int> r(R);
  for (auto &i : r) i = in() - 1;

  vector<vector<int>> d(n, vector<int>(n, inf));
  for (int i = 0; i < m; ++i) {
    int u = in() - 1, v = in() - 1, c = in();
    d[u][v] = d[v][u] = c;
  }

  for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }

  int ans = inf;
  sort(r.begin(), r.end());
  do {
    int sum = 0;
    for (int i = 1; i < R; ++i) {
      sum += d[r[i - 1]][r[i]];
    }
    ans = min(ans, sum);
  } while (next_permutation(r.begin(), r.end()));

  cout << ans << endl;
}