ABC041を解いてみた

A問題

　入力をString型で受けとりS[i-1]を出力しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007

int main(void)
{
  string S;
　int i;
　cin >> S;
　cin >> i;
　cout << S[i-1] << endl;
　return 0;
}

B問題

　直方体の体積の計算自体はA*B*Cで求められる。変数はlong long型で確保しておきオーバーフローしないように掛けるたびに余剰の計算を行いました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007

int main(void)
{
  ll a, b, c, ans;
  scanf("%lld %lld %lld", &a, &b, &c);

  ans = (((a*b)%MOD)*c)%MOD;
  printf("%lld\n", ans);

  return 0;
}

C問題

　vector< pair< int, int > > (身長と出席番号のペア）を作成し身長をもとにソートを実行、そしてその順番で出席番号を出力しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007

int main(void)
{
  int n = 0, a = 0;

  scanf("%d", &n);
  vector< pair<int, int> > height(n);

  for(int i = 0; i < n; i++)
  {
    scanf("%d", &a);
    height[i] = make_pair(a, i);
  }

  sort(height.begin(), height.end(), greater<pair<int,int> >());

  for(int i = 0; i < n; i++)
    printf("%d\n", height[i].second+1);

  return 0;
}

D問題

　満点解法のトポロジカルソートを用いる方法の計算が理解できなかったのでとりあえず全探索の部分点解法について。next_permutationを使って全パターンについて探索し、各パターンについてxがyより先に出ればそのパターンは条件を満たしていると考えられます。満点解法については理解できたら書きます…

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007

int main(void)
{
  int n = 0, m = 0, x[120], y[120], lis[16][16];
  scanf("%d %d", &n, &m);
  for(int i = 0; i < m; i++)
  {
    scanf("%d %d", &x[i], &y[i]);
  }

  vector<int> data;
  for(int i = 1; i <= n; i++) {data.push_back(i);}

  ll ans = 0;
  bool flag = true;
  do
  {
    for(int i = 0; i < m; ++i)
    {
      for(int j = 0; j < n; ++j)
      {
        //xのあとにyが出ればtrueに　yのあとにxが出ればfalseになる
        if(data[j] == x[i]) flag = false;
        else if(data[j] == y[i]) flag = true;
      }
      if(!flag) break;
    }
    if(flag) ans++;
  }while(next_permutation(data.begin(), data.end()));

  printf("%d\n", ans);

  return 0;
}