mooakiのブログ

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

HTTF2024(AHC027)メモ

Seed=0


HTTF2024(AHC027)に参加したメモみたいな日記みたいな記事です。コンテストは12/1からだったんですが12/2までは仕事の合間に問題見たりダウンロードしたりしたくらいで取り組んだのは12/3からということでそこから。

 

12/3

貴重な1日休みなので、朝遅めに起きてスプラやって玄関に飾るクリスマスリースを初めて手作りして裏庭の枝が伸びすぎたクルミや松の枝刈りをして午前が終わった。昼食べてよーしAHCやるぞー、その前に買い出しってことでコンビニ行ってあれこれ買って今度こそAHCやるぞーってパソコンに向かうも、なんか眠くて頭働かないのでちょっと昼寝して、で、起きて甘いものとか食べながらポチポチやってたらようやくエンジンかかってきた(午後4時)。まず入力もらう。グリッドのセルとセルの間の壁が与えられるやつ。前回ようやく気付いたんだけど、これは移動できるマス同士を繋ぐグラフで持てば良いよね。出力はUDLRの羅列なので特に問題なく。で、とりあえず正のスコア取れる解を作るには全部のマスを回ってスタート地点に戻って来なきゃいけなくて、どうすればいいの?とサンプルコードを見る。DFSか。普段ヒューリスティックでは最短ルートを知りたいことが殆どだからBFSばかり書いてるけど、まぁキューをスタックにすれば良いのだし。とPythonのコードを見ながらDFS書き始めたんだけど数行で「行って帰って来るって面倒くさそうだし、その後そこから改善していける気がしないな」と思ってやめて自分なりにAC取る方法を考える。近い未踏のセルに移動していって最後(0,0)に戻ればいいのでは?じゃあやっぱりBFSだな。BFSは全てを解決する。とばかりにBFS解を書いて見る。実行するとツラツラと塗りつぶして行って無事AC。でもサンプル解よりいいのか悪いのか分からないなということでサンプルコードをchatGPTにC++に翻訳してもらって実行。何の問題もなく一発で動くのね、すげーな。で比較するとBFS解の方が良さそう。よし投げるか。第一投にしてはまぁまぁ。ビジュアライザ見ていて、雑にマンハッタン距離の近い未踏のセルに移動してたのが壁越しに行ったり来たりして無駄に見えたので、ちゃんとBFSで最寄りの未踏セルに移動するようにしたら若干改善したので第二投。

12/4

ビジュアライザを見てるとやっぱり汚れやすいところは何回か行かないとダメそうなので(ビジュアライザ見なくてもそう)汚れ度の高いところをある程度回ってから未踏セルを巡回してみる。逆に一度全部回ってから汚れてるところを回ってみる。汚れてるところ回って全面清掃してまた汚れてるところを回る。などなど試してみて2番目のが良さげだったので提出。31G乗って180位。おお。思ったより良かった。

12/5

スコア計算がきちんと出来てなかったけど、この後焼きなましやビームサーチは出来なくても山登り、いやせめて乱択はしたいので、スコア計算をデバッグ。printfで内部の計算途中の値をドバっと出して見て修正していったら公式のテスター(vis)と一の位までピタリと合うようになって気持ち良い。

12/6

汚れるとこから汚れるとこへの移動の合間に未踏セルを経由するとどう?と実験してみたけど改悪に終わる。

12/7

小手先の変更ではやはりダメそう。未踏セルをある程度回ったら汚れるとこを掃除、を繰り返すようにしてみるか。ある程度ってどの程度?与えられたデータから計算できる?まずはn分割を一通り試してみるか。で、1から20分割まで試して1番良いのを出力するのを提出。4TLE。時間管理しないとだめかー。でもふと順位表見ると33Gに伸びてる。TLEあってもそれ以外の点数は有効なんだっけ。高速化もちょっと想うところあるけれどとりあえずは1800msで打ち切りに直して、でも4TLE直してもさほど変わらないかーと思いつつ提出。おお35G乗った。提出結果を見たらまだ1TLE。1700msにして再度提出。ぬ?36Gで167位?!1TLE馬鹿にならないな。

12/8

セル間の距離を知りたいときいちいちBFSしてたんだけど、今回はマップは固定なので初めに全セル間の距離を求めておいて使い回す高速化。デバグ用のグリッド表示。ルートを探すとき、未踏セルを優先。などをした。

