simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

競技プログラミング獲得賞金(2023年)

一覧

コンテスト名 順位 金額 備考
Hitachi Hokudai Lab. & Hokkaido University Contest 2022 B問題 2位 100,000円
トヨタ自動車 実課題プログラミングコンテスト 2023 Spring 5位 10,000円
MC Digital プログラミングコンテスト2023 4位 30,000円 賞金対象外者が 1名いたので繰り上げ
HACK TO THE FUTURE 2024 5位 40,000円 賞金対象外者が 1名いたので繰り上げ
Marathon Match 142 1位 75$
Marathon Match 150 2位 125$
TCOファイナル旅費 - 650$ TCO Final が中止になった代わりに得られた
ICPC 2023 Online Challenge powered by Huawei 46位 800€ 本当に貰えるかはまだわからず

合計 180,000円 + 850$ + 800€

Marathon Match 150 QueenAttack Postmortem

Problem

www.topcoder.com

Last submission

MM150 last submission · GitHub

Strategy

The following process is repeated at high speed and the one with the best score is adopted.

  • By using SA method to obtain an arrangement in which the queens do not collision with each other as much as possible.
  • Assign queen locations using min-cost flow for the obtained placement
  • Move to the assigned placement using the Dijkstra method.

Obtain an arrangement

The first step is to search for a queen arrangement by SA. A neighboring state is as follows

  • Choose the highest number of collisions with other queens among some queens and move to the place with the lowest number of collisions with other queens among some empty spaces.

After the operation, the score is evaluated to determine whether the new state is adopted. This process is repeated until the time limit is exceeded or there are no more collisions between queens (Errors == 0).

Faster collision detection.

To speed up the determination of whether queens are in collision with each other, the range of influence of queens is counted and its value is checked to speed up the collision determination.

This information has for each color, and the number of values written indicates the number of collisions with other queens.

Assign position

For the arrangement obtained, which queens move to which position is determined using the min cost flow. As a cost, the raw score is used as the basis for the extra costs incurred when passing queens.

Move it to the assigned position

Once the allocation is complete, move the queen to that position using the Dijkstra method. Treat other queens as immobile when moving. The queens that can be moved to the destination are moved with the lowest cost and the process is repeated until there are no more queens left to move.

Randomly change the order in which they are moved.

If the queens are moved in order of decreasing cost, the order of the queens to be moved is fixed, but by adding a random value to the cost, the order of movement is not fixed. This process of moving the queens is executed several times and the one with the lowest cost is adopted.

Summary

When I saw it as a problem, I thought that bowwow's solution of AHC013 might work, but it looked like it would be troublesome to implement, so I went through with it and implemented it as it was using the strategy I thought of. The N-queen problem itself could be solved fairly fast, but in the end I couldn't manage the extra diversions and extra cost if I made the operation based on the assumption that I didn't move other queens when I moved them.

Marathon Match 150 QueenAttack 参加記

問題

www.topcoder.com

コード

MM150 last submission · GitHub

戦略

以下の処理を高速に繰り返して一番スコアが良くなるものを採用します。

  • なるべくクイーン同士が取り合わないような配置を焼きなまし法で求める
  • 求めた配置に対して最小費用流を用いて位置の割当を行う
  • 割り当てた配置にダイクストラ法を用いて移動させる

クイーンの配置を焼きなまし法で求める

まず最初に焼きなまし法によってクイーンの配置を探索します。近傍としては以下の 1つです

  • 任意のクイーンの中から一番他のクイーンと取り合っている数が多いものを選択して、任意の空白地点の中から一番他のクイーンと取り合う数が少ない場所に移動する

操作後にスコアを評価して近傍を採用するかどうかを判断します。制限時間を超えるかクイーン同士の衝突がなくなるまで (Errors == 0) この処理を繰り返していきます。

衝突判定の高速化

クイーン同士が衝突しているかどうかの判定を高速化するためにクイーンの影響範囲をカウントしてその値をチェックすることで衝突判定の高速化を行いました。

この情報は各色毎に持たせており、書かれた値の数だけ他のクイーンと衝突していることを表しています。

最小費用流を用いて位置を割り当てる

求めた盤面に対して、どのクイーンがどの位置に移動するのかを最小費用流を用いて求めます。コストとしては生スコアを基本としてクイーンを通過するときに余計なコストが発生するようにしました。

