mooakiのブログ

貪欲に出来ることはまだあるかい?

マラソン系プロコンでコンソールでビジュアライズする話

これは何?

ラソン系のプログラミングコンテストTopcoder Marathon Match(MM)、AtCoder Heuristic Contest(AHC)など)で、コンソールでビジュアライズするのはいかがですか?とお勧めする記事です。 上記のようなコンテストではグラフィカルなビジュアライザーが公式に提供されることが多いですが、コンソールで見られるビジュアライザーを提出コードに書くことで、コードを実行するだけで動作を確認できる、公式ビジュアライザー以上の情報を盛り込むことができる、などのメリットがあります。

環境はwsl、プログラミング言語C++ですが、他の言語でも応用できると思います。

まず初めに

AHC011を題材に進めていきます。

atcoder.jp

まずは入力を読み込んで、盤面を標準エラー出力に出力してみます。

// 前略
// ソルバー
class Solver
{
    public:
    vector<int> grid;
    string answer;
    
    Solver() {};
    
    void init() {
        srand(time(NULL));
        cin >> N >> T;
        grid.resize(N * N);

// 中略
    }

    void input() {
        rep(r, N) {
            string s;
            cin >> s;
            rep(c, N) {
                grid[r * N + c] = s[c];
            }
        }
    }

    void output() {
        cout << answer << endl;
    }

    void show()
    {
        rep(r, N) {
            rep(c, N) {
                cerr << (char)grid[r * N + c];
            }
            cerr << endl;
        }
    }
    
    void solve() {
        init();
        input();
#ifdef LOCAL
        show();
#endif
        output();
    }
};

Solver solver;

int main()
{
    solver.solve();
}

コード全体はこちら。 Solver クラスの中で grid という int の vector に盤面を読み込みます。show()関数が標準エラー出力に盤面を出力します。呼び出しを #define LOCAL ~ #endif で囲うことで、コンパイル時に -DLOCAL オプションをつけた時だけ盤面出力をするようにし、このまま提出できるようにしています。 -DLOCALオプションを付けてコンパイルし実行した結果はこのようになります。

入力をそのまま出力しているだけですが、まず入力をきちんと読み込み保持出来ているか確認するのは、特に初心者には大事だと思います。

ちょっと動かしてみる

AHC011はスライドパズルで木を作る問題です。とりあえず空きマスをランダムに動かしてみましょう。

class Solver
{
    public:
    //    int N, T;
    vector<int> grid;
    
    Solver() {};
    string answer;
    
    void init() {
        srand(time(NULL));
        cin >> N >> T;
        grid.resize(N * N);
        nei4.resize(N * N);
        nei4rc.resize(N * N);

        // 4近傍事前計算
        rep(r, N) {
            rep(c, N) {
                rep(dir, 4) {
                    int r0 = r + DR[dir];
                    int c0 = c + DC[dir];
                    if(!inside(r0, c0)) continue;
                    nei4[r * N + c].push_back(dir);
                    nei4rc[r * N + c].push_back(r0 * N + c0);
                }
            }
        }
    }
// 中略
    void modify()
    {
        // 0 を探す
        int r0, c0; // 0 の位置
        rep(i, N * N) {
            if(grid[i] == '0') {
                r0 = i / N;
                c0 = i % N;
            }
        }
        // 動かす
        int rc0 = r0 * N + c0;
        int dir = nei4[rc0][rand() % nei4[rc0].size()];
        int r1 = r0 + DR[dir];
        int c1 = c0 + DC[dir];
        int rc1 = r1 * N + c1;
        swap(grid[rc0], grid[rc1]);
        answer.push_back(DIREC[dir]);
    }
    
    void solve() {
        int totaltime;
        init();
        input();
#ifdef LOCAL
        show();
#endif
        rep1(loop, LOOP_MAX) {
            modify();
#ifdef LOCAL
            cerr << "\nloop:" << loop << endl;
            show();
#endif
        }
        output();
    }
};

Solver solver;

int main()
{
    solver.solve();
}

ソース全体はこちらです。 ランダムに空きマスを移動しているのは modify()関数です。事前にnei4配列にセルごとに4近傍のうち移動可能な方向をリストアップしてあるので、その中からランダムに移動先を選びgridの値をswap()関数で入れ替えています。また移動方向をあらわす文字 DIREC[] を解を保持する変数 answer に追加しています。

そしてsolve()関数の中ではmodify()関数を呼び出してループ回数とgridの表示を LOOP_MAX 回繰り返しています。移動を確認できればいいので、とりあえず3回ループしてみましょう。

0が空きマスを表しています。初期状態から0が下→上→左と移動していて、最後に移動を表す"DUL"という文字列が標準出力に出力されています。よく見ると正しく操作が行われているのがわかりますが、ループ回数を上限のT回(2 * N ^ 3回)まで増やすと大量の表示があっという間にスクロールしていってしまいます。

表示位置を固定してみる

show()関数の表示位置を固定してループごとに上書きしてみましょう。コンソールで表示位置を指定するにはANSI エスケープシーケンスが使えます。ANSI エスケープシーケンスについてはこちらを参考にさせていただいてます。

qiita.com

エスケープ文字(プログラム中では '\e')に続けて所定の文字列を出力することでカーソル位置の指定や文字色背景色の変更、画面消去などができます。これはコンソール側の機能なのでプログラミング言語によらず利用することが出来ます。一方で利用するターミナルソフトによってANSI エスケープシーケンスへの対応に違いがあり、利用できないものがある場合もあります。 プログラム中でよく使いそうなものは関数にしておくと便利です。

