simanのブログ

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

Hitachi Hokudai Lab. & Hokkaido University Contest 2021 の感想

atcoder.jp

に参加してました。と言っても最低限のコードを書いて終わったのでガッツリ参加したというわけではありませんが、 全体を通しての感想を残しておきます。(どちらかというと要望)

f:id:simanman:20220205014242p:plain:w800

運営も自虐するぐらいにはグダっていたと思います。

共通

アナウンス無しの延期は止めてほしい

  • OO 日に更新予定です。 -> OO 日に特に何も無し
  • XX 日に公開予定です。 -> XX 日に特に何も無し

このパターンが多かったです。当日でも良いので延期のアナウンスがあったほうが嬉しいです。(アナウンス無しは「もしかして放置されている?」と不安になります)

ジャッジプログラムや問題文の更新が多い

正直多すぎました。特にコンテストの序盤とかはちょっとジャッジプログラムを読み進めるだけでもすぐ問題文との矛盾点が見つかるぐらいには多かったです。4000行近くのジャッジプログラムだったので不具合が多いのは仕方ないと思いつつ、コンテスト終了直前まで定期的に修正が入るのはさすがにきつかったです。

ジャッジプログラムが読みにくい

不要な ;if (false) のようなコードが多く、ジャッジプログラムを読むときには毎回消しながら読んでいました。

エラーメッセージが不親切

コンテストタント側のプログラムが何かしらの制約にひっかかって落ちた時にエラーメッセージ無しに exit(1); だけで終わらせていたので原因を突き止めるのに時間がかかりました。 (自分でエラーメッセージを追加してました)

ジャッジプログラムの計算資源を別で管理して欲しい

今回制限として「実行時間制限: 300 sec」「メモリ制限: 3072 MB」とあったのですが、正直何の指標にもなりませんでした。 というのも今回、コンテスタント側はジャッジ側にクエリを投げることで仮スコアを得ることが出来たのですが、 クエリの処理にかかる「時間」と「メモリ使用量」がこの制限に含まれていました。そのため、コンテスタント側で制限を守っていてもジャッジ側の処理でそれを超えてしまう可能性がありました。

様々なケースが考えられる中でテストケースのジェネレータも無いままジャッジ側のメモリの最大使用量を見積もるのは面倒でした。

「時間」に関しては A 問題だと、グリッド配置を決めたら後はジャッジプログラムが処理するだけなのですが、例えば 280sec 使って配置を決めても、ジャッジ側の処理で 21 sec 以上使ってしまうとアウトなので、コンテスタント側では「この配置だと XX sec 使用する」みたいな予測を行って、余裕をもたせてプログラムを終了させる必要がありました。

コンテスト序盤とかはほぼ何もしてないサンプルコードでも 90 sec 近くかかっていました。(改良版が出て 20 sec ぐらいには下がりました)

テストケースジェネレータの提供もしくは生成方法の擬似コード表記

今回 pretest が 3件だけだったので、システムテストが重要になってくるのですが、システムテストでどのようなパラメータになるのかがちょっとわからなかったです。 例として

(例: 系統から電力を購入することによるペナルティ(alpha_buy_ele やalpha_buy_env)が大きいケース、w_acc, w_trans, w_ele, w_envのいずれか1つが小さくなるケース)

とあり「alpha_buy_elealpha_buy_env は制約内でランダムに決められる値ではないのか」「いずれか1つが小さくなるケース ということは他のパラメータは同一の値なのか」とか色々質問したい事項がありました。

将来的な技術動向や政策動向を考慮し、特定のアセットや条件などが有利になるケースを含むように選択

と書かれてしまうと正直もう個人的にはお手上げでした。

相対スコアの導入

