# Gori#021(ABC041)
# B - 直方体
# 概要
が与えられた時, をで割ったあまりを求めよ.
# 解法
問題文に答えが書いてある.
#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 - 背の順
# 概要
身長がの生徒が人いる.
生徒達を背の順に並べたときの出席番号を出力せよ.
# 解法
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 - 徒競走
# 概要
匹のうさぎが徒競走をした.
観客からは, 番目のうさぎは番目のうさぎよりも先にゴールしたという情報が人分与えられる.
ここで, 全ての観客の情報に合致する着順は何通りあるか求めよ.
# 解法
- 制約からbitDPであることに気づく
- まず, DPテーブルの持ち方を考える(以下のようになる)
dp[i][j] := i番目のうさぎまで見たときに,
状態がj(0:unreached, 1:reached)だったときの通り数
その後, 遷移を考える
番目のうさぎが遷移できるのは,
- のとき, 状態のビット目が立っていないとき
- (番目のうさぎは到達していてはならない)
- のとき ,状態のビット目が立っているとき
- (番目のうさぎは到達していなければならない)
DPテーブルの持ち方と遷移がわかったので解ける
ちなみに計算量は
#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;
}
以上.
お疲れ様でした.