割り当てた位置に移動させる

割当が完了したらその位置にダイクストラ法を使用してクイーンを移動させます。移動の際には他のクイーンを動かせないものとして処理します。移動できるクイーンの中からコストが一番小さいものを移動させていき最終的に移動できるクイーンが無くなるまで繰り返します。

移動させる順番をランダムに変える

コストが小さい順に移動させると移動させるクイーンの順番が固定されますが、コストにランダムな値を追加することで移動の順番が固定化されないようにしました。この移動させる処理を複数回行って一番コストが小さくなるものを採用しています。

感想

問題と見たときに AHC013bowwow さんの解法が有効かなと思ったけど実装が面倒そうなのでスルーして自分の考えた方針でそのまま実装した。Nクイーン問題自体はかなり高速で解けたけど結局移動させるときに他のクイーンを動かさない前提の操作にすると余計な遠回りをしてコストが余分にかかってしまうのをどうにも出来なかった。

AHC027 Recurring Cleaning Route 参加記

問題

A - Recurring Cleaning Route

戦略

ビームサーチパートは 500msec (テストケースによってはもっと速く終わる)、焼きなましパートは 1500msec 使用しています。

ビームサーチによる初期解生成

最初にビームサーチによる初期解の作成を行います。全てのマスを通りかつ初期位置に戻る経路を 1度の探索で求めるのは難しいので複数回に分けて探索を行いました。 具体的には以下のパートで構成されています

  • 通常探索
  • 未到達領域を埋める処理
  • 初期位置に戻る経路探索

具体的には通常探索を複数回行った後に未到達領域を埋める処理を行って最後に初期位置に戻る経路を追加する感じになります。

通常探索

通常探索ではスコアを保ちつつ未到達領域の数を減らすような経路を探索します。スコアを評価関数にすると汚れにくいマスを探索してくれないので 到達済みのセルの数 を基本的な評価値にしました。また未到達領域の d の値については底上げを行って探索が行われやすくするようにして到達後は元の値に戻します。(今回は未到達のセルの d の値を +25 しています)

通常探索では 1回の探索で数百程度の長さの経路を作成して、未到達領域のセルの数が一定の数になるまでは経路探索を続けます。

評価項目

通常探索における主な評価項目は以下の通りです

一度探索したセルをなるべく探索しないようにする

行って戻ってだったり、一度探索した箇所に再度訪れるみたいな行動は禁止しています。ただ行き止まりの通路から戻るときや周りに壁がある場合はその限りではありません。

残りの未到達領域の数

通常探索で一番重要視している項目です。初期解パートではなるべく短い経路にしたいのでこの数が最終的な経路長にかなり直接的に関わってきます。ただし、経路長を重要視してしまうとスコアが悪化するのでそのあたりのバランスを取る必要があります。

生スコア

現時点で存在している汚れの総和と今までの汚れの総和の 2つを評価しています。残りの未到達領域の数 よりは低めに評価しています。

未到達領域を埋める

複数回通常探索を行うと図のようなほとんど探索したけどいくつか未到達領域が残っている状態になります。

この状態から通常探索だけで全ての未到達領域を埋めようとするとかなりの経路長が必要になってしまうので別の方法で未到達領域を埋めていきます。

未到達領域に隣接している到達済みのセルが存在している場合 到達済みのセル -> 未到達領域のセル -> 到達済みのセル の経路を追加することで未到達領域のセルを消すことが出来ます。(元の経路から枝が生えたような感じになるので自分は 枝パス と読んでました)

この処理を未到達領域がなくなるまで繰り返します。この処理のメリットとしては全体的なスコアをあまり落とさず未到達領域を消せるというところです。 この後の焼きなましパートでスコア計算を差分ではなくフルで行っているので同じぐらいのスコアであればなるべく経路長を短くしたいためこのような処理を行っています。(経路長 10000, スコア 2000 と 経路長 5000, スコア 2200 なら後者のほうが望ましい)

ビームサーチパートより焼きなましパートのほうが圧倒的にスコアが改善されるのでその試行回数を稼ぐ意味でもなるべく経路長は短くしたいです。

初期位置に戻る

全ての領域の探索が終わったら初期位置に戻る経路を作成します。特にこれといった処理は無いですが最短距離でなるべくスコアが良くなるような経路を探索しています。

初期解を複数作成して一番良いものを選ぶ

