simanのブログ

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

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

2022年 一覧 コンテスト名 順位 金額 備考 Hitachi Hokudai Lab. & Hokkaido University Contest 2022 B問題 2位 100,000円 トヨタ自動車 実課題プログラミングコンテスト 2023 Spring 5位 10,000円 MC Digital プログラミングコンテスト2023 4位 30,000円 …

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…

Marathon Match 150 QueenAttack 参加記

問題 www.topcoder.com コード MM150 last submission · GitHub 戦略 以下の処理を高速に繰り返して一番スコアが良くなるものを採用します。 なるべくクイーン同士が取り合わないような配置を焼きなまし法で求める 求めた配置に対して最小費用流を用いて位置…

AHC027 Recurring Cleaning Route 参加記

問題 A - Recurring Cleaning Route 戦略 ビームサーチによる初期解生成 焼きなまし法による経路改善 ビームサーチパートは 500msec (テストケースによってはもっと速く終わる)、焼きなましパートは 1500msec 使用しています。 ビームサーチによる初期解生成…

AHC026 Stack of Boxes 参加記

問題 atcoder.jp コンテスト中ずっとバグ修正してたので参加してたかと言われると怪しい 戦略 基本的な部分は上位の人達と一緒です 任意の山を 1つ選択する 選択した山からすべての箱を取り除く 空になった山に昇順になるように箱を置き直す 山が全て昇順に…

AHC025 Balancing by Balance 参加記

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

Marathon Match 148 Frogs 参加記

問題 www.topcoder.com 方針 各カエルの行動をなるべくコインが集まるように焼きなましで決定する。 提出コード MM148 last submit · GitHub 焼きなましによる行動探索 各カエルごとに「このターンに移動する方向」の情報を持たせ、任意のカエルの移動方向を…

Marathon Match 147 SurfaceReconstruction 参加記

問題 www.topcoder.com 提出コード https://gist.github.com/siman-man/2218aee9a4a99e3bc6c780dbb72066ba 方針 N と A の値からサンプリングの回数を決定 クエリーの投げる位置を焼きなましで調整 クエリーの結果からグリッドを生成している方程式のパラメ…

#15 atmaCup 参加記

問題 www.guruguru.science 結果は 57位 方針 LightGBM 1本で戦いました。 test データに存在するユーザに対して train データに含まれている場合と含まれていない場合で 2つモデルを用意して予測 考えた特徴量をすべて突っ込んで LightGBM さんに頑張っても…

ICFP Programming Contest 2023 参加記

問題 https://www.icfpcontest.com/specification_v3.pdf M人のミュージシャンと A人の観客がいて、観客の満足度を最大化する問題でした。 満足度はミュージシャンと観客の距離とミュージシャンが演奏する楽器の種類によって決定されます。また、ミュージシ…

Marathon Match 146 HappyGrid 参加記

問題 www.topcoder.com 最終提出コード https://gist.github.com/siman-man/f8e9022891d996d36d5f505f67ff929d 方針 「盤面の作成」「ボールの移動」の 2つのフェーズがあります。 焼きなましによる盤面の作成 最小全域木を作成し葉の頂点を埋めるようにボー…

ALGO ARTIS プログラミングコンテスト2023 参加記

問題 atcoder.jp 方針 放送局の電波の強さを焼きなましで求める 使用する放送局を頂点とした最小全域木を求める 電波の強さを焼きなましで求める 各放送局の電波の強さを焼きなましで求めました。遷移としてはランダムな放送局を 1つ選んで電波の強さを変化…

CodinGame のローカル対戦ツール psyleague を試してみた

CodinGame のコンテストでは終盤になるとサブミットしたボットがすべての対戦を終了するのに数時間かかることも珍しくないので、ローカル環境で開発 & 検証を出来ることが重要になっています。 Spring Challenge 2023 では cg-brutaltester を利用してローカ…

Spring Challenge 2023 参加記

問題 www.codingame.com 久々の参加 方針 拠点と資源(クリスタル・卵)を頂点として最小全域木を作る 木の上にビーコンを配置し、ビーコンの強さを焼きなましで決定 どの資源を狙うかについてはターン毎にルールベースによって決定する 最小全域木の作成 資…

MC Digital プログラミングコンテスト2023 参加記

問題 atcoder.jp 方針 それぞれの空間からランダムに座標をいくつか選ぶ シルエットAの回転方向は 0で固定、シルエットBの回転方向をすべて試して一番評価が良くなるブロックを選ぶ ブロック設置後に 1マス延長を試してスコアが良くなるなら採用する処理をス…

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

一覧 コンテスト名 順位 金額 備考 Hitachi Hokudai Lab. & Hokkaido University Contest 2021 B問題 2位 100,000円 MC Digital プログラミングコンテスト2022 4位 30,000円 賞金対象外者が 1名いたので繰り上げ 第8回 Asprova プログラミングコンテスト 9位…