今回大まかに「輸送スコア」「電力スコア」「災害対応スコア」とカテゴリー別のスコアがあったのですが「輸送スコア」で得られるスコアが他のスコアに比べて大きかったので「輸送スコアを得意とする人」と「電力スコアを得意とする人」を比較した時に「輸送スコアを得意とする人」が有利となってしまうので、各スコアを平等に評価するのであれば相対スコアで比較したほうが良いと思いました。

A 問題

サンプルコードの充実化

A問題のサンプルコードが簡素なシェルスクリプトだったのは不親切かなと思いました。 問題自体が多くの入力を受け取る必要があったのでサンプルコードを書くコストもそれなりに高かったと想像できるのですが

なお、初心者向けのサンプルコードを用意しているので、必要に応じて参照して欲しい。

この文言からの

#!/bin/sh

echo end
echo 2
echo 1000 10000
echo 1 3
echo 1 
echo 1 3
echo 1
echo 1561 20000
echo 1 2
echo 1 
echo 1 3
echo 1 
echo 2
echo 1000 100000 1
echo 1561 100000 1
echo submit 9999 1

このコードは少し不親切かなと思いました。最低限入力を受け取るあたりのコードは欲しかった気がします。

車両アルゴリズムの説明

A 問題はグリッドと EV の配置を決めたら後はジャッジ側で事前に用意されたアルゴリズムによって処理が行われていくのですが、この車両アルゴリズムについての説明が一切無いのでジャッジプログラムを読んで理解する必要がありました。

A 問題の目的として「安定した電力供給に加えて円滑に輸送サービスを提供するために適切なナノグリッドの配置を考えて欲しい」とあるので、車両のアルゴリズムについてはある程度出題者側から説明が欲しかったです。

B 問題

ジャッジプログラムに計算資源を取られること以外は特に不満はありませんでした。

Marathon Match 132 BouncingBalls

問題

www.topcoder.com

方針

  • 銃の位置を焼きなましで決める
  • 銃の位置決定後はビームサーチで良い盤面を探す
  • ボールが真ん中に集まるように盤面を作成する

銃の位置を焼きなましで決める (START ~ 1 sec)

まず最初に銃の位置を固定するために焼きなましを行って良さそうな銃の配置を決めます。

遷移としては以下の 1つだけです。

  • ランダムに銃の位置を変化させる

銃の位置が決まったあとは、シミュレーションを行い貪欲にパネルを配置していってスコアを求めます。

貪欲に配置

パネル配置については以下のルールのもと行われます。

新しい空白マスに到達した際に

  • ボールが上方向に進んでいる場合
    • ボールが盤面の左側に存在する場合は / のパネルを設置
    • ボールが盤面の右側に存在する場合は \ のパネルを設置
    • それ以外はランダムにパネルを配置

f:id:simanman:20220120061550p:plain:w240

f:id:simanman:20220120061621p:plain:w240

  • ボールが右方向に進んでいる場合
    • ボールが盤面の上側に存在する場合は \ のパネルを配置
    • ボールが盤面の下側に存在する場合は / のパネルを配置
    • それ以外はランダムにパネルを配置

f:id:simanman:20220120062111p:plain:w240

f:id:simanman:20220120062328p:plain:w240

下方向と左方向については上方向と右方向を逆にしたものになります。

貪欲にパネルを置いていってスコアが高くなる配置を採用します。

ビームサーチで良い盤面を探す (1 sec ~ TIME_LIMIT)

銃の位置を固定したらビームサーチで盤面を探索していきます。

進め方としては以下の方法で行っていきます

  • 盤面のシミュレーションを行う
  • いずれかのボールがまだパネルを配置していないマスに止まるとシミュレーションを止める
  • パネルを配置
  • シミュレーションを再開

パネルの配置

パネルの候補として /, \, . のいずれか 1つを選択します。 配置候補が複数ある場合はすべての組み合わせを試しますが、空白パネルを 2つ以上を含む候補は除きます。

例) 配置候補が 2箇所ある場合のパネル候補一覧

  • /, /
  • /, \
  • /, .
  • \, /
  • \, \
  • \, .
  • ., /
  • ., \

