AHC052参加記～AIへの文句を添えて～

参加したよ

今回AHC052に参加して自分の中では調子がよかったので書いていきます。
今回のスコアは193822、順位は599位でした。
Qiitaに動画を埋め込む方法が分からなかったのでビジュアライザはないです

第一章　雑巾がけ

https://atcoder.jp/contests/ahc052
とりあえず入力を受け付けて出力をするコードを作りました

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define oke cout << "Yes" << '\n';
#define dame cout << "No" << '\n';
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using HaiI = vector<vector<int>>;
using Hai2 = vector<vector<ll>>;
using HaiB = vector<vector<bool>>;
using Hai3 = vector<vector<vector<ll>>>;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(15);
	int N,M,K;
	cin >> N >> M >> K;
	vector<pair<int,int>>R(M);
	rep(i,M){
		int a,b;
		cin >> a >> b;
		R[i]={a,b};
	}
	vector<string>V(N);//右と左に行くとき
	rep(i,N){
		cin >> V[i];
	}
	vector<string>H(N-1);//上と下にいくとき
	rep(i,N-1){
		cin >> H[i];
	}


	vector<vector<char>> C(K,vector<char>(M));
	rep(i,K){
		rep(j,M){
			C[i][j]='S';
		}
	}
	vector<int>A={};


	rep(i,K){
		rep(j,M){
			cout << C[i][j] << " ";
		}
		cout << "\n";
	}
	for(int x:A){
		cout << x << "\n";
	}
}

いい感じですね
次に方針を考えました
上から下に雑巾がけするように動けば壁がなかったとしたら全て清掃できますね。書いたものがこちらです

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define oke cout << "Yes" << '\n';
#define dame cout << "No" << '\n';
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using HaiI = vector<vector<int>>;
using Hai2 = vector<vector<ll>>;
using HaiB = vector<vector<bool>>;
using Hai3 = vector<vector<vector<ll>>>;

int N,M,K;
vector<pair<int,int>>R(10);
vector<string>V(30);//右と左に行くとき
vector<string>H(29);//上と下にいくとき
vector<vector<char>> C(10,vector<char>(10,'S'));
vector<vector<pair<int,int>>> CGO(10,vector<pair<int,int>>(10,{0,0}));
vector<int>A={};


