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コンテストで使う武器まとめ｜にゃにゃん(山名琢翔)
ものづくりとプログラミングとルービックキューブが大好きなにゃにゃんです。今回は競技プログラミングに関する内容です。 この記事の執筆時点ではもうすぐAHC002というヒューリスティックコンテストが開かれます。 これに向けて過去問を解いて準備をしていて、ヒューリスティックコンテストやゲームAIコンテスト(基本的にまとめて「ヒューリスティックコンテスト」と言うことにします)における様々な武器やTIPSがわかってきました。それを自分のメモも兼ねてまとめます。なお、深さ優先探索や幅優先探索など、アルゴリズムコンテストでもよく出てくるアルゴリズムについては省きました。ただでさえ記事の文字数が結構多くなってしまったので… この記事は私が今後精進していく中で新たな発見があったら随時追記していこうと思います。 ヒューリスティックコンテストとは ヒューリスティックコンテストは、ある問題が与えられて、それに対す
マラソン勉強するぞ！~アルゴリズム編~ - tardigradeの競プロ日記
はじめに こんにちは、tardigradeです。本ブログでは主に競技プログラミングのマラソンコンテスト(ヒューリスティックコンテスト)についての記事を書いていく予定です。そんなに固い記事を書くつもりはないので、のんびり気楽に読んでいただければ幸いです。 本記事が初投稿になります。 自己紹介 名前は「tardigrade(たーでぃぐれいど)」です。「くまむし」の英訳から来ているので、「くまむし」とか「くま」と呼ばれることもあります。競技プログラミング歴はおよそ1年、2021/03/02時点でAtCoder緑です。 AHC001が開催されるぞ～！！！ 今週の土曜日、3/6から3/14まで、「AtCoder Heuristic Contest 001」が開催されます。マラソン用の新しいレーティングも整備されるということで、とても楽しみです(*ﾟ▽ﾟ*) ところで、僕はあまりマラソンの経験がありま
今日から使えないビット演算（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手ぐらいまでにな
TCO10 Marathon Round 3 - てきとーな日記
Subgraph Isomorphismする問題 暫定8位だけど、おそらくシステムテストで順位が超入れ替わると思われるので安心出来ない 通過できてるといいなぁ 戦略上重要なこと スコアが絶対評価なので、点が稼げるところで一気に稼がないといけない 難しいケースは頑張っても20〜40点とかそれくらいの点数しかとれないのに対し、簡単なケースは300点以上取れる forum情報だと１ケースで2600点とった人までいるとか… このことに終盤で気づいたので、そっからは点数低いのをあげようとするのをやめて、点数高いやつをさらに高くするために頑張った 基本的な方針 基本的には全探索するだけ まず最初に、H(小さい方のグラフ)の頂点の順番を固定し、その順に探索を行う 固定せずに、候補数の少ない点からやったほうがよさそうな気がするが、候補数の計算に時間がかかる、ちょっと先の方に難しい場所があってもそっち方法に
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
AHC035解説
https://x.com/eijirou_kyopro/status/1753041794617823445?s=12&t=YpIPcsjKfoTpmECNdRL-uw
GitHub - kera6rhy/codevs_reborn
GitHub - piroz95/CodeVSReborn
2013 TCO Marathon Round 2 (yowa)