Marathon Match 147 SurfaceReconstruction 参加記 - simanのブログ
問題 www.topcoder.com 提出コード https://gist.github.com/siman-man/2218aee9a4a99e3bc6c780dbb72066ba 方針 N と A の値からサンプリングの回数を決定 クエリーの投げる位置を焼きなましで調整 クエリーの結果からグリッドを生成している方程式のパラメータを焼きなましで求める N と A の値からサンプリング回数を求める サンプルの個数から大体これぐらいの mse スコアが出るよというのを事前に計算しておいて、ちょうどいい感じのサンプル個数を求める。 mse の推測値が悪かったのか N < 40 のケースだとうまくいかなかったので場合分け。もっと細かく調整できたと思うけど多分そんなスコア改善しないし面倒なのでやってない。（cover_rate は sample_count * 9 / (N * N) で計算して
ビームサーチをライブラリ化する【基礎編】 - 競技プログラミング学習
7/30 追記：一部の実装を変更して高速化しました。(ビームサーチ内で毎回配列を定義するコストが無視できなかったため、一度だけ定義して毎回中身を全て消去する形にしました) ヒューリスティックコンテストでよく用いられるビームサーチという手法があります。山登り/焼きなまし法と並んで必ずと言っていいほど紹介されるビームサーチですが、実装が大変と感じている方も多いと思います。 この記事ではビームサーチを既に知っている方向けに、ライブラリ化の指針を提供したいと考えています。ビームサーチ自体については簡単に説明する程度ですのでご了承ください*1。 今回は基礎編と題して、一般に広く用いられていると思われる実装方法を紹介します。応用編*2ではrhooさんの記事などで解説されている他の実装方法を紹介したいと考えています。本記事中のソースコードは自由に利用していただいて構いませんが、万一何らかの不利益が生じて
プリム法ベースのシュタイナー木 - bowwowforeachの日記
AHC020でシュタイナー木を作るような問題がでました。そこでプリム法ベースのシュタイナー木を作ることがあったのでその方法を説明します。 シュタイナー木とは グラフとターミナルと呼ばれる頂点集合が与えられたとき、ターミナルを全てつなぐ木のことをシュタイナー木といいます。 頂点A,B,Cがターミナル シュタイナー木の例 ターミナルでない頂点はつないでもつながなくても構いません。 シュタイナー木のうちコストが最小のものを最小シュタイナー木といい、これを求めるアルゴリズムとしてDreyfus-Wagner法というものがあるらしいです。しかしこの方法はとても計算量が多いです。 今回紹介するプリム法ベースのシュタイナー木は、計算量は少なくて済みますがコストが最小になるとは限りません。ヒューリスティックコンテストにおける焼きなましの最中など、厳密さより速度が優先されるようなケースでの使用を想定していま
最適化AIでサービス生み出すリクルート、領域と技術の「かけ算」が奏功
人工知能（AI）というと機械学習や深層学習が注目されがちだが、実はそれはAIの半分にすぎない。あとの半分、いわば「アナザーAI」は企業の生産計画や物流などで重要な役割を果たす「最適化AI」だ。最適化AIを実現するための技術が、「焼きなまし法」や「ビームサーチ」などの「ヒューリスティックアルゴリズム（メタヒューリスティクス）」である。この連載では、競技プログラミングサービスを提供しているAtCoderの高橋直大社長が、アルゴリズムに対する深い知識を生かし、最適化AIを活用している企業を訪ねて取り組みを探っていく。 今回は、飲食や美容などさまざまな領域で消費者向けや企業向けのサービスを提供しているリクルートを訪問した。データ関連技術を統括する同社プロダクト統括本部 プロダクト開発統括室 データ推進室 データテクノロジーユニットの阿部直之ユニット長に、最適化AIを使ったサービスの取り組みを聞いた
高速なビームサーチが欲しい!!! - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? この記事はアルゴリズム強化月間の一環として書かれた記事です。 はじめに こんにちは！ rhooというアカウント名で競技プログラミングをやっている者です。 半年ほど前からヒューリスティック系のコンテストにも手を出し始めました。 この記事では私がゲーム実況者xの挑戦という過去問を解くときに使った手法の解説記事となります。 要約 ビームサーチの状態の管理を差分を持った木構造で管理するとコピーコストが発生しなくなり高速になります。 前提知識 ビームサーチについての基礎的な知識と参照カウントベースのスマートポインタ(c++でのshared_ptr
ヒューリスティックコンテスト(マラソン)、ゲームAIコンテストで使う武器まとめ｜にゃにゃん(山名琢翔)
ものづくりとプログラミングとルービックキューブが大好きなにゃにゃんです。今回は競技プログラミングに関する内容です。 この記事の執筆時点ではもうすぐAHC002というヒューリスティックコンテストが開かれます。 これに向けて過去問を解いて準備をしていて、ヒューリスティックコンテストやゲームAIコンテスト(基本的にまとめて「ヒューリスティックコンテスト」と言うことにします)における様々な武器やTIPSがわかってきました。それを自分のメモも兼ねてまとめます。なお、深さ優先探索や幅優先探索など、アルゴリズムコンテストでもよく出てくるアルゴリズムについては省きました。ただでさえ記事の文字数が結構多くなってしまったので… この記事は私が今後精進していく中で新たな発見があったら随時追記していこうと思います。 ヒューリスティックコンテストとは ヒューリスティックコンテストは、ある問題が与えられて、それに対す
マラソン勉強するぞ！~アルゴリズム編~ - tardigradeの競プロ日記
はじめに こんにちは、tardigradeです。本ブログでは主に競技プログラミングのマラソンコンテスト(ヒューリスティックコンテスト)についての記事を書いていく予定です。そんなに固い記事を書くつもりはないので、のんびり気楽に読んでいただければ幸いです。 本記事が初投稿になります。 自己紹介 名前は「tardigrade(たーでぃぐれいど)」です。「くまむし」の英訳から来ているので、「くまむし」とか「くま」と呼ばれることもあります。競技プログラミング歴はおよそ1年、2021/03/02時点でAtCoder緑です。 AHC001が開催されるぞ～！！！ 今週の土曜日、3/6から3/14まで、「AtCoder Heuristic Contest 001」が開催されます。マラソン用の新しいレーティングも整備されるということで、とても楽しみです(*ﾟ▽ﾟ*) ところで、僕はあまりマラソンの経験がありま
CODE VS Reborn - y_kawanoのブログ
2019/4/15～2019/5/10にあったゲームAIコンテスト。ぷよぷよみたいな落ち物パズルゲー。 決勝の様子(が見れる予定)：https://live.nicovideo.jp/gate/lv320076507 予選3位/112人・決勝◯位でした。 参加人数は少ないですが参加面子を考えると日本最高峰のゲームAIコンテストだったでしょう。 ルール（適当説明） 基本ぷよぷよですが、4つ揃えるんじゃなくて数字の和を10に揃えたらブロックが消えるみたいなルールです。 連鎖すると敵の盤面にお邪魔ブロックを降らせます。相殺もぷよぷよと同じ仕様です。 ぷよぷよと大きく違うのはスキルがある点です。ブロックを消すとスキルゲージが溜まって、溜まると数字の5を爆発させて連鎖したときと同じように攻撃ができます。 アルゴリズム概要 目標連鎖数を決めてchokudaiサーチで探索して、発火が近くなったら色々考え
Rustでマラソンをするときに使えそうなスニペット達
はじめに Rustでマラソン形式の競技プログラミングコンテストに出場したときに何度か使ったコードを紹介します。 Rustで出場できるマラソンはあまりない印象ですが、参考になれば幸いです また、自分の記事ですがalgoの方に興味がある方は Rustで競技プログラミング スターターキット もしRustでのスニペット管理に興味ある方は Rustで競技プログラミングをするときの"スニペット管理"をまじめに考える(cargo-snippetの紹介) を御覧ください。 この記事で紹介しているスニペットはすべて、hatoo/competitive-rust-snippetsで管理しています。 PCG 2023/08/07 PCGのほうが好きになったのでPCGのセクションを足しました。 XorShiftのところは以前のまま置いておきます。 外部クレートは使えないので簡単にPCGで乱数生成器を用意します。
今日から使えないビット演算（CODE VS Reborn編） - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 0. はじめに この記事は，チームラボ・リクルートさんがスポンサーするCODE VS Reborn (https://codevs.jp/ ) に関する記事になります． CODE VS Rebornはぷよぷよとボンバーマンを合わせたようなゲームのAIを作るコンテストです． 1. ゲームのルール 今回のゲームは, CODE VS 2.0 のリメイク版であるCODE VS for STUDENTのリメイク版で, 対戦形式の落ちものパズルです．ルールの詳細は以下の PDF に記されています. https://static.codevs.jp/
日本橋ハーフマラソン本戦B 日本橋大渋滞 解説 - koyumeishiのブログ
日本橋ハーフマラソン本戦B 日本橋大渋滞 解説 先日 RCO が主催したプログラミングコンテスト 日本橋ハーフマラソン のオープンコンテストに参加しました。 オープン参加で賞金もレートもかかっていなかったのでA問題は放棄して、 ビジュアライザが用意されていた B問題 日本橋大渋滞 を解こうとしたのですが、実装が間に合わず未提出、0点のままコンテストは終了してしまいました。 後日考えていた方針の実装を終わらせ提出したところ、かなり出来のいい点数を出せたのでその振り返りをします。 2017/03/26 時点で一位 http://rco-contest-2017-final-open.contest.atcoder.jp/submissions/1176109 入力例2 74手 46555点 おおよその方針は次の一連のツイートの通りですが、もうちょいと詳しく解説。 天才過ぎて70手ぐらいまでにな
焼きなまし法の真実 – システム工房コルン
はじめに 焼きなまし法はベター山登りなのか？ 探索空間は本当に高次元なのか？ 採択確率式の正当性 メトロポリス・ヘイスティングス法がうまくいく条件 メトロポリス・ヘイスティングス法と温度 おまけ1 … 遷移先候補をどう提案するか？ おまけ2 … 温度管理について 終わりに 謝辞 はじめに 著者は、TopCoder Marathon Matchesで世界大会決勝へとアメリカに3度招待された。 その3度ともが、予選では強文脈ゲームによる通過であり、焼きなまし法の使えない問題分類だった。 近年、文脈のない探索の出題が増えてきており、焼きなまし法が正解方針であることが多くなっている。 焼きなまし法へと苦手意識を持った著者であったが、出題の傾向がそうであるのなら避けて通れるものでもなく、焼きなまし法の出題であっても単純な殴り合いで1位をもぎ取れるまでになりたいと2年前に決意して、七転八倒を繰り返しな
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
AHC035解説
https://x.com/eijirou_kyopro/status/1753041794617823445?s=12&t=YpIPcsjKfoTpmECNdRL-uw
JavaScript is not available.
Chokudai Searchっぽい探索手法が書かれた文献をちょっと調べた
GitHub - kera6rhy/codevs_reborn
GitHub - piroz95/CodeVSReborn
talks/2019/05/RustLT5/slides.md at master · togatoga/talks
2013 TCO Marathon Round 2 (yowa)