12/9

この日も1日休み!でも12月の貴重な休みなので、午前は床屋、午後は花壇整理したり庭の勝手に生えた木切ったり玄関脇のなんちゃって枯山水整たりしてたら午後4時。休日まるまるAHCに注ぎ込んで進捗なかったりしたらかなり後悔しそうなので、やることやって残りの時間でやるくらいがいいかなーみたいな弱腰な姿勢。で、ビジュアライザ見るとルートがくるくるしたり行ったり来たりしてるので、汚れるセルで囲まれたセルも汚れるセルの仲間にしてある程度塊にしてやったりとか、汚れないセル回ってるときにもう少し残ってるってとこで汚れるセルの掃除に行っちゃうので汚れないセル掃除の個数をランダムに増減して一番良いのを出力する乱択にするとかしてジワジワと改善。39Gで150位でこの日は終了。

12/10

最終日だけど仕事あるのでちょこっと思いつきを実験して改悪に終わってほぼおしまい。牛舎で順位表やX見て「上位争いアツいな~」と思ってたら初提出でいきなり1位の人が現れてビックリ。すげー!自分はというと1700msで打ち切ってた乱択を1900msまで伸ばして再提出したんだけど、終了13分前に「攻めすぎかな」と思って牛舎からスマホで1850msに直したやつを再々提出して終了。結局山登りもせず貪欲と乱択で終わり。暫定で180位38G。

結果&感想

システスでTLEが10個以上あったようで180位から201位まで落ちてしまいました。間に合ってるのはほぼ1800ms台でTLEは2200ms超えなので、最後に50ms加減したのはあまり関係なかったのかも。でも青パフォが取れて良かったです。

今回とにかくビジュアライザが高機能で楽しかったし助かりました。ありがとうございます。あとwataさんの解説もいつもだけど簡単な自明解から初めてステップアップしていって「そんなスコアが?!」みたいな驚きもあってすごいなぁと思います。途中の上位の抜きつ抜かれつや最終日に初提出の方が優勝をかっさらっていった展開も下から眺めていてアツかったです。ほんと楽しいコンテストでした。12日からのMMも貪欲頑張ります(たまには焼けよ)(いや無理)。

 

 

AHC017参加記

久しぶりに書くか

こんにちは。AHC017に参加したので参加記を書こうと思うのですが、滅多に書かないので参加記のフォーマットが自分の中で定まってなくて困ってます。とりあえず他の方と違うアイキャッチ貼っとくか(は?)。

手作りグラフ

これは与えられるグラフが大きすぎるのでデバッグ用に手作りしたグラフで、実は問題の要件を満たしてない(2-辺連結ではない)のだけど、でも結構役立ちました。

成績は

316位でした。今回の目標はヒューリスティックのレートがなので青パフォを目指していたのですが 1459 ということで水パフォ止まりでした。次は頑張りたいですが、 AHC018 は MM144 と日程が重なるので、うーん。

解法は

最終的な解法としては

  • BFS的にグラフをたどってmodで工事日を割り振る(ばらけさせたかったので)

  • 各日のUnionFindのグループ数を最小化するように山登りして不連続点をなくす

  • 2辺スワップで山登り(スコア計算が遅いので数十~百数十くらいしか回ってない)

という感じでした。これだとTwitterに書いたのと同じなのでもうちょっと説明します。

BFS的にグラフをたどってmodで工事日を割り振る

コンテストの最初から最後まで工事する辺はばらけている方がいいと思い込んでいたので、グラフをたどりながら1,2,3,4,5,1,2,3,4,5,1,2,...(D=5の場合)と工事日を割り振ります。まさか工事する辺が連結の方がいいとはね…。

各日のUnionFindのグループ数を最小化するように山登りして不連続点をなくす

「不連続点」というか、非連結だと109(かける非連結な頂点のペアの数)という重いペナがあって今回の相対スコアだとかなり低い点数になるので、まずは連結な解を作れるようにしようと思い、UnionFindでのグループ数が各日1で合計がD(工事日数)になるまで2辺スワップの山登りをしました。

これで提出一覧のスコアが下のスコアから上のスコアへグンと良くなって Twitter で他の方が言ってた「ようやくスタートライン」とはこれか?と思いました。

2辺スワップで山登り(スコア計算が遅いので数十~百数十くらいしか回ってない)

