# Gori#021(ABC041)

問題セット

# B - 直方体

# 概要

A,B,CA,B,Cが与えられた時, A×B×CA \times B \times C109+710^9 + 7で割ったあまりを求めよ.

# 解法

問題文に答えが書いてある.

#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1e9 + 7;

int main() {
  int64_t a,b,c, ans = 0;
  cin >> a >> b >> c;
  (ans = (a * b % MOD) * c) %= MOD;
  cout << ans << endl;
  return 0;
}

# C - 背の順

# 概要

身長がaia_iの生徒がNN人いる.
生徒達を背の順に並べたときの出席番号を出力せよ.

# 解法

std::pair(身長, 出席番号)を持ち, 身長順をキーとして降順にソートしてから出力すればよい.

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

int main() {
  int n;cin >> n;
  vector< pair<int,int> > a(n);  
  for(int i=0;i<n;++i) {cin >> a[i].first; a[i].second = i+1;}
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  for(int i=0;i<n;++i) cout << a[i].second << endl;
  return 0;
}

# D - 徒競走

# 概要

NN匹のうさぎが徒競走をした.
観客からは, xix_i番目のうさぎはyiy_i番目のうさぎよりも先にゴールしたという情報がMM人分与えられる.
ここで, 全ての観客の情報に合致する着順は何通りあるか求めよ.

# 解法

  • 制約からbitDPであることに気づく
  • まず, DPテーブルの持ち方を考える(以下のようになる)
dp[i][j] := i番目のうさぎまで見たときに,
            状態がj(0:unreached, 1:reached)だったときの通り数
  • その後, 遷移を考える

  • ii番目のうさぎが遷移できるのは,

    • i=xii=x_iのとき, 状態jjyiyiビット目が立っていないとき
    • (yiy_i番目のうさぎは到達していてはならない)
    • i=yii=y_iのとき ,状態jjxix_iビット目が立っているとき
    • (xix_i番目のうさぎは到達していなければならない)
  • DPテーブルの持ち方と遷移がわかったので解ける

  • ちなみに計算量はO(n×2n×n×m)=O(n2×2n×m)O(n \times 2^n \times n \times m) = O(n^2 \times 2^n \times m)

#include <bits/stdc++.h>
using namespace std;
using int64 = int64_t;
#define int int64

int dp[20][(1<<20)];
vector< int > e[20];

signed main() {
  int n,m; cin >> n >> m;
  for(int mi=0;mi<m;++mi){
    int x,y;
    cin >> x >> y;
    --x; --y;
    e[x].push_back(y);
  }

  dp[0][0] = 1;
  for(int ni=0;ni<n;++ni){
    for(int state=0;state<(1<<n);++state){
      // i番目のうさぎへの遷移が可能かを確認
      for(int i=0;i<n;++i){
        if(state & (1<<i)) continue;

        bool can_move = true;
        for (auto &&ti: e[i]) {
          can_move &= !(state & (1<<ti));
        }

        if (!can_move) continue;
        dp[ni+1][state | (1<<i)] += dp[ni][state];
      }
    }
  }

  int ans = dp[n][(1<<n)-1];
  cout << ans << endl;
  return 0;
}

以上.
お疲れ様でした.

# 参考資料

Last Updated: 2019-2-15 04:38:05