盤面の評価

1つでもボールが盤面から出てしまうとゲームが終了するので、盤面から出ないように中央にボールが集まっている状態を良しとします。 また、各パネルの配置についてボーナス点を与えていきます。いくつか例をあげます

  • 盤面中央に向きを変える配置

f:id:simanman:20220120064446p:plain:w240

  • 盤面中央へと進む配置

f:id:simanman:20220120064807p:plain:w240

また特定の配置にはペナルティを与えています

  • 盤面外に向きを変える配置

f:id:simanman:20220120065117p:plain:w240

  • 盤面外へと進む配置

f:id:simanman:20220120065225p:plain:w240

他にもボールの位置についてもペナルティやボーナスを与えています

f:id:simanman:20220120065532p:plain:w240

赤い部分はペナルティ、緑の部分はボーナスになっています。

他にも色々ありますが、基本的には「盤面中央に向かう変更ならボーナス、盤面外へと進む変更ならペナルティ」といった感じです。

感想

評価関数をうまく作れた人が勝てそうだと思ったので、ビジュアライザをずっと眺めてましたが最後までこれとこれといったアイデアは出てきませんでした。事前に計算した盤面を埋め込む方針も考えましたが、固定パネルとボーナスパネルがかなりノイズになっててそれが出来ない仕組みになっていた気がします。

Seed 1: 198
Seed 2: 42985
Seed 3: 28195
Seed 4: 2748
Seed 5: 285
Seed 6: 1866
Seed 7: 4445
Seed 8: 28274
Seed 9: 46363
Seed 10: 35872

MM131 StopTheElves 感想

問題

www.topcoder.com

最近オンライン問題多くなってきた。

方針

  • プレゼントを囲むように箱を設置する
  • 箱はすぐ設置するのではなくエルフが近づいたときに設置を行う
  • 事前にシミュレーションを行って防衛成功率の低いプレゼントは守らない

プレゼントを囲むように箱を設置

プレゼントの周辺マスをチェックして、このマスに対して凸包を求めます。この操作は毎ターン行います。

f:id:simanman:20211223235843p:plain:w240

f:id:simanman:20211224000523p:plain:w240

f:id:simanman:20211224000842p:plain:w240

求めたマスに対して、それぞれ最短路を求めてマス同士を接続します。

f:id:simanman:20211224001108p:plain:w240

箱はすぐ設置するのではなくエルフが近づいたときに設置を行う

箱を早く設置しようがしまいが結局エルフは箱 or プレゼントを持ち帰るまでフィールドに居続けるので、なるべく右往左往してもらうために箱の設置はギリギリまで待ちます。あと、お金は基本的に保持していたほうがあらゆる事象に対処出来るのでなるべくセーブします。

f:id:simanman:20211224002300p:plain:w240

f:id:simanman:20211224002316p:plain:w240

事前にシミュレーションを行って防衛成功率の低いプレゼントは守らない

実際にクエリを送る前にシミュレーションをある程度回してみて、防衛に成功する確率の低いプレゼントについては守る対象から外します。

感想

エルフ行動の優先順位をもっとうまく利用した守り方もありそうだったけど、そこまで考察 & 実装が出来なかった。ただプレゼントを守るだけではダメなのはスコア差から読み取れたけど、そこから何も進めれなかったので残念。凸包以上に効率的な守り方を見つけられなかったのもダメだった。(木が多いときはもっと効率的な守り方がありそう)

TCO21Final 参加記

TCO21Final に参加してきました。

問題

下の画像のようなトーラス状の N * N フィールドが存在しており、コインを 1つ取ると 100 point、棘を踏むとスコアが半分になります。コインは取得すると消えますが、棘は踏んでも消えません。

f:id:simanman:20211119225829p:plain:w400