N が小さく時間に余裕があるケースについては複数回初期解を作成してその中で一番スコアが良いものを選びます。

焼きなまし法による経路改善

焼きなましパートでは経路の一部を削除 & 作り直しを繰り返していきます。

経路の作り直し

経路の一部からランダムな長さ (2 ~ 8) を削除して再度経路を作り直します。

作り直す経路についてはものすごい小さなビーム幅のビームサーチで探索を行います。(今回だとビーム幅 3)

経路の制約

作り直す経路にはいくつか制約を設けています。

最大経路長

作り直す際の最大の経路長として 削除した経路の長さ + [2, 4, 6] から選ばれたランダムな値 を設定します。全部偶数なのは偶奇性の特徴から奇数を設定しても意味ないからです。この長さを超えるような経路を作成しようとした場合はその時点で切られます。

同じマスをなるべく踏まないようにする

ここは通常探索と同じく「行って戻って」だったり「ぐるぐる回って同じマスを踏む」のような行動を禁止しています。

削除した経路と同じ経路を作成しない

削除前と状態が変わらないので拒否します。

短い間隔でマスを踏まないようにする

図のような時刻 7 - 10 時点の経路を削除して時刻 6 の位置から時刻 11の位置への経路を探索することを考えます。

例として以下の図のように探索中に時刻 19の時点のマスに到達したとします。このときの間隔は 19 - 9 = 10 となり、この時間間隔が短すぎる場合はその経路を切り捨てます。

このようにすることで作り直した経路のスコアが悪化しにくくなるようにしています。

全てのセルの到達状態を維持する

経路を削除した際に未到達のセルが発生した場合はそのセルを通過しない経路を無効としています。

評価項目

作り直す経路の評価としては以下のようになります。

  • 削除した汚れの総和

高速化のために評価はシンプルにしていて、これだけだと毎回似たような経路が作られるので乱数で適当な値を追加しています。

制約を緩めて再実行

上記の制約で新たな経路が見つからなかった場合(壁の影響で経路が作れないときがある)、制約を緩めて再度実行を行います。この際には重複マス排除やマスの到達間隔のチェックなどは行われません。

評価

作り直した結果を計算して評価します。スコアは生スコアそのままを使用しています。

感想

初期解作成 -> 焼きなましで改善というパターンで初期解の作成がかなり難しい問題。枝パスの存在を見つけてからは初期解作成の時間を短く出来たので焼きなましパートの時間を増やすことが出来たけど、スコアの差分計算が出来なくてこの部分にかなりの時間を取られてしまった。1位とはかなり点差があるので何か見落としているのは確実だけど結局最後までわからないまま。ヒューコンの最終日に何も出来なのは本当に良くないんだけど何が悪いと言われたら自分が悪いとしか言えないので精進するしかない。

掃除ロボット高橋くん

AHC026 Stack of Boxes 参加記

問題

atcoder.jp

コンテスト中ずっとバグ修正してたので参加してたかと言われると怪しい

戦略

基本的な部分は上位の人達と一緒です

  • 任意の山を 1つ選択する
  • 選択した山からすべての箱を取り除く
  • 空になった山に昇順になるように箱を置き直す

山が全て昇順になった状態であれば任意の山から常に最小の箱を選択することが可能となり実質ゲーム終了となります。

勝利盤面

自分は今回ビームサーチで選択した山から「どれだけ取得するか」「どこに配置するのか」を求めました。昇順に置き直す部分は貪欲法で実装しています。

任意の山を選択

まず最初にどこの山を選択するのかについてですが「まだ運び出されていない箱の中で最小の ID を含む山」を選択するようにしています。理由としては主に 2つあります。

  • 確実に最小の箱を盤面から運び出すことが出来る
  • 運び出す際に必ず最小の箱を運び出す操作が出来るので箱を空にする操作のコストが実質的に減る

時間があれば選ぶランダムに選択することも可能だとは思いますが、今回の実装だとそんなに多く回せなかったので貪欲に山を選択しています。

選択した山からすべての箱を取り除く

ソートまでの流れとしては主に以下の通りになります。

  • 山から箱を取り出して空にする
  • 箱を他の山に積む
  • 空の山に箱がソートするように移動させる

これらを行いつつなるべくコストを抑えるように工夫します。

山の取り出し

