読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

ABC041を解いてみた

ABC 競技プログラミング

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;
}