評価関数を軽くする方法が結局見つからないまま、残り時間でしないよりましくらいの山登りをしています。

試したあれこれ

自分はGitHubなどのバージョン管理ツールは使ってなくて、ある程度変更するたびにファイル名を変えて保存しているんですけど、今回は各ファイルのメモをファイルの先頭に書いていました。こんな感じ。

// p01.cpp
// mod割り当て
// 提出1

// p02.cpp
// スコア計算したい
// まずはべたに
// ワーシャルフロイド重すぎた

// p03.cpp
// スコア計算出来たっぽいけど重い
// (ダイクストラ)

// p04.cpp
// コードテストだと6から7倍はやい
// A*やりかけてあきらめた

// p05.cpp
// ダイクストラ・アゲイン
// 経路復元すっぞ

// p06.cpp
// スコア計算

// p07.cpp
// 構築頑張るか?

// p08.cpp
// バックトラック

// p09.cpp
// タイムアウト対策

// p10.cpp
// 乱択にした

// p11.cpp
// 偏角ソート

// p12.cpp
// unionfindで山登り

// p13.cpp
// unionfindで山登りの後、スコア差分で山登り

// p14.cpp
// ワーシャルフロイドとかダイクストラ高速化とか試したけどダメ

// p15.cpp
// p13.cpp からコピー
// 小手先の高速化

// p16.cpp
// お試し焼きなまし -> ぜんぜんだめじゃん?

// p17.cpp
// 遷移逆だったのなおした

// p18.cpp
// 焼きなましいじってみてもスコア上がらん

// p19.cpp
// mountain()の効率をちょこっとよくしたつもり

// p20.cpp
// ???

// p21.cpp
// 初期解を偏角ソートじゃなくてグラフ順(?)

もうちょっと詳しく書きますと...。

// p01.cpp
// mod割り当て

これは辺番号順に1,2,3,4,5,1,2,3,4,5,1,2,...(D=5の場合)と工事日を割り振った解で、とりあえず入出力がちゃんとできるか確認という感じで提出しました。同じスコアの方がたくさんいて「やっぱりねー」と思いました。

// p02.cpp
// スコア計算したい
// まずはべたに
// ワーシャルフロイド重すぎた

で「次はスコア計算!」と思い全頂点間の最短距離なのでワーシャルフロイドを試してみたんですけどさすがO(N3)、重すぎました。試さなくても計算量で気付けって話なんですけど、本当にこの人アルゴ緑なんですかね。

// p03.cpp
// スコア計算出来たっぽいけど重い
// (ダイクストラ)

で、全頂点からのダイクストラで真正直にスコア計算してみました。当然重い。

// p04.cpp
// コードテストだと6から7倍はやい
// A*やりかけてあきらめた

手元で5秒近くかかってて「山登れないじゃん!」と絶望してたのですが、コードテストで走らせたら800msくらいで「俺のパソコンおせぇ!!」となりました。どのみち大して山登りできないですが。

で「そういえばA*ってダイクストラより早いんだっけ?」と検索して書いていたんですが、A*はゴール地点が一点決まっているときに使うアルゴリズムで、今回のスコア計算では全頂点から全頂点へA*回さないといけないとなると、むしろ遅いのでは?となってやめちゃいました。書く前に気づけ、それはそう。

// p05.cpp
// ダイクストラ・アゲイン
// 経路復元すっぞ

やっぱり全頂点からダイクストラすることにして、経路復元すればそこから高速化できないかと思いました。具体的には最短経路はその途中の区間もそれぞれ最短経路になっているはずなのでその区間は計算済みとしてチェックしていけば、全頂点からダイクストラしないでもいいかも?とか試してみたんですけど、余計重くなってしまってやめました。

// p06.cpp
// スコア計算

これはスコア計算の間違ってた部分を直した、気がする。

// p07.cpp
// 構築頑張るか?

スコア計算が重いけど、多くの人が割と簡単にもっといいスコア出しているように見えて、これは初期解の構築に何かうまい手があるのかも?と思いました。

// p08.cpp
// バックトラック

それでバックトラック法でまずは連結な解を一つ作ってみたんですけど、頂点数多すぎて時間かかりすぎました。

// p09.cpp
// タイムアウト対策

で時間計測してバックトラック中断したりとか。

// p10.cpp
// 乱択にした

バックトラックで解の候補を順番に試すんじゃなく乱択してみたりとか。

// p11.cpp
// 偏角ソート

