19日目 Beginner 36

19日目(2019/9/4)

AtCoder Beginner Contest 036

解けた問題

A:お茶

Aという単位で買うなら (A+B-1)/Aを出力すれば求める答えが出ます

B:回転

vector<string> s(N)として定義して、文字列を受け取る。最近ちょっとvectorの扱いにもなれてきたかな？ 内部でデータを保持してないといけないわけでもないので、string型をchar型の配列としてみて、回転したあとの順番で出力しました。

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

using namespace std;

int main(void){
    int N;
    cin >> N;
    vector<string> s(N);
    for(int i=0;i<N;i++)
        cin >> s[i];
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cout<<s[N-j-1][i];
        }
        cout << endl;
    }
}

C:座圧

とりあえず、問題を理解するのにちょっと時間がかかりましたｗ
つまるところ、この問題の内容を読み解いていくと、

• aの要素を小さい順に出力しよう。
• ただし、同じ値のときはそれは同じ値として表示しよう。

ということなので、もとのindexを保持しつつ、データをソートして、ソートしたときに小さい順に重複したものは同じ値として値を保持して、元の順番で出力しよう。ってことですね。
Dataクラスを宣言して、メンバ変数として、index,data,順番を保持する変数をもたせました。sort関数で使うために、operator<をオーバーロード。dataでソートできるよにしました。
実装はこんな感じ！（もっとスマートな書き方はありそうですね）

```cpp // C++のテンプレート

include

include

include

include

using namespace std;

class Data{ public: int index; int data; int s; bool operator< (const Data &another) const{ return data < another.data; } Data(int i,int d,int sort){ index = i; data = d; s=sort; } };

int main(void){ int N; cin >> N; vector a; vector b; int temp; for(int i=0;i<N;i++){ cin >> temp; a.push_back(Data(i, temp,0)); } sort(a.begin(),a.end());

a[0].s = 0;
for(int i=1;i<N;i++){
    if(a[i-1].data==a[i].data)
        a[i].s = a[i-1].s;
    else
        a[i].s = a[i-1].s+1;
}
for (int i = 0; i < N; i++)
{
    //cout << a[i].index << ":" << a[i].data << ":" << a[i].s <<endl;
    b.push_back(Data(a[i].data,a[i].index,a[i].s));
}
sort(b.begin(),b.end());
for(int i=0;i<N;i++){
    cout << b[i].s << endl;
}

} ```

解けなかった問題

D:塗り絵

んー、これが頂点染色問題って呼ばれるやつなのかな？アルゴリズムを何も覚えてなくて、どう実装したら良いんだろうってなりました。入力例を見る限り組合せ爆発のように通りが増えていきそうなので、一つ一つ数えるのは絶望的だろうと思い、数学的に計算する方法を考えたけどよくわからず…。

解説を見てみる

C

連想配列 mapを使うといいらしい。勉強しておいたほうが良いかも！

D

問題として与えられているものは、木構造である。N-1なので確かに。この問題はtree DP（木構造の動的計画法?）の簡単な場合らしい。