プレイヤーは自由に移動できるというわけではなく移動用のサイコロを複数保持しています。(2 ~ 6 個) サイコロの種類は全部で 12種類存在しています。

  • 0 が出るサイコロ (STAY)
  • 1 が出るサイコロ (ONE)
  • 2 が出るサイコロ (TWO)
  • 3 が出るサイコロ (THREE)
  • 4 が出るサイコロ (FOUR)
  • 5 が出るサイコロ (FIVE)
  • 6 が出るサイコロ (SIX)
  • 1 or 3 or 5 が出るサイコロ (ODD)
  • 2 or 4 or 6 が出るサイコロ (EVEN)
  • 1 or 2 or 3 が出るサイコロ (LOW)
  • 4 or 5 or 6 が出るサイコロ (HIGH)
  • 1 or 2 or 3 or 4 or 5 or 6 が出るサイコロ (RANDOM)

1 度サイコロを使用すると、そのサイコロは消費され新たなサイコロを補充します。このとき補充されるサイコロの確率は各サイコロの出目の種類数に比例します。(なので、例えば RANDOM は ONE のサイコロよりも 6倍出やすく、ODD よりも 2倍出やすいといった感じです)

N * N ターンの間でより多くのスコアを取得するように頑張りましょうという問題です。(N * N ターンの経過を待たずとも途中で辞めることも可能です)

方針

最初は効率的にコインを集める方法で最初考えていたのですが、棘が密集している画像を見て「いかに棘を踏まないようにサイコロを振るか」に方針を変えました。

f:id:simanman:20211119232321p:plain:w400

基本方針は貪欲で現時点で保持しているサイコロを振ってみて止まる可能性のあるマスをすべて試して、その後の盤面の評価値の合計が高いものを採用していきます。

評価値としては主に以下のような内容になってます(一部)

  • コインに止まる [+100]
  • 棘に止まる [-score / 2]
  • RANDOM サイコロを消費する [+1000]
  • RANDOM サイコロを安全に消費できるマスに移動する [+100]
  • 棘以外のマスで STAY サイコロを振る [+1000000]

ある程度ゲームを回してみたところ、手持ちが RANDOM サイコロだけになり棘を踏むリスクが高まってゲームを中止するといった流れが多く見られたので、とにかく RANDOM を捨てることに比重を置きました。STAY サイコロは実質手札交換みたいなものなので振れるタイミングでは必ず振るようにしています。

あとは、実際にジャッジ側に投げる前にどの程度のスコアが取れるのかを事前にシミュレーションをしておき、そのシミュレーションの平均スコアを基準にゲームをやめるかどうかの判断を行いました。

やめる基準としては 事前計算した平均スコア * 0.8 のスコアを保持している状態で棘を踏む可能性が発生した際に、ローカルでシミューレーションを複数回してそのスコアの平均値が今よりも大きいのであればゲームを続行、そうでないなら終了という判断をしています。

感想

実装した内容は 2手読みな感じになったが、個人的にはモンテカルロ木探索とか刺さりそうな感じはした。(ただ眠くて頭が回らず実装できなかった) 3手読みは時間制限的に無理で、いい感じに DP で書けるかな?と思ったけどあまりいい感じにスコアは伸びてくれなかった。

関係ない話

ノート PC 1台で参加したけど、画面共有とカメラ ON でかなりのパワーを取られて少しモッサリした環境で参加する必要があったのが辛み。

事前に AWS マシンの提供があったけど結局使ってない、割とハイスペックだったからテスト回すときとか使っとけばよかった感はある。

途中眠すぎて寝てた。

トイレ行きたいときに毎回チャットで連絡して返信を待つのが面倒だった。

途中 AHC006 が開催れていることに気づいて順位表だけ眺めてた。

たまに英語でなにか言われたけど、何を言ってるかわかってなくてとりあえず「OK!!」とか言ってた。間違った返事をしている可能性がある。(大体はテキストでやり取りしてたので多分大丈夫)

色々新鮮で楽しかった。