// ANSI エスケープシーケンス関数
// カーソルを上へ移動
void escUp(int a)
{
    fprintf(stderr, "\e[%dF", a);
}

// 文字色を変更
void escColor(int c)
{
    fprintf(stderr, "\e[3%dm", c);
}

// 文字色を変更(拡張)
void escColorEx(int c)
{
    fprintf(stderr, "\e[38;5;%dm", c);
}

// 背景色を変更
void escBColor(int c)
{
    fprintf(stderr, "\e[4%dm", c);
}

// 背景色を変更(拡張)
void escBColorEx(int c)
{
    fprintf(stderr, "\e[48;5;%dm", c);
}

// 表示属性をリセット
void escReset()
{
    fprintf(stderr, "\e[0m");
}

// 画面消去
void escClear()
{
    fprintf(stderr, "\e[2J");
}

// カーソル位置を移動
void escLocate(int r, int c)
{
    fprintf(stderr, "\e[%d;%dH", r + 1, c + 1);
}

上記の関数を使って次のように変更します。

// ソルバー
class Solver
{
    public:
    //    int N, T;
    vector<int> grid;
    
    Solver() {};
    string answer;
    
    void init() {
        srand(time(NULL));
        cin >> N >> T;
        grid.resize(N * N);
        nei4.resize(N * N);
        nei4rc.resize(N * N);

        // 4近傍事前計算
        rep(r, N) {
            rep(c, N) {
                rep(dir, 4) {
                    int r0 = r + DR[dir];
                    int c0 = c + DC[dir];
                    if(!inside(r0, c0)) continue;
                    nei4[r * N + c].push_back(dir);
                    nei4rc[r * N + c].push_back(r0 * N + c0);
                }
            }
        }
#ifdef LOCAL
        escClear();
#endif
    }

// 中略

    void show()
    {
        escLocate(0, 0); // 画面左上にカーソルを移動
        rep(r, N) {
            rep(c, N) {
                cerr << (char)grid[r * N + c];
            }
            cerr << endl;
        }
        usleep(250 * 1000); // 250ms のウェイト
    }
    
// 中略

    void solve() {
        int totaltime;
        init();
        input();
#ifdef LOCAL
        show();
#endif
        rep1(loop, T) {
            modify();
#ifdef LOCAL
            show();
#endif
        }
        output();
    }
};


Solver solver;

int main()
{
    solver.solve();
}

初期化関数 init() の中でescClear()関数を呼び出し画面消去しています。また show()関数で初めにカーソル位置を(0, 0)(左上隅)に移動してから表示してます。そのままだと一瞬で表示が終わってしまうので usleep()関数で250msのウェイトを入れています。 実行すると次の様になります。

youtu.be

0がランダムに移動していることがわかりますが見づらいですし、グラフの繋がり具合もパッと見ただけではわかりません。

グラフを表示してみる

タイルを分かりやすく表示するにはどうしたらいいでしょうか。1文字で各タイルを表現できる文字があれば比較的簡単ですが、そのような記号文字はなさそうです。今回は各タイルを3×3文字で表現してみます。中心の頂点は'*'、縦横に伸びる枝は'|'と'-'を使います。今までの様に上の行から順番に出力しようとするとプログラムが複雑になりそうなので、表示用のバッファを用意しタイルごとにバッファに書き込んだ上で出力します。 これまでは盤面を表すgridを読み込んだ文字のまま保持していましたが、扱いやすいよう読み込んだ段階で'0'から'f'の文字を0から15の数値に変換しておきます。show()関数は次の様になります。

    void show()
    {
        int N3 = N * 3;
        vector<string> buf(N3 * N3);
        escLocate(0, 0);
        rep(r, N) {
            rep(c, N) {
                int rc = r * N + c;
                // 空白で初期化
                rep(r1, 3) {
                    rep(c1, 3) {
                        int rc1 = (r * 3 + r1) * N3 + (c * 3 + c1);
                        buf[rc1] = " ";
                    }
                }
                if(grid[rc] != 0) {
                    int rc1 = (r * 3 + 1) * N3 + (c * 3 + 1);
                        buf[rc1] = "*";
                }
                
                rep(dir, 4) {
                    if(grid[rc] & (1 << dir)) {
                        int rc1 = (r * 3 + 1 + DR[dir]) * N3 + (c * 3 + 1 + DC[dir]);
                        buf[rc1] = "-|"[dir%2];
                    }
                }                
            }
        }

        rep(r, N * 3) {
            rep(c, N * 3) {
                int rc = r * N3 + c;
                cerr << buf[rc];
            }
            cerr << endl;;
        }
        
        usleep(250 * 1000);
    }

ソース全体はこちらです。 実行するとこのようになります。

youtu.be

もうちょっと見栄えをよくする