void iku(int s){
	rep(i,K){
		int y=R[i].first, x=R[i].second;
		int yy=y+CGO[s][i].first, xx=x+CGO[s][i].second;

		if(xx < 0 || xx >= N || yy < 0 || yy >= N){
            continue;
        }
		if(y+1==yy && H[y][x] == '1'){
			continue;
		}
		if(y==yy+1 && H[yy][x] == '1'){
			continue;
		}
		if(x+1==xx && V[y][x] == '1'){
			continue;
		}
		if(x==x+1 && V[y][xx] == '1'){
			continue;
		}

		R[i]={yy,xx};
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(15);
	cin >> N >> M >> K;
	rep(i,M){
		int a,b;
		cin >> a >> b;
		R[i]={a,b};
	}
	rep(i,N){
		cin >> V[i];
	}
	rep(i,N-1){
		cin >> H[i];
	}


	rep(j,M){
		C[0][j]='U';
		CGO[0][j]={-1,0};
	}
	rep(j,M){
		C[1][j]='D';
		CGO[1][j]={1,0};
	}
	rep(j,M){
		C[2][j]='L';
		CGO[2][j]={0,-1};
	}
	rep(j,M){
		C[3][j]='R';
		CGO[3][j]={0,1};
	}


	rep(i,K){
		rep(j,M){
			cout << C[i][j] << " ";
		}
		cout << "\n";
	}

	rep(i,N){
		A.push_back(3);
	}
	rep(i,N){
		A.push_back(0);
	}
	rep(i,N){
		rep(j,N){
			if(i%2 == 0){
				A.push_back(1);
			}else{
				A.push_back(0);
			}
		}
		A.push_back(2);
	}
	for(int x:A){
		cout << x << "\n";
	}
}

左上にロボットを集めて雑巾がけの要領で動かすようにしました
この時のスコアは126790点
iku関数はロボットの今いる場所が必要になった時の布石に書いていますがロボットの動きシミュレーションは使いませんでした。

最初に左に集めるとき、N回左に動かしていたけど回数を減らしたりしてみたけどスコアはあまり変わりませんでした

第二章　迷走

この時点ではすべてのロボットが同じ動きをしていたので、一つだけ自由に動ける遊撃ロボットを作ろうとしました
雑巾がけをするロボットは上と下に行く回数が多いので上と下と上下左右で８通りの違う動きをするようにしました。
右と左は違う動きにできないのでそのまま同じ動きにしました

vector<char>goc={'R','L','U','D'};
	vector<int>gox={1,-1,0,0};
    vector<int>goy={0,0,-1,1};
	rep(i,4){
	rep(j,M){
		if(j==0){
			C[i][j]=goc[i];
			CGO[i][j]={goy[i],gox[i]};
			continue;
		}
		C[i][j]='U';
		CGO[i][j]={-1,0};
	}
	}
	rep(i,4){
	rep(j,M){
		if(j==0){
			C[i+4][j]=goc[i];
			CGO[i+4][j]={goy[i],gox[i]};
			continue;
		}
		C[i+4][j]='D';
		CGO[i+4][j]={1,0};
	}
	}
	rep(j,M){
		C[8][j]='L';
		CGO[8][j]={0,-1};
	}
	rep(j,M){
		C[9][j]='R';
		CGO[9][j]={0,1};
	}

違う動きをする機構はできたので次はきれいでないマスに遊撃ロボットを動かそうとしましたがここで迷走しました。

ロボットの場所からきれいでないマスの最短距離をBFSで求めました

void yuugekikyo(int i,int j){
	vector<int>gox = {1,0,-1,0};
	vector<int>goy = {0,1,0,-1};
	yuugekidist[i][j]=0;
	queue<pair<int,int>>Q;
	Q.push({i,j});
	while(!Q.empty()){
		int x,y;
        tie(y,x) = Q.front();
        Q.pop();
        rep(i,4){
            int xx=x+gox[i],yy=y+goy[i];
            if(xx < 0 || N <= xx || yy < 0 || N <= yy){
                continue;
            }
			if(y+1==yy && H[y][x] == '1'){
				continue;
			}
			if(y==yy+1 && H[yy][x] == '1'){
				continue;
			}
			if(x+1==xx && V[y][x] == '1'){
				continue;
			}
			if(x==x+1 && V[y][xx] == '1'){
				continue;
			}
            if(yuugekidist[yy][xx] > yuugekidist[y][x]+1){
                yuugekidist[yy][xx] = yuugekidist[y][x]+1;
				yuupre[yy][xx]=i;
                Q.push({yy,xx});
            }
        }

	}
}

しかし、自分はなぜか一回BFSしただけで複数のスタート場所からの複数のゴール場所の最短距離が分かると思っていました（？）
書いていて何言ってるかよくわからないけどこういう雰囲気のことを思ってました。ここで数十分使ってしまいました。

第三章　AIへの文句

この方針をいったん諦めて、螺旋状にロボットを動かそうとしました。
一回自分で作ろうとして何か間違えていると思ってAIを使って実装しようとしました。
これは自分が作ったコードです。

void seisou() {
    rep(i, hidaritika.second) {
        //左
        iku(8);
    }
    int cut = 1;
    int muki = 0;
    int hen = 1;
    bool dai = false;
    rep(i, N) {
        rep(j, N - 1) {
            //vector<char> goc = {'R','L','U','D'};
            if (cut == hen && dai) {
                hen++;
                if (muki == 0) {
                    muki = 3;
                } else if (muki == 1) {
                    muki = 2;
                } else if (muki == 2) {
                    muki = 0;
                } else if (muki == 3) {
                    muki = 1;
                }
                cut = 0;
                dai = false;
            }
            if (cut == hen) {
                if (muki == 0) {
                    muki = 3;
                } else if (muki == 1) {
                    muki = 2;
                } else if (muki == 2) {
                    muki = 0;
                } else if (muki == 3) {
                    muki = 1;
                }
                cut = 0;
                dai = true;
            }
            //左は雑巾がけロボットの動き、右は遊撃ロボットの動き
            iku(((i % 2) * 4) + (muki % 4));
            cut++;
        }
        //右
        iku(9);
    }
}

そしてこれがAIのコードです

void seisou_spiral(int start_x, int start_y, int N) {
    int dx[4] = {0, 1, 0, -1}; // 右下左上
    int dy[4] = {1, 0, -1, 0};
    int x = start_x;
    int y = start_y;
    int dir = 0; // 0=右,1=下,2=左,3=上
    int step = 1; // 現在の進むマス数
    int move_count = 0; // 何回方向を変えたか

    while (true) {
        for (int i = 0; i < 2; i++) { // 同じステップ数を2回繰り返す
            for (int j = 0; j < step; j++) {
                // ここで実際に移動
                iku(dir); // 方向に1マス移動
                x += dx[dir];
                y += dy[dir];

                // もしマスがグリッド外なら終了
                if (x < 0 || x >= N || y < 0 || y >= N) return;
            }
            dir = (dir + 1) % 4; // 90度方向転換
        }
        step++; // 2回繰り返したら step を増やす
    }
}

自分のコードを送った後に２ラリー会話はしたんですけどこのコードは本当に意味が分からないですね。
まず、関数の名前や変数が変わってます。何が何だか分からなくなりました
そして向きは(雑巾ロボットの値％4)＊４＋（遊撃ロボットの値%4）で管理していましたが遊撃ロボットの値%4だけにしてしまっています。
さらに{0,1,2,3}={右、左、上、下}にしています。
雑巾ロボットのことを考慮していないっぽいですね。
何なら // もしマスがグリッド外なら終了　とかいう意味わからないことをしています。

向きの話やグリッド外で終了を改善してほしいというと壁との当たり判定とか追加してきてバグがさらに増えていきました。
AIが出してくるコードを読む時間や修正しようとする時間がかさんでタイムロスしてしまいました。

自分の元のコードの未熟さや指示の出し方が変な可能性もあるけど、それにしたって変なコードを出してきます。問題文も自分のコードの意図もちゃんと伝えたつもりなのに。
コードのおかしいところを指摘しても直してくれないし、勝手に新しい要素を追加してきて使いづらかったです。
ニ度と使わないからな

第四章　横

AIとの喧嘩が終わった後、雑巾がけを横にすればもっとたくさんのマスをきれいにできると気が付きます。
さっきまで遊撃ロボットとして使っていたものを横雑巾として使いました

void seisou() {
	//vector<char>goc={'R','L','U','D'};
	int cut=0;
    rep(i,10) {
		iku(8);
		cut++;
	}

    rep(i,N){
        rep(j,N-1){
            //上と下にうごくものと右と左に動くもの
            iku(((i%2)*4)+(i%2));
			cut++;
        }
		if(i==0){
			continue;
		}
        iku(9);
		cut++;
    }
}

これによってスコアが劇的に上がり193822点！
ケースによっては全部のマス清掃できたものもありました！
ここから色々微調整したけどスコアは上がらず終了でした

反省

反省していきます
一つ目は全てのマスにきれいにした後すぐに操作を終わらせなかったこと
これを修正したら217396点になりました
二つ目は雑巾がけした後せっかく作ったBFSできれいでないマスに向かわなかったこと
まだ実装してないけど後で作りたいですね
AIはもう使いません