時間内にバックトラックで解が作れなければ、辺の中点の座標で偏角ソートしてmodで工事日を割り振ってみたりとか。

...と色々試してみたものの「これじゃないな」ということでバックトラックはここまでにしました。

// p12.cpp
// unionfindで山登り

で、まずは連結な解を作るために各日のUnionFindでのグループ数が各1になるように2辺スワップの山登り。ダイクストラでのスコア計算はまだ高速化出来てなかったので、より軽いUnionFindでとりあえず連結な初期解を作りました。これで大きくスコア改善して順位表でも22Gに乗りました。多くの人が20G超えてる中で自分はさっぱりスコア伸ばせず20G行けずに終わるのかなと思っていたので、本当にほっとして嬉しかったのを覚えています。

// p13.cpp
// unionfindで山登りの後、スコア差分で山登り

で、残ってる時間で2辺スワップした2日分のスコアだけ計算して山登り。

// p14.cpp
// ワーシャルフロイドとかダイクストラ高速化とか試したけどダメ

やっぱりスコア計算が重いので捨てたはずのワーシャルフロイドまたやってみたり。本当にこの人アルゴ緑なんですかね(2回目)。そのほかもいじってみたけど、さっぱりでした。

// p15.cpp
// p13.cpp からコピー
// 小手先の高速化

でp14.cppは捨てちゃって、検索して出てきた定数倍高速化を試してみたり。

// p16.cpp
// お試し焼きなまし -> ぜんぜんだめじゃん?

試行回数が全然足りないのに焼きなましにしてみたり。

// p17.cpp
// 遷移逆だったのなおした

よく見たら焼きなましが最大化する遷移になってたのでなおしてみたり。

// p18.cpp
// 焼きなましいじってみてもスコア上がらん

温度とかいじってみたり。でもそもそもの試行回数が足りないのでダメでした。

// p19.cpp
// mountain()の効率をちょこっとよくしたつもり

焼きなましはあきらめて、山登りで都度グラフをコピーしてた部分をコピー回数減らしてみたり。

// p20.cpp
// ???

ここはメモるのを忘れていた部分。

// p21.cpp
// 初期解を偏角ソートじゃなくてグラフ順(?)

初期解を偏角ソートじゃなくてBFSでたどった辺の順にしてみたりして、終了。

結局、スコア計算を高速化できずにもがいていた一週間でした。いや、途中で全頂点からのダイクストラじゃなくてもいいのでは?と雑にN/2頂点にしてみたりとかしたんだけど、スコア悪くなったので「やっぱり全頂点からの正確なスコアじゃないとちゃんと山登りできないか~」とすぐやめちゃいました。雑に試して捨てちゃうの、良くないなぁとも思うんだけど、ハズレ方針にいつまでも時間を掛けちゃうのも怖いし、悩ましいです。

おわりに

終わってみれば「スコア計算を高速化して山登りor焼きなまし」っていうある意味オーソドックスな問題で、AHCの中でももっと初めの方で出してても良かったんじゃないかなとも思いました。自分としては特に個性的な解法も思いつけず、よくやるテキストでのビジュアライズとか、それをTシャツにしたりとかしておちゃらけたりも出来ず、なんともパッとしない回だった印象ですが、今回の試行錯誤が今後のAHCやMMに生かせればと思います。とりあえず計算量くらいは実装しなくても判断できるようになれよと。はい。

AHC014でとりあえず貪欲法を書くまでの話

経緯

AHC014 が終わった翌日、地域の焼肉イベントが感染対策に配慮しつつ行われまして、そこで近所に先日出来たばかりのクラフトビール工場のビールも振舞われまして、要するに酔ってたんですね。

こんなことをつぶやいてしまったら「じゃあお前はどうやってんだ」って、まぁ、なりますね。あーあ。

AHC014では 111位、TopCoderMarathon Match も参加してますが順位表の真ん中へんをうろうろし続けてるだけで、決してヒューリスティック/マラソンが強い訳ではないので自分のやり方をマネして強くなれる保証は一切ないのですが、晒してみれば「そこは無駄だろ」とか「自分のこの実装の方が良い」とかの見識の呼び水になるやもしれんと自分に言い聞かせて、AHC014を題材にとりあえず貪欲までを書いてみることにします。言語は競プロで使える言語界の絶対王者 C++です。クラスや変数の命名規則がメチャクチャですがご容赦ください。