山を空にした後に他の山の状態がどうなっていると嬉しいかについて考えます。理想的には「他の山の箱が降順で並べられている」のが好ましいです。(この状態であれば空いた山に昇順ですべての箱を並べることが出来るため)

ソート時の様子

実際にはこのような盤面になることはありませんが、基本的な方針としては「他の山の頂点からなるべく降順で箱が並ぶようにする」となります。 そのため、ビームサーチにおける手の選択としては「箱を◯◯個取り出す」を実行する際に取り出した箱の列が降順を維持しているかどうかをチェックしています。ただ、これだけだと手の選択が狭いので確率で昇順になっていても取り出せるようにしています(ただし箱の ID の差が大きいとダメ)

箱を選択した後は任意の山の上に置きます。

山の状態の評価

今回のビームサーチの評価関数として「現在の状態でソートを行ったときに出来上がる山の高さとコスト」を利用しました。ソートを行う部分については後のほうで説明します。 この評価値を使うことでソート後に出来上がる山が「高さ」「コスト」のバランスが良いものとなります。(実際には高さとコストのバランスのチューニングが難しかったので色々重みを変えながら実行しています。)

実際の評価関数は以下のようになっています。(x, y, z はそれぞれの重み)

x * 山の高さ - y * 山を取り出す時のコスト - z * ソートする時のコスト

ソート時の処理

以下の操作が出来なくなるまで繰り返し実行します。

  • ソート済みの山と移動先の山を除く山に対して一番上の箱の ID が一番大きいものを選択する
    • 既に置かれている箱の ID より大きいものは選択されない
  • 選択した箱をソート対象の山に移動させる。この際選択した箱より下の箱も一緒に移動できる場合は移動させる。

実際の実装では運び出せる箱が存在する場合は必ず運び出すようにしていますが(今回の例だと 1 と 2)、説明のために省略しています。

時間制限いっぱい繰り返す

1回の処理で大体数百 msec ぐらいかかりますが、これを複数回繰り返して一番スコアが良いものを選択します。実行するごとに評価関数で使っている重みを変更しています。

Score = 9516 (seed = 0)

感想

評価関数をずっと考えていたが特に良いものが思いつかなかった。各山に置くときになるべく降順を維持するほうが良いのは確かだが移動時のコストを考えると昇順になっていたほうが嬉しい場面も存在しており、そこを評価するのが難しかったので実際にソートしてみてその結果をそのまま評価値に使うと良くなった。もっと良い評価値が見つかればスコアが伸びると思う。

コンテスト後にゆっくり実装しても普通にバグらせてたので短期で実装し切るのは流石に無理があった。評価関数さえ良ければ良いスコアが出るという点ではまだ戦えるほうのコンテストだと思ったけど「箱の移動」「箱の取り出し」の処理を無限にバグらせていたので仕方ない。

AHC025 Balancing by Balance 参加記

問題

A - Balancing by Balance

戦略

パラメータによって「ソートを行う」「ソートを行わない」の2パターンに分ける。ソートを行う場合はマージソートを使ってアイテムのソートを行う。箱ごとの比較を行い最も重い箱の重量と最も軽い箱の重量の差分が小さくなるように更新を行っていく。

初期解生成

アイテムのソートを実行したかどうかで初期解の生成も変える

ソートを行わない場合

ソートを行わない場合の初期解の生成ではまず最初に N個のアイテムを均等に箱に入れて、その後に箱のソートを行う。

ソートを行う場合

アイテムがソートされている場合はまず大きい順から D個取り出して箱に 1つずつ入れていき、その後は総重量が一番小さい箱を選択して新しくアイテムを追加、再度並べ直して総重量が小さい箱を選択 -> アイテム追加の処理をアイテムがなくなるまで続ける。追加するアイテムは後半に大きな変化が生じないように重量の大きい順に追加していく。

並べ直すときは 2分探索で挿入する位置を求める。

アイテムの入れ替え

初期解作成後は箱の中のアイテムの入れ替えをクエリーが実行できなくなる or 更新が行われなくなるまで実行する。操作としては以下の 3つ

  • 最も重い箱の中のアイテムを取り出し一番軽い箱の中に追加
  • 最も重い箱の中のアイテム 1つと一番軽い箱のアイテム 1つを入れ替え
  • 任意の箱のアイテム 1つと任意の箱のアイテム 1つを入れ替え

