[アルゴリズムプール解析]プログラマの柱と梁の取り付け(2020 Kakao Blind Recruition)

今日の問題はプログラマブル柱とビームのインストール題です.2020年KACA公募第1回試験問題この試験は5回目ですか?そうらしい.正解率は低いのですが、回答を見るとやはり経験が多いと答えにくい質問なのか、という思いがわいてきました…!
あと5日、怖かった、、、!ううう

プログラマブル柱とビームのインストール

氷河が砕けるにつれて、雪城に漂ってきた「ジョルディ」は人生の第2幕のため、住宅建築事業に身を投じることを決意した.「ジョルディ」は柱と梁を利用して壁面構造を自動的に構築するロボットを開発する計画で、これまでロボットの動作をシミュレートするプログラムを作成していた.
このプログラムでは、2 D仮想壁面に柱と梁を使用して、柱とビューの長さが1のセグメントとして表されるフレーム構造をインストールできます.次のルールがあります.

柱は、底部、梁の一端、または他の柱に配置する必要があります.

梁の一端は柱に位置するか、両端は他の梁と同時に接続しなければならない.
しかし、床とは壁の底の床のこと.

2 D壁面がn x nサイズの正射メッシュで、各メッシュサイズが1 x 1です.最初の壁面は空です.柱と梁は、グリッド線の交点ではなく、グリッドの各エッジに取り付けることができます.次に、柱と梁を取り付けてフレームを作成する例を示します.

たとえば、上図は次の手順で構造を作成します.

(1,0)から柱を上に取り付け、(1,1)から右にビームを作成します.

(2,1)から柱を上に取り付け、(2,2)から右にビームを作成します.

(5,0)から1本の柱を上に取り付け、(5,1)からもう1本の柱を上に取り付けます.

(4,2)からビームを右に取り付け、次に(3,2)からビームを右に取り付けます.

(4,2)右側のビームを最初に取り付けず,(3,2)右側のビームを取り付けてみると,2番ルールに合わないため取り付けられない.柱と梁を削除する機能もあり、柱と梁を削除した後、残りの柱と梁も上記のルールを満たすべきです.実行した操作が条件を満たしていない場合は、その操作は無視されます.
2 D配列build frameにパラメータが付与されている場合、壁面サイズn、柱、梁をインストールまたは削除する操作を含み、すべてのコマンドを実行した後に構造の状態に戻ります.

にゅうしゅつりょく

nは5以上100以下の自然数です.

build frameの垂直(行)長は1000より大きい.

build frameの水平(列)長は4です.

build frameの要素は[x,y,a,b]である.

x、yは柱、梁の交点を取り付けたり削除したりする座標で、「水平座標、垂直座標」形式です.

aは、取り付けまたは削除する構造のタイプを示し、0は柱、1は梁を表す.

bはインストールまたは削除する構造を示し、0は削除を示し、1はインストールを示す.

壁面の外に柱、梁を取り付けない.

の下部にビームが取り付けられていません.

では、交点座標に基づいた右側の構造と上部の柱がインストールまたは削除されます.

重複するように

構造がインストールされている場合は、存在しない構造の削除を入力できません.

最終構築物の状態は以下の規則に従って返してください.

を返す配列には、各構造の座標が含まれ、3つの水平(列)の長さを持つ2次元配列が必要です.

の配列を返す要素は[x,y,a]形式です.

x,yは柱・梁の交点座標,[横座標,縦座標]形式である.

柱は、ビューの交差点座標の右側または上に取り付けられていることを示します.

aは構造のタイプを表し、0は柱を表し、1は梁を表す.

を返す配列はx座標昇順で並べられ、x座標が同じ場合はy座標昇順で並べられます.

xとy座標が同じであれば、柱は梁の前にあります.

nbuild_frameresult5[[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]][[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]]5[[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]][[0,0,0],[0,1,1],[1,1,1],[2,1,1],[3,1,1],[4,0,0]]

私の答え

結論から言えば、完全に私の解答で解決したわけではない.
私が初めて試した方法は、3次元配列wallを宣言し、[x,y]に柱、wall[x][y][0] = trueを取り付け、梁を取り付けた場合wall[x][y][1] = true、削除する場合は部材が削除できるかどうかを判断し、できればwall[x][y][0] / wall[x][y][1] = falseに処理します.
ただし,その中の構造が削除できるか否かを処理する部分は,すべての場合の数を上書きすることはできず,もちろん通過できない.
公式解説でも条件通りに実現すれば良いというだけなので、有効な実現方法を見つけ、非常に簡単な解決方法を見つけました位置!
方法はずっと簡単だ.削除は削除、インストールはインストール、削除/インストール後、現在残っているすべての構造が正常であることを確認します.確認の条件は問題と同じです.

기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
단, 바닥은 벽면의 맨 아래 지면을 말합니다.

しかし、もちろん疑問が生じる.時間的にカバーできますか?構造物を探すために、毎回n個の構造物を巡回しなければならないのではないでしょうか.
この点を解決するために、こちらは<set>の資料構造を使用しています.線形探索を回避し,探索時間を節約し,困難な状況を考慮することなく簡単に実施できる.
アルゴリズム自体は簡単ですが、なぜ思いもよらなかったのでしょうか.
やっぱり経験ですね…!経験!!

コード#コード#

#include <vector>
#include <set>

using namespace std;

set<vector<int>> buildings;

bool isSafe(){

    for (auto frag : buildings) {
        if (frag[2]==0){  // 기둥 설치 조건
            if (frag[1]==0) continue;  // 바닥에
            //보의 한쪽 위
            if (buildings.find({frag[0], frag[1], 1}) != buildings.end() || buildings.find({frag[0]-1, frag[1], 1}) != buildings.end()) continue;
            // 다른 기둥 위
            if (buildings.find({frag[0], frag[1]-1, 0}) != buildings.end()) continue;
            return false;
        }else{ // 보 설치 조건
            // 한쪽 끝이 기둥 위 
            if (buildings.find({frag[0], frag[1]-1, 0}) != buildings.end() || buildings.find({frag[0]+1, frag[1]-1, 0}) != buildings.end()) continue;
            // 다른 양쪽 끝이 다른 보와 연결 
            if (buildings.find({frag[0]-1, frag[1], 1}) != buildings.end() && buildings.find({frag[0]+1, frag[1], 1}) != buildings.end()) continue;
            return false;
        }
    }
    return true;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;

    for(int i=0; i<build_frame.size(); i++){
        vector<int> fragment = {build_frame[i][0],build_frame[i][1], build_frame[i][2]};

        if (build_frame[i][3] == 1){
            buildings.insert(fragment);
            if (!isSafe()){
                buildings.erase(fragment);
            }
        }else{
            buildings.erase(fragment);
            if (!isSafe()){
                buildings.insert(fragment);
            }
        }
    }

    for (auto frag : buildings){
        answer.push_back(frag);
    }

    return answer;
}