25日目：Beginner 41

25日目(2019/9/10)

AtCoder Beginner Contest 041

解けた問題

A:添字

string型でi-1を出力すればおｋ

B:直方体

数がめちゃくちゃ大きくなってしまうので、A*Bをした時と、(A*B)*Cに値を10^9+7でmodをとって出力しました。

C:背の順

Studentクラスを作成して、出席番号と身長を記録するようにして、operator<をオーバーロードして、身長でソートしました！ だめかな？って思ったら普通にAC通った！

// C++のテンプレート
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

class Student{
    public:
    int num;
    int height;

    bool operator<(const Student &another) const
    {
        return height < another.height;
    }
};
int main(void){
    int N;
    cin >> N;
    vector<Student> a(N);
    for(int i=0;i<N;i++){
        a[i].num = i;
        cin >> a[i].height;
    }
    sort(a.begin(),a.end());
    for(int i=N-1;i>=0;i--){
        cout << a[i].num+1 << endl;
    }
}

解けなかった問題

D:徒競走

なぜか実際の並び順を考えてしまったけれど、その通り数を考えるんだからダメじゃん…、どうやって数えればよかったんだろう？

解説を見てみる

D

どうやら、トポロジカルソートをする問題らしい、聞いたことあるようなないような…。 問題を有向グラフ問題と考えて、横一列に並べたときに全て同じ向きを向くようなソートの仕方を指すらしく、N<=8のときは、最大ステップ数的にも全探索して良いみたい。これで部分点は取れるみたいですね。