グラフの繋がりが分かるようにはなりましたが、もう少し見栄えをよくするために背景色で表示してみます。またタイルが縦長なので、正方形に近づけるためにバッファの1要素を半角の空白1文字から2文字にします。さらにタイルの境界が分かりやすいように背景をグレーの濃淡で市松模様にしてみましょう。ANSIエスケープシーケンスによる色の指定などをバッファに追加できるように、これまで標準エラーに出力していたANSIエスケープシーケンスをstring型で返す関数を用意しました。

    void show()
    {
        char sb[255];
        int N3 = N * 3;
        vector<string> buf(N3 * N3);
        int back_color[] = {0xEC, 0xEF};
        
        escLocate(0, 0);
        rep(r, N) {
            rep(c, N) {
                int rc = r * N + c;
                // 空白で初期化
                rep(r1, 3) {
                    rep(c1, 3) {
                        int rc1 = (r * 3 + r1) * N3 + (c * 3 + c1);
                        buf[rc1] = escSBColorEx(back_color[(r + c) % 2]) + "  " + escSReset();
                    }
                }
                if(grid[rc] != 0) {
                    int rc1 = (r * 3 + 1) * N3 + (c * 3 + 1);
                    buf[rc1] = escSBColorEx(0x82) + "  " + escSReset();
                }
                
                rep(dir, 4) {
                    if(grid[rc] & (1 << dir)) {
                        int rc1 = (r * 3 + 1 + DR[dir]) * N3 + (c * 3 + 1 + DC[dir]);
                        buf[rc1] = escSBColorEx(0x82) + "  " + escSReset();
                    }
                }
            }
        }

        rep(r, N * 3) {
            rep(c, N * 3) {
                int rc = r * N3 + c;
                cerr << buf[rc];
            }
            cerr << endl;;
        }
        
        usleep(250 * 1000); // 250ms スリープ
    }

ソース全体はこちらです。 そして実行結果はこちらです。

youtu.be

とても見やすくなりテンションがあがりますね!コンテストへのやる気もアップするというものです。え?自分だけ?

ここまでで、プログラムを実行するだけでビジュアライザーで動作を確認できるようになりました。ですが、まだ公式のビジュアライザーに比べ最大の木を色を変えて表示出来てないので情報量としては負けています。さらに工夫して公式にはない情報を盛り込み、現状の解法の改善点を見つけやすくすることでスコアアップに繋げられるかどうかはあなた次第です!!

気を付けること

今回表示の更新速度を落とすためにusleep()関数でウェイトを入れています。実行時間制限いっぱいに解を探索しながらビジュアライズする場合、当然ですがビジュアライズしない場合より探索できる量が大幅に落ちてしまいます。あくまで動作の確認時にのみ表示するか、ビジュアライズ時は探索時間を延ばすなどの工夫が必要でしょう。

おわりに

男の子ってこういうのが好きなんでしょ?

自分も大好きです。普段のprintfデバッグANSI エスケープシーケンスで色を付けるだけでもグッと視認性がよくなります。この記事で自作ビジュアライザー画像をシェアしてくれる方が増えると嬉しいです。エスケープシーケンス大好きおじさんなので。

おまけに

かっこいいビジュアライザーが出来たら、スクショを撮ってうまく切り抜いて一辺が2000pixくらいにサイズ調整して SUZURI というグッズ作成サイトでTシャツにしてみるのも楽しいですよ。

「HACK TO THE FUTURE 2022 予選」の一括テストスクリプトをAWKで書いた話。

「HACK TO THE FUTURE 2022 予選」とは

 フューチャー(株)が主催したいわゆるマラソン形式のプログラミングコンテストです。コンテストページはこちら

一括テストスクリプトとは

 マラソンコンテストで自分のプログラムの性能をより正確に評価するには、ローカル環境で多くのテストケースを与えた出力を見る必要があります。手作業ではとてもやってられないので「機械的な作業は機械にやらせる」の精神で一括でテストするスクリプトを書いてしまおう、という話です(環境はWSLのubuntuです)。


AWKとは

 AWKオーク)は、プログラミング言語の一つ。 テキストファイル、特に空白類(スペースの他、タブなど)やカンマなどで区切られたデータファイルの処理を念頭に置いた仕様となっているが、一般的なプログラミングに用いることも可能である。UNIX上で開発された。

Wikipediaより)

 つい「えーだぶりゅけー」って読んじゃうんですけど「オーク」が正しいようです。

 オークと呼ぼう!えーだぶりゅけー!

 なんで今回数ある言語の中からAWKを選んだかというと、外部コマンドの出力を取り込むのが簡単なような気がしたからです(自分の書ける言語の中では)。


書いてみる

 まずAWKスクリプトを書くときのひな型です。

#!/bin/bash
awk 'BEGIN {
}

 この"{"と"}"の間に処理を書いていきます(本来はBEGINアクションといって前処理を書く部分です)。

 今回は公式テスターと一緒にinフォルダーに0000.txtというような形式でテストケースが与えられますので、まずinフォルダーにあるファイルのファイル名を取得し表示してみます。

#!/bin/bash
awk 'BEGIN {
    while(("ls in" | getline) > 0) {
        print  $1
    }
}

まず

"ls in" | getline

の部分で外部コマンド(ls in)を実行した結果を1行づつ読み込みます。"while( ~ >0)"とすることで入力のある間、その後に書かれた処理を繰り返しています。入力はデフォルトでは空白文字で分割され先頭から$1,$2,...という変数に格納されます(分割まえの行全体は$0)。 なので

print $1

で1個目の項目を表示できます。

これを使って今回実行したいコマンドにしてみます。 今回のテスターは

cargo run --release --bin tester cmd < in.txt > out.txt

という形式で実行します。cmdが自分で作成したプログラム、in.txt、out.txtは入力ファイルと出力ファイルです。 このcmdを変数cmdで、in.txtとout.txtをそれぞれinフォルダとoutフォルダのファイル$1になるよう置き換えます。

