AtCoder Beginner Contest 039

[TakefumiYamamura]

http://abc039.contest.atcoder.jp/

[TakefumiYamamura]

C - ピアニスト高橋君

時間制限 : 2sec / メモリ制限 : 256MB

問題文

高橋君は青木君に突然魔法で小さくされ、ピアノの上に乗せられてしまいました。

高橋君は、今ピアノのある鍵盤の上に立っていますが、どの鍵盤の上にいるのかを知りたいです。

高橋君は、自分の今いる鍵盤から右 20 個の鍵盤の色を調べました。高橋君のいる鍵盤の音階を調べてください。

調べた鍵盤の色は、W、B からなる文字列 S として与えられ、W は白色、B は黒色を表します。そして、高橋くんのいる鍵盤の色は文字列の先頭に対応します。

なお、ピアノの鍵盤は下図のように、色は"白黒白黒白白黒白黒白黒白"、音階は "ド ド# レ レ# ミ ファ ファ# ソ ソ# ラ ラ# シ" を繰り返しています。

Note

ただやるだけ

#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
using namespace std;

int main(){
    string s;
    cin >> s;
    string onkai = "WBWBWWBWBWBW";
    string ans[12] = {"Do", "Do", "Re", "Re", "Mi", "Fa", "Fa", "So", "So", "La", "La", "Si"};
    vector<string> v;
    for (int i = 0; i < 12; ++i)
    {
        string tmp = "";
        for (int j = 0; j < 20; ++j)
        {
            tmp.push_back(onkai[(i+j)%12]);
        }
        v.push_back(tmp);
    }

    for (int i = 0; i < 12; ++i)
    {
        if(s == v[i]){
            cout << ans[i] << endl;
        }
    }
    return 0;
}

[TakefumiYamamura]

D - 画像処理高橋君

時間制限 : 2sec / メモリ制限 : 256MB

問題文

2 値画像に対して行う、収縮という処理があります。なお、2 値画像とは、画素の色が白か黒かの 2 種類しかない画像の事です。

収縮とは、それぞれの画素についてその画素と周り 8 方向の画素のうち、一つでも黒い画素があったらその画素を黒くするという処理です。

ここで、画素数が高さ H、幅 W の 2 値画像を考えます。この画像はある画像に一回収縮を行ったものであることがわかっています。元の画像として考えられるものがあるかを判定し、もしあるならばそのうちどれか 1 つを復元してください。

画像は、H 個の、W 文字の文字列 Si で与えられます。Si の j 文字目は、上から i 個目、左から j 個目の画素の色を表しており、. なら白、# なら黒です。

制約

1≦H,W≦100 Si は W 文字の .、# からなる文字列である

note

貪欲にやるだけno2

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>
#include <string>

using namespace std;

class MrTakahashiProcessingImages
{
public:
    int h, w;
    vector<vector<int > > image;
    vector<vector<int > > visited;
    vector<vector<char > > ans;
    MrTakahashiProcessingImages();
    ~MrTakahashiProcessingImages();
    void exec();

};

MrTakahashiProcessingImages::MrTakahashiProcessingImages(){
    cin >> h >> w;
    image.resize(h);
    visited.resize(h);
    ans.resize(h);
    for (int i = 0; i < h; ++i)
    {
        image[i].resize(w);
        visited[i].resize(w);
        ans[i].resize(w);
        string tmp;
        cin >> tmp;
        for (int j = 0; j < w; ++j)
        {
            if(tmp[j] == '#'){
                image[i][j] = 1;
                visited[i][j] = 0;
            }else{
                image[i][j] = 0;
                visited[i][j] = 1;
            }
            ans[i][j] = '.';
        }
    }
}

MrTakahashiProcessingImages::~MrTakahashiProcessingImages(){}

void MrTakahashiProcessingImages::exec(){
    for (int i = 0; i < h; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            if(image[i][j]){
                bool flag = false;
                for (int k = -1 + i; k <= 1 + i; ++k)
                {
                    for (int l = -1 + j ; l <= 1 + j; ++l)
                    {
                        if(k < h && l < w && 0 <= k  && 0 <= l && !image[k][l]){
                            flag = true;
                            goto BREAK_LABEL;
                        }
                    }
                }
                BREAK_LABEL:
                if(flag) continue;
                for (int k = -1 + i; k <= 1 + i; ++k)
                {
                    for (int l = -1 + j ; l <= 1 + j; ++l)
                    {
                        if(k < h && l < w && 0 <= k  && 0 <= l){
                            visited[k][l] = 1;
                        }
                    }
                }
                ans[i][j] = '#';
            }
        }
    }

    for (int i = 0; i < h; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            if(!visited[i][j]){
                cout << "impossible" << endl;
                return ;
            }
        }
    }

    cout << "possible" << endl;
    for (int i = 0; i < h; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            cout << ans[i][j];
        }
        cout << endl;
    }

}

int main(){
    MrTakahashiProcessingImages mtpi = MrTakahashiProcessingImages();
    mtpi.exec();
}