Marathon Match 130 GraphLabeling Strategy

Problem

www.topcoder.com

Note

This article has been translated by DeepL. Original ver is here.

https://simanman.hatenablog.com/entry/2021/11/03/121958

Strategy

The general strategy is to determine the maximum value for labeling before, and then gradually reduce the maximum value if the entire node was successfully labeled, in a binary search-like strategy.

  • Pre-determine the maximum value of label X to be given before labeling.
  • Start labeling from a random point and visit each node recursively
  • When labeling at each vertex, check if nodes with an even distance from the starting point can be labeled from 0 (0, 1, 2, ..., X). Nodes with odd distances are checked to see if they can be labeled from X (X, X - 1, X - 2, ..., 0).
  • If labeling succeeds for all nodes, update the maximum X value (X = X / 2); if it fails, set a value slightly lower than the previous best value (X = BEST_X * random_value [0.95, 1.0))
  • Repeat this procedure until the time limit is reached.

Determine the maximum value X of the label

Determine the maximum value when labeling is done. This way you will get a graph with a definite X score when the labeling is complete.

Labeling

Start from a random point and label it. Nodes with an even distance from the starting point will search for labels assignable from 0, and nodes with an odd distance will search for labels assignable from X.

Example for X = 100

f:id:simanman:20211103120144p:plain:w240

f:id:simanman:20211103120719p:plain:w240

f:id:simanman:20211103120707p:plain:w240

f:id:simanman:20211103120826p:plain:w240

f:id:simanman:20211103120925p:plain:w240

f:id:simanman:20211103121016p:plain:w240

Since the labeling was successful for X = 100, we will do the same for the next attempt with the value of X = 50. If it fails, we randomly choose a value from the range X = [95, 99]. If it succeeds, it will lower the maximum value by a large amount, and if it fails, it will lower it by a small amount.

Repeat this process until the time limit and output the best labeling.

Summary

My overall score was low because I didn't know about the Gorom ruler, but I was able to get a high score on a sparse graph, so I put together a strategy.

Marathon Match 130 GraphLabeling 戦略

問題

www.topcoder.com

戦略

大まかな戦略としてはラベル付けを行う際の最大値を事前に決定して、ノード全体にラベル付けが成功した場合は最大値を徐々に減らしていくという二分探索風な戦略を取りました。

  • ラベル付けを行う前に与えるラベルの最大値 X を事前に決定する
  • 任意の点からラベル付けを開始し、各ノードへ再帰的に訪問する
  • 各頂点においてラベル付けを行う際に、開始地点からの距離が偶数のノードは 0 からラベル付けが行えるかどうかをチェックする (0, 1, 2 ... X)。距離が奇数のノードは X からラベル付けが行えるかどうかをチェックする (X, X - 1, X - 2, ... 0)。
  • すべてのノードに対してラベル付けが成功した場合は最大値 X の値を更新する(X = X / 2)、失敗した場合は過去のベストの値から少し下げた値を設定する(X = BEST_X * random_value [0.95, 1.0))
  • この手順を制限時間まで繰り返す

ラベルの最大値 X を決定する

ラベル付けを行う際に最大値を決定します。こうすることでラベル付けが完了した際に X スコアが確定したグラフを手に入れることが出来ます。

ラベル付けを行う

任意の点から開始してラベル付けを行います。開始地点から距離が偶数のノードは 0 から割り振り可能なラベルを探索、距離が奇数のノードは X から割り振り可能なラベルの探索を行います。

X = 100 の例

f:id:simanman:20211103120144p:plain:w240

f:id:simanman:20211103120719p:plain:w240

f:id:simanman:20211103120707p:plain:w240

f:id:simanman:20211103120826p:plain:w240

f:id:simanman:20211103120925p:plain:w240

f:id:simanman:20211103121016p:plain:w240