#!/bin/bash
awk -v "cmd=$1" 'BEGIN {
    while(("ls in" | getline) > 0) {
        print("cargo run --release --bin tester ./" cmd " < in/" $1 " > out/" $1 " 2>> score.txt")
    }
}

 2行目、「awk」のあとの「-v "cmd=$1"」でコマンド実行時のオプションとして与えられた実行ファイル名を変数cmdに代入しています。 最後の「2>> score.txt」ですが、今回のテスターはスコアを標準エラーに出力するので、score.txtというファイルにリダイレクトで追加書き込みすることにしました。

 4行目、AWKでは文字列や変数をスペースで並べて書けば文字列として連結してくれます。

 実行してみると、

 まだprint文で表示しているだけですが、うまくいっているようです(入力ファイルは10個にしました)。これを変数sに代入してsystem関数で実行します。

#!/bin/bash
awk -v "cmd=$1" 'BEGIN {
    while(("ls in" | getline) > 0) {
        s = "cargo run --release --bin tester ./" cmd " < in/" $1 " > out/" $1 " 2>> score.txt"
        print s
        system(s)
    }
    close("ls in")
    total = 0
    while(("grep Score score.txt" | getline) > 0) {
        print $3
        total = total + $3
    }
    print total
}

8行目は外部コマンドを実行した結果を受け取るために開いたパイプをクローズしています。 その後、score.txtからgrepコマンドで"Score"の含まれた行を抽出し、その3項目目($3)を変数totalに加算していきます。文字列から数値への変換はAWKがいい感じにやってくれます。 最後にprint文でスコアの合計値を出力します。 実行してみると一見うまくいくようですが、2回目以降は残っているscore.txtファイルにさらに追加してしまうので、合計値が大きくなってしまいます。最初にrmコマンドでscore.txtファイルを消去するようにします。

#!/bin/bash
awk -v "cmd=$1" 'BEGIN {
    system("rm -f score.txt")
    while(("ls in" | getline) > 0) {
        s = "cargo run --release --bin tester ./" cmd " < in/" $1 " > out/" $1 " 2>> score.txt"
        print s
        system(s)
    }
    close("ls in")
    total = 0
    while(("grep Score score.txt" | getline) > 0) {
        print $3
        total = total + $3
    }
    print total
}

これで正しいスコアの合計値が出力されます。このままでもテストは出来るのですが、うっかり実行するプログラムの指定を忘れたときのためにusageを出力して終了してみます。

#!/bin/bash
awk -v "cmd=$1" 'BEGIN {
    if(cmd=="") {
        print "usage: mytest cmd"
        exit
    }
    system("rm -f score.txt")
    while(("ls in" | getline) > 0) {
        s = "cargo run --release --bin tester ./" cmd " < in/" $1 " > out/" $1 " 2>> score.txt"
        print s
        system(s)
    }
    close("ls in")
    total = 0
    while(("grep Score score.txt" | getline) > 0) {
        print $3
        total = total + $3
    }
    print total
}

 これでうっかりさんも安心ですね。

 コンテスト中はこんな感じでテストを回していたんですが、各テストケースのスコアが実行後にまとめて出力されるので「seed=5のスコアは?」なんてときに不便です。各テスト実行後にスコアを逐次出力するならこんな感じでしょうか。

#!/bin/bash
awk -v "cmd=$1" 'BEGIN {
    if(cmd=="") {
        print "usage: mytest cmd"
        exit
    }
    system("rm -f score.txt")
    total = 0
    while(("ls in" | getline) > 0) {
        s = "cargo run --release --bin tester ./" cmd " < in/" $1 " > out/" $1 " 2>> score.txt"
        print s
        system(s)
        if(("grep Score score.txt" | getline) > 0) {
            print $3
            total = total + $3
        }
        close("grep Score score.txt")
        system("rm score.txt")
    }
    close("ls in")
    print total
}

テスト実行ごとにscore.txtからスコアを読み取って削除しています。

 この方が便利だったな。

実際に使うには(追記)

 上記の内容をファイルに書き込み(例えばmytest)、

chmod a+x mytest

などとして実行可能にする必要があります。詳しくはこちら

最後に

 自分の乏しい知識で「動きゃあいいんだよ」と書いたものなので、もっと上手い書き方や、もっとお手軽な言語があるかもしれません。あったら教えてください。説明にも正確じゃない所や間違っている点もあるかもしれません。ご容赦ください(教えてくださいとは言わない)。 HTTF2022予選自体は、ビジュアライザに力が入っていて素晴らしかったし、seed=0のビジュアライザをシェア出来るのも、公平さなどには検討の余地があるかもしれませんが盛り上がって楽しかったです。準備された皆さん、本当にありがとうございました。

 解法記事書くほどの面白考察もできなかったので、こんな話題でお茶を濁してみました。いかがでしたか?

AHC005参加記

AHC005に参加した記録です。 ※マラソン強い人が読んでも得るものはないし、マラソン初心者が参考にしても強くはなれないと思います。そのくせ無駄に長いです。

atcoder.jp

問題

N*Nのグリッドをパトロールする最短経路を求めよ(各セルまで行かなくても見通せればOK)。

方針

小さなことからコツコツと。 自分の場合、短時間マラソンコンテストで焦って実力以上の実装をしようとしてバグりまくるのがありがちなので無理はしないことにします。

枠組みを作る

まずはプログラムの枠組みを作って、入出力を確認します。 つい先日までMM128でもグリッドの問題を解いてたので、それを流用しました。

  • 解を保持するAnswerクラス

内部では0~3の数字で持っておいて、出力するときに文字にします。

  • グリッドのデータを保持するGridクラス

グリッドは2次元ですが1次元配列で持ってgrid[r * N + c]でアクセスすることにします。障害物'#'は0にしました。

  • 問題解決のためのSolverクラス