プログラムの下準備

これは自分もまだ試行錯誤中ですが、Solverクラスのsolve()関数に実際の解法を書くようにして main() からそれを呼び出してます。

Solver クラス

class Solver
{
    public:

    Solver() {};

    void init() {
        cin >> N;
        cin >> M;

        nei8rc = vector<vector<int>>(N * N, vector<int>(8));
        // 8近傍事前計算
        rep(r, N) {
            rep(c, N) {
                rep(dir, 8) {
                    int r0 = r + DR8[dir];
                    int c0 = c + DC8[dir];
                    if(inside(r0, c0)) { // グリッドの内側か判定するマクロ
                        nei8rc[RC(r, c)][dir] = RC(r0, c0);
                    } else {
                        nei8rc[RC(r, c)][dir] = OUTSIDE;
                    }
                }
            }
        }
    }

    void solve() {
        srand(time(NULL));
        init();
        STATE state;
        state.input();
        state.init();
        state.make_answer();
        state.output();
    }
};

「8近傍事前計算」というのは bowwowforeachさんの

というアイデアを拝借したものです。ありがとうございます。これを使うとp1からdir方向にあるp2まで辺を張る関数は

    void draw1(int p1, int p2, int dir) {
        for(int p = p1; p != p2; p = nei8rc[p][dir]) {
            set_con(p, dir); // 点pからdir方向に辺を張る
        }
    }

みたいに書けます。dir方向にp2がないとバグりますが、p1からdir方向にある印がp2のはずなのでチェックは省略してます。

STATE クラス

また、現在の状態を表すものは STATE クラスにまとめておきます。AHC014 で言うとグリッドの印の有無、辺の有無、その時点での解、スコアなどです。

class STATE {
    public:
    Grid g;
    vector<Answer> ans;
    int score;
    set<int> points;
    vector<vector<int>> near_point;
   // 以下略
};

