きままにものづくり

日々の気付いたことなんかを書いてます。

ARC#006の問題を解いてみた

こんばんは、even_ekoです。
今日の午前中は、昨日から続いた風邪でダウンしてました。
午前中によく寝て、昼食をとったら元気になったの久しぶりにAtCoderをやってみました。

AtCoder Regular Contest #006 B問題

下は、ARC#006のB問題の解答です。
懐かしのC++です。OpenGLで少し出てくるのですが、あまり使わないので懐かしく感じました。

#include <iostream>
int main(int argc, const char * argv[])
{
    int column,row;
    std::cin >> column;
    std::cin >> row;
    column = 2*column;
    row = row + 1;  
    char matrix[row][column];
    //to ignore EOF 
    std::cin.get();
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < column; j++) {
            matrix[i][j] = std::cin.get();
        }
    }
    //to ignore EOF
    column = column - 1;
    //to ignore leader postion
    row = row -1;
    int leaderPos;
    //find position of 'o'
    for (int i = 0; i < column; i++) {
        if(matrix[row][i] == 'o')
            leaderPos = i;
    }
    //search horizontal lines
    for (int i = 0; i < row; i++) {
        if (leaderPos) {
            if (matrix[(row - 1) - i][leaderPos - 1] == '-') { 
                leaderPos -=2;
            } else if (matrix[(row - 1) - i][leaderPos + 1] == '-') {
                leaderPos +=2;
            }
        } else {
            if (matrix[(row - 1) - i][leaderPos + 1] == '-') 
                leaderPos +=2;
        }
    }
    //optimize value
    leaderPos = (leaderPos/2) + 1;
    std::cout << leaderPos << '\n';
    return 0;
}

解答の概要としては、あみだくじの正解位置から上にたどっていって目的地の値を出してます。
注意点としては、std::cout.get()が改行も拾ってしまうところですかね。なので、どの変数にも戻り値を代入していないstd::cout.get()がいくつかの場所にあります。英語のコメントは完全に勢いでつけているので、文法とかは滅茶苦茶です。

AtCoder Regular Contest #006 問題C

今度は、ARC#006のC問題の解答です。
個人的には、C問題の方が解きやすく感じました。

#include <iostream>

int main(int argc, const char * argv[])
{
    int num_of_box;
    int count = 0;
    int weight_of_box;
    int stack[50];
    
    std::cin >> num_of_box;
    
    for (int i = 0; i < num_of_box; i++)
    {
        std::cin >> weight_of_box;
        if (!count) {
            stack[count] = weight_of_box;
            count++;
        }
        else 
        {
            if (weight_of_box > stack[count - 1]) 
            {
                stack[count] = weight_of_box;
                count++;
            }
            else
            {
                for (int j = 0; j < count ; j++) 
                {
                    if (weight_of_box <= stack[j]) 
                    {
                        stack[j] = weight_of_box;
                        break;
                    } 
                }
            }
        }
    }
    
    std::cout << count << '\n';
    return 0;
}

この問題の入力例1は少し不思議なことをしています。1は一番軽いので、一番上にくるようにした方が良いのになぜか一番下に配置しています。
何か例外があるのかと考えたのですが、思いつきませんでした。しかし、ある規則を発見しました。
それは、入力例1以外を参考にアルゴリズムを考えると、左側が一番小さくなるように勝手にソートされるということです。おそらく、この規則を明確にしないために、入力例1はよく分からないことをしているのでないでしょうか。


D問題もやろうと思ったのですが、時間があまりなかったのでやめました。今度、時間がある時にでもやろうかと思います。

余談

名前空間上の問題から、using namespaceは使用していません。しかし、競技用プログラミングにおいてはそんなに名前空間は問題にならないと思うので、using namespaceは使用した方がいいかもしれないです。

広告を非表示にする