変数N,si,sjと解とグリッドを保持し、input()でデータを読み込み、solve()で解を求め、output()で出力します。solve()ではmake_first_answer()を呼び出しています。まず初期解を作り、少し変更してスコアが改善すれば新しい解として採用するのを繰り返す「山登り法」を意識して書いたのですが、今回は山登り法はしませんでした。 まずは動作確認したいのでmake_first_answer()は4方向で移動できる方向に1セル移動して逆方向に戻るだけにしています。

  void make_first_answer() {
    int r0 = si;
    int c0 = sj;
    rep(d, 4) {
      int r1 = r0 + DR[d];
      int c1 = c0 + DC[d];
      if(map.grid[r1 * N + c1] != 0) {
        ans.root.push_back(d);
        ans.root.push_back((d + 2) % 4);
        break;
      }
    }
  }

全体はこうなります。

// C++11
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <map>
#include <sstream>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <chrono>

using namespace std;
typedef long long ll;

#define MOD (long long)(1e9+7)
#define INF (1LL<<60)
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define rep1(i,n) for(ll i = 1; i <= (n); i++)
#define SIGN(x) (((x) == 0) ? 0 : ((x) > 0) ? 1 : -1)
#define DBG(x) cerr << #x << ": " << x << "\n" 

int DR[] = {1, 0 ,-1, 0}; // DRUL
int DC[] = {0, 1, 0, -1};
string DIR = "DRUL";

class Answer
{
public:
  vector<int> root;
  
  void output() {
    rep(i, root.size()) {
      cout << DIR[root[i]];
    }
    cout << "\n";
  }
};

class Grid
{
public:
  int N;
  vector<int> grid;

  Grid() {}
  Grid(int n) {
    N = n;
    grid.resize(n * n);
  }
  void read()
  {
    rep(r, N) {
      string s;
      cin >> s;
      rep(c, N) {
        if(s[c] == '#') {
          grid[r* N + c] = 0;
        } else {
          grid[r* N + c] = s[c] - '0';
        }
      }
    }
  }

  void dump()
  {
    rep(r, N) {
      rep(c, N) {
        cerr << grid[r * N + c] ;
      }
      cerr << "\n";
    }
  }

  Grid& operator=(const Grid& a) 
  {
    this->N = a.N;
    this->grid = a.grid;
    return *this;
  }
};

class Solver
{
public:
  ll N, si, sj;
  Grid map; // 名前がmapクラスとぶつかってるのに後から気づいた。良い子はマネしない。
  Answer ans;
  
  Solver() {};

  void input() {
    cin >> N >> si >> sj;
    map = Grid(N);
    map.read();
#ifdef LOCAL
    map.dump();
#endif
  }

  void output() {
    ans.output();
  }

  void make_first_answer() {
    int r0 = si;
    int c0 = sj;
    rep(d, 4) {
      int r1 = r0 + DR[d];
      int c1 = c0 + DC[d];
      if(map.grid[r1 * N + c1] != 0) {
        ans.root.push_back(d);
        ans.root.push_back((d + 2) % 4);
        break;
      }
    }
  }

  void solve() {
    make_first_answer();
  }
};

Solver solver;

int main()
{
  solver.input();
  solver.solve();
  solver.output();
  return 0;
}

「class で全メンバー public にするなら struct でいいんじゃないの?」 それはそうです。でも class の方がオブジェクト指向プログラミングしてる感が出る気がするので。それだけです。

提出すると25,571点になります。 (seed=0の場合:以下同じ) f:id:mooaki:20210809131931p:plain

全部回る

