simanのブログ

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

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) まず最初に銃の位置を固定するために焼きなましを行っ…

MM131 StopTheElves 感想

問題 www.topcoder.com 最近オンライン問題多くなってきた。 方針 プレゼントを囲むように箱を設置する 箱はすぐ設置するのではなくエルフが近づいたときに設置を行う 事前にシミュレーションを行って防衛成功率の低いプレゼントは守らない プレゼントを囲む…

TCO21Final 参加記

TCO21Final に参加してきました。 問題 下の画像のようなトーラス状の N * N フィールドが存在しており、コインを 1つ取ると 100 point、棘を踏むとスコアが半分になります。コインは取得すると消えますが、棘は踏んでも消えません。 プレイヤーは自由に移動…

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…

Marathon Match 130 GraphLabeling 戦略

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

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 far…

Marathon Match 129 ChickenRun

問題 www.topcoder.com 方針 農家を 2人 1グループにまとめる。奇数の場合は 1つだけ3人のグループになる。 農家を移動させる 移動後の盤面を評価して一番良い配置を決定する 農家のグループ分け 鶏の確保には最低でも 2人必要なので 2人組のグループを作成…

RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜 参加記

問題 atcoder.jp 方針 機械は連結を維持する、ただし序盤は非連結をある程度許容する 野菜の「出現位置」「出現時間」を元にヒートマップを作成してそれを元に機械の配置を決めていく 探索で使用しているパラメータを変化させながらシミュレーションを複数回…

My approach of MM126 Slider

It was a matter of efficiently dropping the blocks into the holes. https://www.topcoder.com/challenges/82eb883d-85e9-442f-b0eb-91631d3d2a8f 方針 First, create an operation array in the order of dropping the base block. There are several st…

MM126 Slider 参加記

ブロックを効率よく穴に落とす問題でした https://www.topcoder.com/challenges/82eb883d-85e9-442f-b0eb-91631d3d2a8f 方針 まずベースとなるブロックを落とす順番の操作配列を作成します。 操作配列の作成についてはいくつかステップを踏んでいます 1手落…

MM 123 Jewels 参加録

参加してました。最初から最後まで順位表の不具合で自分の正しい順位がよくわからなかった。(恐らく 4, 5 位あたり) https://www.topcoder.com/challenges/b846362a-218e-4a3d-b86c-3d38f472e199 方針 スコアの計算式が「ラインスコア * コンボ数」で計算…

HACK TO THE FUTURE 2021 予選参加録

問題 atcoder.jp 方針 1 - カードをすべて回収する。 全部のカードを持っていたほうが後にカードを再配置する際に自由が効きそう。 2 - 集めたカードを再度配置し直す。 後で 0 から 99 のカードを集めるときの移動コストが小さくなるようにする。 3 - 0 か…

Ruby で赤黒木を実装してみた

この記事は Okinawa.rb Advent Calendar 2019 の 15日目の記事です。 結論 実装しました。 https://gist.github.com/siman-man/a8ed58effeaaf59855deac490574760c 二分探索木 前々から赤黒木を実装しようと思っていたのですがずっと放置していたので、今回実…

RailsDM 2019 で登壇してきました

RailsDM 2019 で登壇 RailsDM 2019 で「Ruby のコード解析の「静」と「動」」というタイトルで発表してきました。 去年の年末あたりに平野さんから登壇依頼が DM 経由で来て「せっかくの機会なのでやるか!」と思い引き受けることにしました。(CFP 形式だと…

今年作った gem の紹介 (2017)

この記事は Okinawa.rb Advent Calendar 2017 4日目の記事です。 自分は思いついたアイデアをすぐ gem にするようにしているのですが、今年は結構作った気がしたのでそれを紹介したいと思います。 spellcheck 主に技術系の単語にフォーカスしたスペルチェッ…

北大日立マラソン参加記

参加してました。 https://hokudai-hitachi2017-1.contest.atcoder.jp/ やったこと とりあえず submit (52935) 左上から丁寧に並べる 焼きなましする (52935 -> 149624) 近傍は ランダムな2点の位置を交換する 温度管理を調整 (149624 -> 155183) 雑に設定し…

PoisonedWine 参加録

問題 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16944&pm=14636 複数のワインの中から、毒に反応する試験紙を使って「毒入りのワイン」を見つけ出し「毒入りではないワイン」をいかに多く集めることが出来るかという問題…

MM92 Lighting 参加録

Marathon Match 92の「Lighting」に参加していました。 問題 SxS のセル状空間に光源の強さがDのL個のライトをいい感じに設置して、なるべくたくさんの空間を照らしましょう。 すごいシンプルでした。美術館問題に似た問題だなと思いました。 方針 大きく分…

RubyのEnglish.rbソース読み

Rubyの標準ライブラリを読んでいく、前回は3年前に ostruct を読んだ RubyのOpenStructソース読み 今回は English.rb を読んでいく。 English.rbとは何か English.rbはRubyの特殊変数に対してわかりやすい別の名前を付与するライブラリである。Rubyの特殊変…

TCO 16 Round3参戦記録 - TerrainCrossing -

TCOMMの最終ラウンドが終わりました。https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16704&pm=14283 問題文 縦横長さが S あるフィールドがあります。フィールド上にはN個のアイテムとN個の目的地が存在しています。あなたは…

OnlineExam 参戦記録

Codeforcesで開催されていたマラソンマッチに参加してました。codeforces.com 問題文 オンラインの試験があります。問題は全部で5000問あり、各問題は「YES」または「NO」で解答を行います。採点については各問題ごとに正解不正解を判別し不正解の数が2000に…

NYC Lightning Round 参戦記録

診断人さんのツイートで気づいて参戦しましたhttps://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16756&pm=14282 topcoder1日マラソン開催されるのであれば、すぐ寝る。されないのであれば、プログラミングして寝る。— nico_shin…