Grid クラスはそのまんまグリッドのクラスです。Marathon Match ではグリッドの問題が多いので基本的なのをテンプレファイルに書いて使いまわしてます(詳しくは後述)。Answer クラスは一回分の解を持つクラス(今回だと p1,p2,p3,p4)で、そのvectorとして一連の解を保持します。points はその時点で探索する点で、最初は読み込んだ点をすべて追加して、印をつけるたびに追加したり、もう四角を作るのに使えなくなった点は除外したりします除外はするつもりだけでしてませんでした(^^;。near_point は各印の8方向の最寄の印です。これも初期化時に求めておいて、新しい印をつけるたびにその8方向上の点についてだけ更新します。こうすることで各印からの8方向の印をいちいちグリッド上で探す必要がなくなります。

Grid クラス

class Grid
{
    public:
    int N;
    vector<int> grid;
    Grid() {}
    Grid(int n) {
        N = n;
        grid.resize(n * n);
    }
    // 略
    int& operator[](int i) {
        return grid[i];
    }
};

grid は各点の印の有無と8方向の辺を int の各ビットに対応させて1次元ベクターで保持しています。

#define DIR_R  0x0001
#define DIR_RD 0x0002
#define DIR_D  0x0004
#define DIR_LD 0x0008
#define DIR_L  0x0010
#define DIR_LU 0x0020
#define DIR_U  0x0040
#define DIR_RU 0x0080
#define MARK   0x0100

と各ビットを定義しておいて

    // 点rcからdir方向に辺を張る
    void set_con(int rc, int dir)   // setConnect にするべきでは?
    {
        int nrc = nei8rc[rc][dir];
        int rdir = (dir + 4) % 8;
        assert(nrc != OUTSIDE);        
        grid[rc] |= (1 << dir);
        grid[nrc] |= (1 << rdir);
    }
 
    // 点rcのdir方向の辺の有無
    bool isConnected(int rc, int dir)
    {
        return (grid[rc] & (1 << dir)) != 0;
    }
 
    // 印をつける
    void setMark(int rc)
    {
        grid[rc] |= MARK;
    }
 
    // 印の有無
    bool isMarked(int rc)
    {
        return (grid[rc] & MARK) != 0;
    }

といった関数でアクセスします。余談ですが、こういう変数名や関数名で毎度悩んだあげく微妙な命名をしてしまって本当に恥ずかしいのですが、提供されているビジュアライザのソースを参考にすればいいのかもしれないと今回のコンテスト中に思いつきました。次回からそうしてみようと思います。

また[]演算子をオーバーライドすることで

    Grid g(N);  // N*N のグリッド
    g[x * N + y] = 0;
    //g.grid[x * N + y] = 0;

の様に書けます。実際は[]の中が毎回書くのは面倒だしたまにバグらせるので

#define RC(r, c) ((r) * N + (c))
#define R(rc) (rc / N)
#define C(rc) (rc % N)

とマクロ定義することでg[RC(x, y)] = 0と書けるようにしています。Gridクラス自体の配列を作ったら不具合ある気がしますが、今のところそれをしたことはないので、とりあえずOKです(は?)。

下準備はこんなところですかね。

貪欲法で解を作る

下準備ができたので、いよいよ何かしら解を作って出力します。まず作れる四角をリストアップし、その中から1つを出力するのを繰り返すことにします。

たまたま解説放送と同じだったのですが、各印をp3としてdir方向にある点をp2、dir方向から90°回転した方向をdir4、dir4方向にある印をp4としてp1を求め、辺を共有してないか、途中に印がないかなど確認する関数canMakeRect()を書きます。

    // 出来ないなら -1、できるならp1
    int canMakeRect(int p3, int dir) {
        int p2 = near_point[p3][dir];
        int dir4 = (dir + 2) % 8;
        int p4 = near_point[p3][dir4];
        if(g.isConnected(p3, dir)) return -1;  // p2方向にすでに辺がある
        if(g.isConnected(p3, dir4)) return -1; // p4方向にすでに辺がある
        if(p2 == OUTSIDE || p4 == OUTSIDE) return -1; //p2,p4方向に印がない
        if(g.isConnected(p2, dir4) || g.isConnected(p4, dir)) return -1; // p2からp1方向またはp4からp1方向に辺がある
        int p1x = R(p4) + R(p2) - R(p3);
        int p1y = C(p4) + C(p2) - C(p3);
        int p1 = RC(p1x, p1y);
        if(g.isUsed(p2, p1, dir4)) return -1; // p2,p1間に印がある
        if(g.isUsed(p4, p1, dir)) return -1;  // p4,p1間に印がある
        if(g.isMarked(p1)) return -1; // p1に印がある
        return p1;
    }

これを使える印それぞれに8方向で調べ、対角のマンハッタン距離が一番小さいものを解の一つとします。

    int  make_answer1()
    {
        //          dist,     p3 , dir
        vector<pair<int, pair<int, int>>> candi; // 候補を入れる
        for(auto p3 : points) {
            rep(dir, 8) {
                int p1 = canMakeRect(p3, dir);
                if(p1 >= 0) {
                    int dist = abs(R(p1) -R(p3)) + abs(C(p1) - C(p3));
                    candi.push_back({dist,{p3, dir}});
                }
            }
        }
        if(candi.size() > 0) {
            sort(candi.begin(), candi.end());
            int idx = 0;
            draw(candi[idx].second);
            return candi[idx].second.first;
        }
        return -1;
    }

これを候補がなくなるまで(-1が返ってくるまで)繰り返します。

    void make_answer()
    {
        int res;
        do {
            res = make_answer1();
        } while(res >= 0);
    }

これで Seed=0 では629389点。 提出すると 32629578 点になります。とりあえず貪欲法できました。

まとめ

コンテスト中に「縦横の四角が作れるようになったので次は斜めを実装」というツイートを見た気がするのですが、四角の向きごとに判定するルーチンを書くとコード量もバグを埋め込む可能性も増え、デバッグに費やす時間も増えがちです。今回やったように点と向きで縦横も斜めも同じく判定できるようにすればコード量もデバッグ時間も減らせ、より高度な解法に取り組む時間が増やせるかもしれません。同じようなコードを何度も書いているのに気付いたら「これは一般化できないか?」と考えてみるといいかも知れません。怠惰はプログラマの三大美徳の一つですしね。

今回のコードの改良の先に順位表1ページ目があるかは自分の実力ではわかりませんし、次の AHC でそのまま使えるということもないとは思いますが、何か一つでもヒントになったり、話題の呼び水になれば幸いです。不慣れで分かりずらい記事になってしまったと思いますが読んでいただきありがとうございました。

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

これは何?

ラソン系のプログラミングコンテスト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などアルゴの知識が生かせて面白かったです。あと、日本、層厚すぎ。