最も重い箱の中のアイテムを取り出し一番軽い箱の中に追加

一番重い箱の中からアイテムを 1つ取り出してそれを一番軽い箱の中に追加します。追加後、元の箱の一番重いものと新しく追加した箱の重量を比較して小さい場合は変更を採用します。(画像でいうと追加後の箱の重量が max のラインを超えてなければ採用する)

更新を行わないパターン (max のラインを超える)

max のラインを超えない = アイテムを取り出した箱も min を下回らない が確定するので 1回の比較で更新できるかどうかを判断することができる。

最も重い箱の中のアイテム 1つと一番軽い箱のアイテム 1つを入れ替え

最も重い箱のアイテムと最も軽い箱のアイテムの入れ替えを行います。交換する前の条件として 最軽量の箱から取り出すアイテムの重量 < 最重量の箱から取り出すアイテムの重量 をチェックする必要があります。(この条件を満たしていない場合は重量差が開くので)ソート済みの場合はこのチェックにクエリーを消費する必要がありません。

条件を満たしていない場合は重量差が開く

条件を満たしている場合は差分が縮まる。(重いアイテム - 軽いアイテム = X のアイテムを先端に移動させるというイメージ)

入れ替え後は最軽量の箱に追加した重量が max のラインを超えていないかどうかをチェックして超えてなければ採用します。

任意の箱のアイテム 1つと任意の箱のアイテム 1つを入れ替え

この操作は他の 2つの操作で更新が出来なくなった時に行います。交換する箱の位置が変わる以外は前の操作と一緒になります。

入れ替え後の操作

入れ替えが成功した後は再度ソートを行います。2分探索で挿入する箱の位置を探索してそこに挿入を行います。

再実行

山登りが終わってまだクエリーが実行できる場合はランダムにアイテムを入れ替えて再度更新を行います。ランダムに入れ替える際には必ず最軽量の箱か最重量の箱を含むようにします。(意図的に解を悪くして再度山登り)

再実行によって得られた結果が前の結果より良くなっているかどうかは 現在の最軽量の箱の重量 < 新しい最軽量の箱の重量 および 現在の最重量の箱の重量 > 新しい最重量の箱の重量 の両方が満たされているかどうかを確認します。 ( min max の差分が小さくなっているかどうかを確認と言っても良いです)

その他の改善

今まで説明した部分がスコアに大きく関与していて、後は細かい改善を重ねた。

二分探索の初期探索位置を指定

二分探索では最初は配列の中央から探索を行うが、特定の条件下では初期の探索位置の指定を行った。

初期解生成時

ソート済みのアイテムを箱に入れていく時に大きな箱から順に詰めていくため、最初は変動が大きくなるが後半は小さくなっていく傾向があるので初期の探索位置を最後に追加した位置から開始するようにした (1 - 2% 程度改善)

再ソート時

アイテムの操作を行って再度ソートを行う際に箱を 2つ挿入していくが 1つ目の箱の挿入位置によって 2つ目の初期探索位置を変えた。1つ目の挿入位置を pos1 とすると 2つ目の初期探索位置を D - pos1 + 1 に設定した。これは両者とも同じ値の増減が発生しているので pos1 の位置の反対部分に挿入されるだろうと予測した結果である。(2-3 %改善)

無駄な探索の排除

  • ソート済みの場合にあるアイテムの末尾から先頭への移動に失敗した場合に、それより重いアイテムの移動を行わないようにする。(100% 失敗するので)
  • 重さのオーダーが 10 と 20 のアイテムの交換に失敗した場合に 5 と 25 といった失敗したものより大きな差分が発生する交換を行わないようにする。

重さ推定

ソートしない場合でも事前チェックの際に一部のアイテム同士の比較は行うのでその結果からある程度の重さの推定を行った。と言ってもシンプルに 重いと判断された回数 - 軽いと判断された回数 というものである。最初は焼きなましでクエリーの結果と一致するように重さを変更するという操作を行っていたが判断材料が少ないのか全然安定して推定できなかったため諦めた。

最初にソート行うかどうかの判断

マージソートの比較回数 + 初期解生成時の比較回数 が Q を下回っているかどうかで判断。マージソートの比較回数については手元でサイズごとに数千回実行して一番比較回数が多いものを計測して配列で情報を持つようにしている、厳密に計算出来るけどなんか面倒なので諦めた。(どうせ数回程度しか変わらないと思ったので)