得点の計算式を見ると、全マス見て回らないと点数が伸びないので、まずは全マスを巡回します。まだ見てないマスを保持するグリッドGrid nsy;(not seen yetのつもり)とその数num_nsyをsolverに追加します。nsyは見てないマスを1、見たマスは0にします。 巡回する手順は

  • 目的地(まだ見てないマス)を一つ選ぶ(find_dest()
  • 目的地までの最短ルートをBFSで求める(find_path()
  • 求めたルート通りに移動しながら縦横見えたマスのnsyを0にしていく(moveto()

を未見のマスがなくなるまで繰り返し、スタート地点へBFSで戻ります。マス間の移動はそれぞれ5~9のコストが与えられているのですが無視します。

目的地を選ぶfind_dest()は、効率は後回しにして取り合えず左上から順に走査して未見のマスを返します。

  int find_dest() {
    rep(i, N * N) {
      if(nsy.grid[i] != 0) {
        return i;
      }
    }
    return -1;
  }

BFSでルートを探すfind_path()はルートの復元も必要です。 なので、既に調べた(見た)マスを記録するGrid lookedに、どの向きからそのマスに来たかも記録することにします。またBFSのスタート地点は-1にしておきます。

Answer find_path(int r0, int c0, int r1, int c1) {
    Answer ret;
    Grid looked(N);
    queue<pair<int, int>> que;
    que.push({r0, c0});
    looked.grid[r0 * N + c0] = -1;
    pair<int, int> p0;
    while(que.size() > 0) {
      p0 = que.front();
      que.pop();
      rep(d, 4) {
        int r2 = (p0.first) + DR[d];
        int c2 = (p0.second) + DC[d];
        if(r2 < 0 || r2 >= N || c2 < 0 || c2 >= N) continue;
        if(map.grid[r2 * N + c2] == 0) continue;
        if(looked.grid[r2 * N + c2] != 0) continue;
        
        looked.grid[r2 * N + c2] = d + 1;
        if(r2 == r1 && c2 == c1) {
          /* ルート復元して返す */
          while(r2 != r0 || c2 != c0) {
            int d1 = looked.grid[r2 * N + c2] -1 ;
            ret.root.push_back(d1);
            r2 = r2 - DR[d1];
            c2 = c2 - DC[d1];
          }
          reverse(ret.root.begin(), ret.root.end());
#ifdef LOCAL
          cerr << "path:" ;
          rep(i, ret.root.size()) {
            cerr << DIR[ret.root[i]] << " ";
          }
          cerr << " \n";
#endif
          return ret;
        }
        que.push({r2, c2});
      }
    }
#ifdef LOCAL
    cerr << "can't find way\n";
#endif
    return ret;
  }

pathとrootとwayがごちゃ混ぜになってますが「動きゃあいいんだよ」ということにしておきます(おい)。

そして実際に移動するmoveto()は次の通りです。

  int moveto(int& r0, int& c0, int d) {
    int r = r0 + DR[d];
    int c = c0 + DC[d];
    if(r < 0 || r >= N || c < 0 || c >= N) return -1;
    if(map.grid[r * N + c] == 0) return -1;
    r0 = r;
    c0 = c;
    see(r, c);
    return 1;
  }

moveto()の中で呼んでるsee()は現在地から縦横見えるマスをチェックしています。

  void see(int r0, int c0) {
    rep(d, 4) {
      int r = r0;
      int c = c0;
      while(1) {
        r += DR[d];
        c += DC[d];
        if(r < 0 || r >= N || c < 0 || c >= N) break;
        if(map.grid[r * N + c] == 0) break;
        if(nsy.grid[r * N + c] != 0) {
          nsy.grid[r * N + c] = 0;
          num_nsy --;
        }
      }
    }
  }

これらを利用してmake_first_answer()を書き換えます。

  void make_first_answer() {
    int r0 = si;
    int c0 = sj;
    Answer path1;
    while(num_nsy > 0) {    
      int p0 = find_dest();
      if(p0 < 0) break;
      Answer path1 = find_path(r0, c0, p0 / N, p0 % N);
      rep(i, path1.root.size()) {
        if(moveto(r0, c0, path1.root[i]) <0) {cerr << "error\n";}
        ans.root.push_back(path1.root[i]);
      }
    }

    // スタートへ戻る
    path1 = find_path(r0, c0, si, sj);
    rep(i, path1.root.size()) {
      moveto(r0, c0, path1.root[i]);
      ans.root.push_back(path1.root[i]);
    }
  }

提出すると 7,471,649点です。

f:id:mooaki:20210809135151p:plain

ここまでで約2時間です。BFSでバグらせたり経路復元のリバースを忘れていたりしました。デバッグはとにかく気になる変数をcerrに書き出します。BFSでTLE/MLEする場合はキューのサイズを出力して大きくなりすぎていないか見るのもいいかと思います。デバッグが済んできれいに全マスをパトロール出来るようになったときは、ちょっと感動しました。

袋小路対策

ビジュアライザを見て気付く無駄は、左上から順に未見の地点を回っているのと袋小路の奥まで移動していることです。まず袋小路対策をします。移動中に目的地を視認出来たら、移動をストップすることにします。具体的にはmake_first_answer()の中で求めたパス通りに1マス移動するごとに目的地が視認されたかチェックするようにします。if(nsy.grid[p0] == 0) break;という行がそれです。

  void make_first_answer() {
    int r0 = si;
    int c0 = sj;
    Answer path1;
    while(num_nsy > 0) {    
      int p0 = find_dest();
      if(p0 < 0) break;
      Answer path1 = find_path(r0, c0, p0 / N, p0 % N);
      rep(i, path1.root.size()) {
        if(moveto(r0, c0, path1.root[i]) <0) {cerr << "error\n";}
        ans.root.push_back(path1.root[i]);
        if(nsy.grid[p0] == 0) break; // 目的地を視認出来たらストップ
      }
    }

    // スタートへ戻る
    path1 = find_path(r0, c0, si, sj);
    rep(i, path1.root.size()) {
      moveto(r0, c0, path1.root[i]);
      ans.root.push_back(path1.root[i]);
    }   
  }

提出すると 8,669,260点です。1行足しただけでスコア伸びて楽しいですね。

f:id:mooaki:20210809140540p:plain

効率化1

いよいよパトロール順の効率化を考えます。今いる地点からBFSで最寄りの未見のマスを目的地にしてみます。 左上から全探索するだけだったfind_dest()をBFSに書き換えます。

  int find_dest(int r0, int c0) {
    Grid looked(N); 
    queue<pair<int, int>> que;
    que.push({r0, c0});
    looked.grid[r0 * N + c0] = 1;
    while(que.size() > 0) {
      pair<int, int> p;
      p = que.front();
      que.pop();
      rep(d, 4) {
        int r1 = p.first + DR[d];
        int c1 = p.second+ DC[d];
        if(r1 < 0 || r1 >= N || c1 < 0 || c1 >= N) continue;
        if(map.grid[r1 * N + c1] == 0) continue;
        if(looked.grid[r1 * N + c1] != 0) continue;
        if(nsy.grid[r1 * N + c1] != 0) {
          return r1 * N + c1;
        }
        que.push({r1, c1});
        looked.grid[r1 * N + c1] = 1;
      }
    }
    return -1;
  }

提出すると 15,762,075点です。さすがにこれはスコアの伸びが大きくて、してやったりです。

f:id:mooaki:20210809142302p:plain

効率化2

ビジュアライザで途中の様子を見てみます。

f:id:mooaki:20210809142702p:plain

左下の通りを見ずに右へ移動してしまい、この後左に戻ってくることになります。目的地を決めるfind_dest()をBFSではなく、現在地からのマンハッタン距離と周辺からの距離の和で決めることにします。近場は見て回ってから先へ進もうという狙いです。色々試してみると「現在地からのマンハッタン距離」と「周辺からの距離」の比で結果が変わることがわかりました。与えられる地図ごとの最適な比はわからないので、比を変えていくつか試した結果で最短距離(マス目の数で)のものを出力するようにします。まだ各マスの移動コストは考えてません。

提出すると15,836,612点です。微増ですね。

f:id:mooaki:20210809150311p:plain

効率化3

夕食をとったこともあって、残り約40分になりました。ここからスコア計算して山登り法へ持っていくのは自分には厳しいので、小手先の改善を試みます。 与えられていてまだ利用してないものといえば、各マス間の移動コストです。きっちり計算するのは面倒なので(おい)、BFSでの検索順を移動コストの低い方向から見ることにしてみます。ビジュアライザでseed = 0の結果を見るとスコアが下がってしまいました。ですが、今回は時間内の提出での最高スコアが採用されるので提出するだけしてみます。 すると 15,906,884点と微増しました。それでいいんかい。いいんです(本当に?)。

悪あがき

「現在地からのマンハッタン距離」と「周辺からの距離」の比の試行の幅を増やしてみました。提出すると 17,108,017点。悪あがきもしてみるもんですね。

乱択にしてみる

提出のスコアは少しづつ改善してますが、seed = 0 だけ見ると実はBFSの方が高得点でした。なので、目的地を決めるときにランダムにBFSと「現在地からのマンハッタン距離と周辺からの距離の和」のどちらかを採用することにします。ランダム要素が出来たので、3秒の制限時間いっぱい(実際は余裕をもって2700msにしました)ルート生成を繰り返して一番良いものを出力します。 ぐっと伸びて 18,977,180点になりました。イェア!

f:id:mooaki:20210809153628p:plain

おまじない

rand()を使うときのおまじないsrand(time(NULL));を忘れていたのでmain()に書き加えました。 提出してみると19,027,578点。たまたま乱数がうまいこといっただけのような気もしますが、なんとか19Mに乗りここでタイムアップ。

結局焼きなましやビームサーチどころか山登りもせずに終わってしまいましたが、最終的に54位。緑コーダーではトップで終わることが出来ました。

f:id:mooaki:20210809161502p:plain

終わってみて

多くの人が最初から巡回サラリーマン問題として解いていたようです。ああ、言われてみれば…。袋小路も、多くの人が前処理で片付けていました。でもなんとかなったよ?2-opt?聞いたことはありますね…。結局BFSしかしなかったなぁ。あと結構DFSしたってツイートを見ました。自分は最短マス数で移動したかったんでBFSしたんですけど、DFSはなんでですかね。

多くの人の方針とは何か違う解法だったようです。自分的にはもう時間があっても改善できる気がしないので、8時間とか1週間とかのコンテストだったらズルズルと落ちていく順位表を眺めているだけだったと思います。 という訳でもう一度言います。ラソン初心者が参考にしても強くはなれないと思います。

じゃあ、なぜ書いた?…ワクチン接種後の休みで一日暇だったんです、としか。ごめんなさい。

MM128参加記

MM128に参加しました。

今回はTCO21 Regionalsの一環として開催されていて、いつもと桁違いの賞金が用意されてましたが、日本を含む東アジア地区は層が厚すぎてねぇ…。

 

一日目

英語でさっぱりわからない開会式のあと、MM128の問題が公開されました。N*NのグリッドのC種類の色のボールを隣同士スワップで各色4近傍でつながるようにするための手数を最小化せよ、といった感じ。ビジュアライザが動くのでテンション上がります(単純)。あとMMでは久々にインタラクティブじゃない問題でした(よね?)。今回は72時間しかないので、手っ取り早く正の点数を取る方法を、と思ったのですが、ちょっと思いつかなかったのでとりあえず寝ました。

二日目

ディレクトリ掘って、ダウンロードするものダウンロードして、シンプル過ぎるサンプルコード眺めておしまい。

三日目

各列縦にソートとか試してみたけど、運がいいケースでしか正の点数にならないので、腹をくくってコード書くことにしました。

まずは上からつづら折りにボールを並べた状態を最終形として、上から順番にそろえていきました。

f:id:mooaki:20210805212258p:plain

これで26点くらい。

四日目

並べる様子を眺めてると右のを左にもっていったり左のを右にもっていったり無駄が多い気がしたので、色別に縦にならべて上から揃えてみました。

f:id:mooaki:20210805213405p:plain

これで42点くらい。

この後、移動するボールを探すのに上から走査線式に探索してたのをBFSで最短距離のボールを探すようにしたり、四隅から揃えたりしてみましたが、さほど改善せず。上から揃えていたのを上と下から交互に揃えるようにしたら少し良くなったりしました。

なんかもう何も思いつかない気がしていたのですが、子供の習い事の送迎でパソコンを離れていると、気が付いたことがありました。上の図で言えば、青いボールは全体に散らばっていたのを全部左に寄せているのですが、4連結でさえあればむしろグリッドに広がっている形の方が移動距離が少ないのでは?でもそれぞれの色が4連結で、でも広がっているってどんな形?グリッドのサイズや色数によらず4連結が保証される配置にするにはどうしたらいい?あれこれ考えた結果中心から2本の渦巻きが伸びる形にしてみました。

f:id:mooaki:20210805221939p:plain

これで57点。アイデアをせっせとコーディングしたらグッとスコアが伸びて、これぞマラソンの醍醐味って感じ。この後、色の並べる順番をnext_permutationで順次試して、一番スコアのいいのを出力するようにしたら66点程になりました。まだ終了まで時間はありましたが、今度こそ、もうアイデア尽きたぞということで、家族とホタルを見に釧路湿原へ行ってきました。子供たちも夏休みだしね。

f:id:mooaki:20210805223329j:plain

 

提出締め切った時点で暫定18位。渦巻き直ぐに思いついた方多かったようですね。

結局今回も焼きなましやビームサーチどころか山登りもせずに終わってしまいましたが、BFSやnext_permutationなどアルゴの知識が生かせて面白かったです。あと、日本、層厚すぎ。

 

 

MM127参加記

TopcoderのMM127に参加しました。

エンジョイ勢の感想文なので、さほど参考にはならないと思いますが。

問題概要

速さが異なるN台の車をK台以下づつ競走させてその結果から総合順位を求める。

競走回数が少ないほど高スコア。

初めにやったこと

問題ページにgifがない=ビジュアライザーが提供されないことにがっかりしつつ問題を読む。「ソートだな」と思ってまずWikipediaのソートのページでソートアルゴリズムをあれこれ見る。効率のよいソートと言えばクイックソートなんだけど、コムソート(櫛ソート)ってのが知らなかったし計算量NlogNらしいし謎のパラメータ1.3とか気になったので実装してみて提出→結果1.6くらい。最低点争いですか?まあKがいくつでも2要素の比較しかしてないし。250レーンを走る2台の車。

 

次にやったこと

エスケープシーケンスでビジュアライズしてソートの様子を眺めていたら同じ要素を何度も比較している。そりゃ効率わるいわ。そういえばAHC003でも一度得た結果を保存しておいて何度も使いまわしたらスコア改善したな。比較結果を保存しておこう。配列はN×Nで、自分同志の部分(対角線)はいらなくて…。ハッΣ(゚□゚;)それってリーグ戦の対戦表では?…ということでリーグ戦の表を効率よく埋める問題を考える。

 

とりあえず対戦は表の空いてる部分からランダムに組んでみる。車の速度は全部異なり固定なので、AがBに勝ちBがCに勝っていれば、A対Cは実際に対戦しなくてもAの方が速いことが推測される。…という感じでプログラム書いてみたものの、ローカルテスタのSEED=2(N=1000)で20秒弱かかる。制限は10秒なので当然TLEなのだけど、そこまで大きくないテストケースなら通るので提出してみると40点弱。とりあえず最低点争いは脱する。TLEがあっても点数ほしい人はMMをやろう(?)

 

まずはTLEを何とかせねば。計算量削減をあれこれ試みるもむしろ実行時間が数倍になったりして、競プロerとしての実力の無さを思い知らされる羽目に。

 

埒が明かないので、計算量削減はあきらめて効率よい対戦の組み方を考えることにする。全体の対戦数を減らせれば実行時間も減るわけだし。ということでまたエスケープシーケンスでビジュアライズしたリーグ表が埋まっていく様を眺める。最後に残るのは順位が1つ違いの組み合わせであることに気づく。順位が一つ違いということはその対戦以外の勝敗は同じなので、推測では埋められず残っちゃうということかな。順位が近そうな対戦を優先して組めば効率よくなるかも?勝利数の度数分布調べて、多い勝利数の車同士の対戦を優先して組むか、と思ったけど面倒くさいので、とりあえず単純に勝利数でソートして順番に対戦させてみることに…。

 

ん?N=1000でもTLEどころかあっという間に終了したぞ?スコアは?さっきまで4桁だったのに3桁、400点弱…?え?え?マジ?

 

これは順位上がるかもと期待しつつ提出………

 

え?9位?Σ(゚□゚;)

いやいや、ソートしただけだし、何も探索してないし、こんなプログラムでこんな順位いいんですか???

 

その後の展開

もう少し効率良くならないかと、勝利数の度数分布から対戦組んでみたり、試合数でソートして対戦組んでみたり、まず0番は残り全部と対戦させてみたり、雑に乱択してみたり、思いつくこと試してみたけど、スコア下がったり無限ループにはまったりして、結局最初に何となく書いた勝利数ソートを超えることはできずじまい。その間に、マラソン上位の常連のみなさんに抜かれて暫定17位で終了。ずっと一つ上にいたkuusoさんが提出ミスで順位下げてしまったようなので、実質18位かなと思います。

 

感想

どちらにしろシステスでもこのまま行ければ過去最高順位なのですが、とりあえず書いた解法が奇跡的に刺さっただけで実力を伴ってないので、うーん、喜んでいいのか微妙な気持ち。ま、とりあえずtourist君には勝てそうです。touristに勝ってみたい人はMMをやろう(?)

あとAHC003でもやったエスケープシーケンスを使ったビジュアライズを今回もやって楽しかったです。やってることは文字出力なのでCtrl-Sで一時停止できたり、スマホ上のC++コンパイラでも動かせたりするので、問題にもよるけど今後もやりたいです。スマホでいつでもどこでもマラソンが出来ると生活崩壊に拍車がかかりそうですが。

 

今回、順位は自分的には良さそうですがマラソンらしい探索は書けてないので、次回は、いや、いずれは「ぼくがかんがえたさいきょうのどんよく」じゃないプログラムを書きたいです。おわり。

 

(6月29日追記)

MM127 kuusoさんが17位に戻ってきて18位で確定のよう。そもそも勝ててなかったので、提出時間はまあいいんじゃないかな。
そして、12日に提出したきり放置のtouristに勝ちました!(嬉しいか? 


f:id:mooaki:20210629073928j:image