MM143 TreeMaker 参加記

問題 www.topcoder.com 戦略 完成図の作成を行う 色の配置を決める タイルの配置を決める 初期解の作成 枝の追加・削除による木の変形 完成図に対してもとのタイルとのどのタイルが対応するのかを割り当てる 盤面を操作してタイルを揃える y軸を揃える x軸を…

MM142 HelpTheElves 参加記

問題 www.topcoder.com 戦略 主に以下の 2つになります。 各エルフについてルールベースによる行動の選択 経路についてはダイクストラ法を使用しての探索 どの AI が使用されているかの検出 & メタ戦略 今回の問題では各AIの弱点を上手く攻める必要があった…

TCO22 Final 参加記

問題 今年のお題はパズルゲームでした。(インタラクティブ問題) 入力として N * N のサイズのグリッドと 3 * 3 の固定サイズの手持ちパネルの情報が与えられ、1ターン毎以下の操作を行うことが出来ます。 手持ちのパネルを 1枚選択しフィールド上のフルー…

MM141 TrafficController 参加記

問題 www.topcoder.com 方針 毎ターンごとに5ターン先までの信号機の方向を焼きなましで求める 焼きなましで信号機の方向を決める 遷移としては任意のターン、任意の信号機をランダムに 1箇所選択して変える 実際にシミュレーションを行い評価を行う 前進 +1…

第9回 Asprova プログラミングコンテスト 参加記

問題 atcoder.jp 方針 各設備の稼働パターンを以下の流れで調整しました。 二分探索で基本となる稼働パターンを決める 調整案をいくつか作成しその中からランダムで選択した案を採用する 終盤に稼働が必要なさそうな設備の稼働を止める 二分探索による稼働パ…

Marathon Match 137 StoneSeries 参加記

問題 www.topcoder.com 方針 2種類のビームサーチによる探索 通常のビームサーチ 最長パスを見つけるためのビームサーチ ビーム幅がある程度確保出来る場合は通常のビームサーチをそうでない場合は最長パスを見つけるためのビームサーチを使用しました。 最…

TCO22 Final に進出しました

TCO22 Final に進出 公式の順位表が更新されて Stage 4 のポイント集計に自分がカウントされていなかったので、去年に引き続き今年も TCO Final に出れるっぽいです(やったー)、去年は 4 -> 2 -> 4 の 200pt での突破でしたが、今年は 3 -> 7 -> 4 の 175p…

AHC011 Sliding Tree Puzzle 参加記

問題 atcoder.jp 方針 主に 3つのパートで構成されています 与えられたパネルから木を構築する 構築した盤面の各パネルに対して数字を割り振る (N * N - 1) puzzle を解く 木の構築 木の構築は盤面を焼き鈍して作成を行いました。木の条件が厳しそうなイメー…

MM136 HungryKnights 参加記

問題 www.topcoder.com 今回のスコア計算では同色の移動を連続で行うことで指数的にスコアが増える仕様となっていたので、出来るだけ長い同色消しの経路を作成する必要がありました。 方針 基本的な方針はビームサーチでの経路探索になります。 スタート地点…

Marathon Match 134 ShearTheSheep 参加記

問題 www.topcoder.com 戦略 どの農家がどの羊を追いかけるかの割当を最小費用流問題として解く 対象への最良経路を探索 羊毛のバケツリレーを行う 農家と羊の割当 どの農家がどの羊を追いかけるのかを最小費用流問題として解きます。辺の張り方としては「農…

第8回 Asprova プログラミングコンテスト 参加記

問題 atcoder.jp 方針 製造する製品の(形状、色、生産個数)をまとめて タスク という形にまとめる。 タスク を行う順番を焼きなましで更新していく 順番が確定した後 生産個数 の部分を別の焼きなましで改善していく タスクの作成 製品を 1個ずつ扱うと計…

AHC008 Territory 参加記

AHC008 に参加していました。 atcoder.jp 方針 大きく分けて「柵を配置する」「動物を捕まえる」の 2つのフェーズでゲームを進めていきます。 複数人で 1つのチームを作ってチーム単位で行動を行う 部屋の中に予め設定しておいた柵を配置する チーム単位で動…

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

atcoder.jp に参加してました。と言っても最低限のコードを書いて終わったのでガッツリ参加したというわけではありませんが、 全体を通しての感想を残しておきます。(どちらかというと要望) 運営も自虐するぐらいにはグダっていたと思います。 共通 アナウ…

Marathon Match 132 BouncingBalls

問題 www.topcoder.com 方針 銃の位置を焼きなましで決める 銃の位置決定後はビームサーチで良い盤面を探す ボールが真ん中に集まるように盤面を作成する 銃の位置を焼きなましで決める (START ~ 1 sec) まず最初に銃の位置を固定するために焼きなましを行っ…