AtCoder Beginner Contest 041

問題

abc041.contest.atcoder.jp

解法

まあ配列かstd::string知っていたら解けます

コード

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

int main() {
  string s;
  int n;

  cin >> s >> n;
  cout << s[n - 1] << endl;
}

問題

abc041.contest.atcoder.jp

解法

の最大値は なので、 の最大値は になるのでそのままやると long long int でもオーバーフローする。

を とすればオーバーフローしないで済むので、計算順序を入れ替えるだけ。

コード

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

const int mod = 1e9 + 7;
using lint = long long;

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

  cout << a * b % mod * c % mod << endl;
}

問題

abc041.contest.atcoder.jp

解法

pairの第一引数に身長、第二引数に出席番号を持っておいて降順にソートするだけ

興味があるのは出席番号だけなので、sort(v.begin(), v.end(), greater()); みたいなことはせずに身長の政府を反転させた方が楽

コード

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

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

  vector<pair<int, int>> v(n);
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    v.push_back(make_pair(-a, i + 1));
  }

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

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

問題

abc041.contest.atcoder.jp

解法

問題文を読み替えると、N頂点をDAGにするパターンはいくつあるか、という問題になる。

愚直な解法を考えると、 通りを列挙してDAGになるかどうか判定するといった方法が考えられるが、 になってしまうので部分点しか得られない。

この問題をbitDPに落とし込めないかと考えてみる。

これまで使ってきたノードの番号をbitで管理しているとすると*1、新たに追加できるノードは

• 現在の状態に到るまでに使われていない(=bit が立っていない)
• 現在の状態に到るまでに使われたノードに辺を張っていない(辺が存在する場合新たなグラフはDAGにならないので(左から右に流したいのに左に流れてしまうみたいなイメージ))

を満たしていればいいことがわかるので、bitDPで殴れる。 なので満点が得られる。

コード

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

using lint = long long;

bool g[16][16];
int n, m;

lint d[1 << 16];
lint dp(int bit = 0) {
  if (bit + 1 == (1 << n)) return 1;

  lint &res = d[bit];
  if (~res) return res;
  res = 0;

  for (int i = 0; i < n; ++i) {
    if (bit & (1 << i)) continue;
    int v = i;
    bool f = true;
    for (int j = 0; j < n; ++j) {
      if (bit & (1 << j) && g[v][j]) f = false;
    }

    if (f) res += dp(bit + (1 << i));
  }

  return res;
}

int main() {
  memset(d, -1, sizeof(d));
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    g[a][b] = true;
  }

  cout << dp() << endl;
}