X = 100 ではラベル付けが成功したので、次の試行では X = 50 の値で同じ処理を行います。もし失敗した場合は X = [95, 99] の範囲からランダムに選びます。成功したときは大きく最大値を下げて、失敗した場合は小さく下げていく感じになります。

この処理を制限時間まで繰り返して一番良かったラベル付けを出力します。

まとめ

ゴロム定規を知らなかったので全体的なスコアは低かったのですが疎なグラフでは高いスコアを出せていたので方針をまとめてみました。

Marathon Match 129 ChickenRun (translated ver)

Prolog

This article is translated by DeepL and fix a little.

simanman.hatenablog.com

Problem

www.topcoder.com

Strategy

  • Organize the farmers into groups of two. If there is an odd number, only one group will have three members.
  • Move the farmer.
  • Evaluate the grid after the move to determine the best farmers placement.

Farmer groupings

We will need at least two people to catch the chickens, so build a group of two.(There are some patterns that can be caught by one person, but that's not many.)

f:id:simanman:20210923220118p:plain:w480

f:id:simanman:20210923220132p:plain:w480

If there is an odd number, there will be only one group of three. Each group decides on a chicken to chase, and then tries to chase.

Move the farmers

As for moving farmers, there are five possible move candidates for each farmer: up, down, right, left, and wait. If you try to combine the moves of each farmer, you will get a pattern of 5 ** number of farmers. In order to find the optimal placement from this vast of patterns, I used the direction of movement of the farmers as an array and SA (Simulated Annealing) the direction of movement to find the optimal placement.

f:id:simanman:20210924055628p:plain:w480

The transition is select any one point and change direction.

f:id:simanman:20210924055532p:plain:w480

This will make it easier to search for some effective patterns even if the number of farmers increases.

Evaluation of the grid

For the evaluation of the board, we focused on the following items for confirmation.

  • Catching the chickens
  • Check to see if the chickens are in a caught pattern.
  • Whether you are able to get close to the chicken to be captured or not.
  • Whether or not the candidates of movement of the chickens to be captured is being reduced.

The higher the likelihood of catching chickens, the higher the evaluation value.

Catching the chickens

If farmer reaches the same cell as the chicken that is the highest value. In some cases, it may be better not to dare to catch them, but I couldn't evaluate them that much.

A case where it's better not to catch them.

f:id:simanman:20210923222127p:plain:w480

The best solution here will be to try to catch two chickens at the same time.

f:id:simanman:20210923222231p:plain:w480

Patterns that can be caught

Condition of a chicken can be caught is the chicken cannot move and there is a farmer in the adjacent cell to the chicken. For each chicken, check if it is in this state, and if it matches the pattern, give it a higher value. The main patterns are as follows.

f:id:simanman:20210923223028p:plain:w600

Leading to a catching pattern

For the patterns that can be caught, the prior state is only one candidate for chicken movement and a fence or farmer exists at the destination, so this state is also evaluated.

f:id:simanman:20210923224255p:plain:w600

Patterns that can be caught with probability

Since both the order and direction of the chickens' actions are randomly determined, the order and direction of the chickens' movements may lead to a catching pattern, also evaluate those patterns.

A pattern that can be caught depending on the order in which the chickens move.

f:id:simanman:20210923231041p:plain:w600

A pattern that can be caught depending on where the chickens are moved.

f:id:simanman:20210923231350p:plain:w600

Approach the target chicken.

Approach the target chicken. When approaching, move in such a way that you can reach as many cells as possible before the target chicken.(Move the chicken so that its Voronoi area becomes smaller.)

Summary

I made a mistake in the design of the evaluate function because the content of the evaluation function to catch the chickens became complicated and produced some unintended behavior. As for the movement of farmers, I think it would have been more efficient to focus on a specific area rather than the whole area at once, but I didn't have time to implement it, so I gave up. I was a little put off by the randomness of the chicken movement, but I wish I had done a little more detailed research and incorporated it into my evaluate function.