初期解生成中にクエリーがなくなってはダメだし、初期解生成後にまともにクエリー回数が残っていないのもダメなのでちょうどいい感じに調整するのが面倒だった。

感想

今回は絶対スコアでも相対スコアでもない順位スコアが採用されたコンテストだったので少し新鮮な気持ちで取り組んいでいた。ヒューリスティックでは点差から自分の方針がどれぐらいダメなのかを判断することができるが、それが出来ないのでとにかく良い解を作るしかなかった。提出したときにどれぐらい上位の点数が削れたかどうかで判断できないこともないけど難しいことには変わりない。

Q / N が低いケースだと十分な回数のアイテム操作が行えないのでかなりスコアがブレてしまう。そのため、100件のテストケースだとかなりスコアが変動することが多々あった。今回のスコア計算だとちょっと差分が出ただけでかなり点差が開くので絶対スコアも相対スコアも確かに採用するのが難しそうだなと感じた。そういった場合でも順位スコアであれば解決出来るのか〜と驚いた。

もっとクエリーをうまく使えば効率的に情報が得られたのかもしれないけど最後まで分からなかった。毎回ソートを行っているがこのクエリーの消費量がハンパじゃないのでもっと効率的に管理できたら良かったけど特に思いつかなかった。

期間中に DALL·E 3 が使用できるようになったのでブログに追加する画像のバリエーションがかなり増やせそうで嬉しい。

0 - 9 までのスコア

Seed 0: 40351
Seed 1: 27805
Seed 2: 1659
Seed 3: 2066
Seed 4: 118717
Seed 5: 782178
Seed 6: 5601
Seed 7: 16586
Seed 8: 1129610
Seed 9: 116495

Marathon Match 148 Frogs 参加記

問題

www.topcoder.com

方針

各カエルの行動をなるべくコインが集まるように焼きなましで決定する。

提出コード

MM148 last submit · GitHub

焼きなましによる行動探索

各カエルごとに「このターンに移動する方向」の情報を持たせ、任意のカエルの移動方向を変更させながら一番コインを集めるような移動パターンを探索します。

任意のカエルの移動パターンを 1箇所ランダムに変更する

変更したあとの行動を実際にシミュレーションして評価が良くなっているかどうかを確認する。変更範囲としては6ターンを先読みしています。

行動の評価

序盤は下の方に移動、中盤はコイン集め、終盤はビーチに戻るを基本行動として行動を評価していきます。

評価項目

  • 序盤は下の方向に移動するように評価
  • 池に落ちる (-9999)
  • コイン
    • 下の方にあるコインの評価を高くする

池ポチャ確定回避

6ターンしか先読みしてないので「この先どう移動しても池ポチャしていまう」という状況でも生存判定をしてしまう可能性があるので、そうなるパターンをある程度列挙して回避するようにしています。

同じ方向に流れる行が 3箇所連続している中心部分がその対象となります。

行動範囲の制限

スタート地点に戻ってこないとスコアにならないので時間経過で行動できる盤面の範囲を制限する。

少しずつ行動できる範囲を狭めていく。(移動できなくするというよりはそこに移動した時に評価値を下げる。そこでコインを取得しても評価しない等)

基本的には残りターンが 4 * H を切ったら徐々に範囲を狭めていく。

LOG の先読み

基本的にはスライドした時に出現するオブジェクトは水で固定しているが、以下のパターンでは別のものを生成する。

確定で LOG が出るとき

既に水が KW 個出ている場合は次のオブジェクトは確定で LOG なのでそれにする

KW = 1 の場合

水が 2個連続する可能性はないので次は LOG で確定

1マススライドする余裕がある場合に確実に移動できる場合

KW = 3 とした場合に、次にくるオブジェクトが水か LOG かわからない状態があるとします。

LOG の場合

水の場合

水が来た場合は左に 1マス移動すれば次は確実に LOG が来るので移動することができます。

このように今連続している水の数が KW - 1個の場合に「横に 1マススライドできる場合だけ移動できる LOG」生成します。

感想

1箇所を変更するとあとの行動に大きく影響するので焼きなましはあまり良くなかったかも。上位はビームサーチだったらしいけどここまでコインの探索効率変わるのかと思った。「とりあえず試す力」みたいななのが落ちている気がする。