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」が開催されます。マラソン用の新しいレーティングも整備されるということで、とても楽しみです(*ﾟ▽ﾟ*) ところで、僕はあまりマラソンの経験がありま
Kyopro Encyclopedia of Algorithms (ア辞典)
これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /#noredirect を利用してください。 これは競プロの知見を収集するための査読付きの半共有 wiki である。 アルゴリズムについての説明が中心となっている。なお、データ構造については scrapbox.io/data-structures (通称: デ wiki) を利用するのがよいだろう。 個人ブログの記事として情報を書くと属人性が高すぎ、古い記事のメンテのコストが高く、記事が不正確なまま残りやすいという問題があった。一方で誰でも自由に編集できる共有 wiki であると属人性が低すぎ、誰が書いたのかが分かりにくいため適切なクレジットが行なわれず、また記事の正確性も担保されな
高度IT人材が物流業界の「配送ルート最適化問題」を解く | ウェブ電通報
競技プログラミング界のキーパーソンであるAtCoder社長 高橋直大氏と共に、優れたアルゴリズム開発能力を持つ「高度IT人材」の育成・採用について考える本連載。 今回は、「世界のラストワンマイルを最適化する」というミッションを掲げるスタートアップ、オプティマインドの社長・松下健氏と高橋氏の対談を実施しました。 「どの車両が、どの訪問先を、どの順で回ると最適か」を提示する、ラストワンマイルのルート最適化、いわゆる「配送計画問題」は、学問として長年研究されているテーマであると同時に、物流業界にとっては事業に直結する問題です。 トヨタ自動車などから10億円を超える資金調達をするなど、注目を集めるオプティマインドの取り組みと、高度IT人材が物流業界でどう活躍できるのかを、二人に熱く語っていただきました。 「組合せ最適化」との出合い。これは社会課題を解決できる研究だ！ 高橋：競技プログラミングの世界
逆元と剰余演算 | なかけんの競プロノート
$p$ を素数とする。整数 $a$ が $p$ と互いに素なら、次が成り立つ。\\[ a^{p-1} \\equiv 1 \\pmod p \\] この式を変形すると、\[ a\cdot a^{p-2} \equiv 1 \pmod p \]となります。これは、 $\bmod p$ の世界では、 $a$ と $a^{p-2}$ を掛けると $1$ になる、ということです。 一般に、 $a$ にある値を掛けて $1$ になるとき、その値のことを $a$ の逆元(inverse element) といいます。逆数と似ていますが、逆数は数の掛け算での話をしているのに対し、逆元は $\bmod$ の世界も含めた、もっと広い世界での話をしています。逆元は、逆数を一般化したもの、ということもできます。 逆元と剰余演算の具体例 さて、ここからは具体的にコードを書いてみます。まず、次の問題を見てみましょう
LINEの新卒採用試験ズバリ問題解説～アルゴリズム問題編～
LINE株式会社は、2023年10月1日にLINEヤフー株式会社になりました。LINEヤフー株式会社の新しいブログはこちらです。 LINEヤフー Tech Blog (2月5日 16:30追記) SNS等で多くのご指摘をいただき、再度掲載していたコードや表現について社内で議論いたしました。それを踏まえて以下の通り、補足および訂正させていただきます。 エラトステネスのふるいの実装方法については、高速化のための実装ではなく、アルゴリズムなどの勉強をしっかり行ってきたか、ということを示すための1例として紹介しましたが、あたかも高速化を目指したコードとしての例示となり、誤解を招く表現でした。上記の意図を明確にするために、本文中に高速化するための実装ではないことを明記しました。 また、"個性がない"という表現も、上記と同様に"アルゴリズムなどの勉強をしっかり行ってきたという実績や経験がコードから判断
プログラミングは楽しくて仕方がない! 世界三大権威の競技プログラミングコンテスト「AtCoder」を運営する高橋直大氏インタビュー
プログラミングは楽しくて仕方がない! 世界三大権威の競技プログラミングコンテスト「AtCoder」を運営する高橋直大氏インタビュー 8月27日(木)、「Codeforces」(ロシア)、「Topcoder」(米国)と並ぶ、世界三大権威の競技プログラミングコンテスト「AtCoder」を運営するAtCoder株式会社の高橋直大社長に、オンラインインタビューを行った。 AtCoderをはじめとする競技プログラミングとは、問題の採点方法が事前に示された上で、全員が同じ問題を解くためコーディングを行う。「実際のプログラミング技術」に基づいて点数が付けられ、獲得した点数で順位が決定する。 一方、中高校生向けに開かれているTech Kids Grand PrixやU-22プログラミング・コンテストなどを代表する一般的なプログラミングコンテストでは、社会的課題に対するアイデアをプログラミングし、その成果物
文系でもプログラミングはできる。実技コンテストを主宰する社長に聞いた | bizSPA!
IT技術の発展に伴いIT人材（システムエンジニアやプログラマーなど）の需要が年々高まっているのにもかかわらず、IT人材不足が深刻だ。経済産業省によれば、2030年には実に45万人ものIT人材が不足するとの試算が出されている。 世界的に見れば、米国のGAFA（Google、Apple、Facebook、Amazon）や中国のBATH（Baidu、Alibaba、Tencent、Huawei）などの世界経済を牽引するIT企業を中心に、人材獲得が激化している状況だ。 いかにIT人材を確保するかが、日本の産業活性化に繋がると言っても過言ではない。そんななか、プログラミングスキルをコンテスト形式で評価する「競技プログラミング」の存在が注目を集めている。 今回は、世界3大競技プログラミングコンテストのひとつである「AtCoder」を運営し、数々の競技プログラミングコンテントで優勝経験を誇る、AtCod
高校生がアルゴリズムとスパコンの力で、京都の碁盤目状道路を13.9%効率化した話 - Qiita
2. 本研究で解く問題 「いざ研究しよう！」と思っても、条件や設定を決めないと何も始まりません。 まずは研究を分かりやすくするために、「一つの問題」に落とし込むことにしました。 問題設定 縦 $N$ 行・横 $N$ 列の大きさの碁盤の目があります。隣り合う交差点間の距離は 1 です。つまり、交差点が合計で $N^2$ 個あり、それぞれ座標 $(1, 1), (1, 2), ..., (1, N),$ $(2, 1), (2, 2), ..., (N, N-1), (N, N)$ に位置すると考えることもできます。 下の図は、$N = 4$ の場合の交差点の位置です。 あなたは、碁盤の目の交差点の位置は変えずに、道路の並びのみを変えることができます。上手く道路の並びを変えることで、できるだけ「便利」な道路網を建設してください。 「便利な道路網」って何？ 私は、以下の 2 つの条件を満たす道路
プログラミングスキル判定サービス「TOPSIC」を通じてアルゴリズムを学ぶ～立教池袋中学校・高等学校 数理研究部の挑戦
プログラミングコンテストで数々の実績をもつ同校がなぜTOPSICを始めるに至ったのか。その背景からアルゴリズムの重要性まで、数理研究部顧問の内田芳宏教諭、TOPSICを運営するシステムインテグレータ代表取締役社長の梅田弘之氏、TOPSICの問題作成を手掛けるAtCoder代表取締役社長の高橋直大氏に話を伺った。 左からシステムインテグレータ梅田弘之氏、立教池袋中学校・高等学校 内田芳宏教諭、AtCoder高橋直大氏 設立47年の実績ある数理研究部 東京・池袋の立教大学の並びに建つ立教池袋中学校・高等学校は、立教大学をはじめとした有名大学への進学率も高く、中高一貫の名門校として人気を誇っている。クラブ活動の豊富さも特徴で、中でも1971年に設立された数理研究部は、歴史と伝統のある部活動の一つだ。 「数理研究部が始まった1970年代はまだ高等学校は設立されていなかったため、中学校しかありません
数学オリンピックの問題にプログラミングで挑戦！ ～数え上げから幾何問題まで～ - Qiita
1. はじめに はじめまして！高校 2 年生の square1001 です。 私は主に「競技プログラミング」に取り組んでいます。情報オリンピックの世界大会の日本代表になったり、TopCoder や AtCoder などのプログラミングコンテストにも出場したりしています。コンテストに出場するだけでなく、問題の作成も積極的にやっています。 ところで、みなさんは、「日本数学オリンピック」という大会を知っていますか？これは、日本全国の高校生以下を対象にした、数学の問題解決能力を競う、全国的にとても有名な大会です。本記事では、日本数学オリンピックの予選で出題される問題を、難しい数学的知識や数学的考察を使わずに、「コンピューターの高い計算能力」と「アルゴリズムの力」でチャレンジしてみます！ 導入 - コンピューターが世界を変えた！ プログラミングを実務などでやっている方の中には、「システムやアプリケー
アルゴリズムと数学的思考力 - 怠惰を求めて勤勉に行き着く
厳しい。年始早々厳しさを感じている。自分のプログラミング力にだ。伸び悩んでいる。 端的に言って、数学力のなさが自分のプログラミング能力に制限をかけている。例えばこの問題。 560. Subarray Sum Equals K 入力として与えられる配列 nums のうち、合計が k となる部分配列の個数を数え上げよ。どうも有名な問題らしいが… まず大前提として、部分配列なので i, j の2重ループで始点・終点を定めて sum(nums[i, j]) = k になるものを数え上げれば必ず答えが得られる。最悪計算量は O(N^3) ただし i < nums.length < 20000 という制約があるので N^3 では遅すぎるから何か考えてくださいというのがスタート地点。 ここで、結果の変わらない累積和を何度も求めているので nums[i, j] = k を求めたい場合、 nums[0, j
競プロでWAが出たときのランダム入力データ生成入門 - ARMERIA
概要 競技プログラミングで提出コードがWAになったとき、実際に不正解となるような入力データを入手できると役に立つ場合があります。ただ多くのコンテストサイトでは、コンテスト中には入力データを見ることはできません。 そのような時に、小さめの入力データを乱数で大量生成して、提出コードと愚直解法の結果を突き合わせ、答えが一致しないものを探すという方法があります。もちろんそのようなデータを確実に得られる保証はありませんが、もし見つかればデバッグの大きな助けになります。 今回の記事はその手順を紹介します。また、生成コードの例としてC++とPythonを扱います。 手順1：愚直解法コード作成 まずは問題に対する愚直解法のコードを書きます。小さな入力データで回すので、 だろうと だろうと気にせず書きましょう。これがバグっていると破綻するので計算量よりも正しさ優先です。 C++等の場合はコンパイル時に提出コ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
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