雑記

競技プログラミングについての話題(?)

AtCoder Beginner Contest 073

abc073.contest.atcoder.jp

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

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


A - September 9

問題

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

解法

問題文を読むと、お腹が痛いのでトイレに行った方がいいことがわかる。
こういうのは 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

問題


MN頂点の連結なグラフが与えられます。
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;
}

*1:?