最適化問題のアルゴリズムの1つ。
こんにちは、yatabis です。 今回 AHC012 に参加したので、やったことなどを書き残しておきます。 AHC012 は 4時間の短期コンテストでした。 4時間というのは Heuristic の問題を解くには短く、スピード感がとても大事になると思っています。 ABC などより時間が長くて大変なのですが、それでも時間いっぱい使わないと間に合わないことがほとんどです。 また、多くの人が時間いっぱい使っているため、長期のコンテストに比べて費やす時間に差が出にくく、より経験や実力がダイレクトに反映される気がします。 さて、結果ですが、90.0M のスコアで 105位で終了しました。 今回で He…
どうも、かわばっちゃんです。 今回はボルツマンマシンについて紹介します。 ボルツマシンとは ディープラーニングで使われる手法です。 ディープラーニングでは入力層、隠れ層、出力層で構成されます。 隠れ層というのは入力層と出力層を除く中間の層です。 ディープラーニングでは人工ニューラルネットワーク（ANN）という複数の層によって構成され、その層の中にある複数のニューロン一つ一つがその他ニューロン全てと繋がるような形になります。 ボルツマンマシンでは入力層、隠れ層、出力層のニューロンそれぞれが0もしくは1の値を持ちます。 そして、ボルツマンマシンの目的は、全てニューロンのエネルギーを最小とすることで…
RECRUIT 日本橋ハーフマラソン 2022夏（AtCoder Heuristic Contest 013）に参加しました。 1位でした！ 問題 atcoder.jp はじめに 「コンピュータ」だと長いので「PC」と呼びます。 解法 PCの移動経路を変更する焼きなまし法で、PCの接続はBFSで行いました。 処理の流れ 状態の初期化 焼きなましループ：(a)～(c)を時間いっぱい繰り返す(a)状態を少し変更してみる(b)状態を評価する＝評価値算出(c)状態の採用判定 一番スコアの高かった状態の移動と接続を出力 1.状態の初期化 プログラムに入力された情報で状態を初期化します。 状態は以下の情報…
はじめに AtCoder Heuristic Contest それは「絶対の正解がある問題をなるべく早くなるべく多く解く」勝負であるアルゴリズムコンテストとは毛色が異なり、AtCoder公式の言葉を借りれば「最適解を出すことが難しい問題に対し、出来るだけ良い解を作成する」勝負になります。 したがって、アルゴコンでは使うことのない「焼きなまし法」や「ビームサーチ」などのヒューリスティックなテクニックが必要になりますが、残念ながら現時点で私はそれらについて理解できておらず、コンテストで使えるレベルには程遠いです。 いつかはヒューリスティックな手法も使いこなせるようになりたいところですが、今回のAH…
自己紹介 大学三年生です．アルゴの方は結構やっていて，現在黄色です．ヒューリスティックは今回が初めてでした．焼きなましとかビームサーチとか何も知らない状態での参戦でした． 考えたこと/やったこと ヒューリスティックで戦う方法を知らないので，とにかく貪欲にやりました．考えたこと/やったことを順番に書いていきます． まず，1 色のコンピュータ 100 台をすべてつなげるとその時点で 4950 点がもらえてかなりお得だなと感じたので，それを達成する方法を考えました．とはいっても移動できる操作回数が限られており，特に遠くにある 2 つのコンピュータをの接続をどうするか非常に悩みました．しばらく考えて，…
こんにちは。競技プログラミングのコンテストに参加しているyunixです。 最近行われたAHC012に参加して33位でした。 コンテスト中にやったこと、考えたこと、やればよかったことなどを書いていきたいと思います。 この記事の内容 AHC012の概要 解法 学びを得たこと
あいねむと申します。 長期AHCが大好きで、色んな方に取り組んでもらいたい気持ちがあり、少しでもハードルを下げられたらと思い、誠に僭越ながら解説記事を書かせていただきます。 問題 ざっっっくり説明すると、16種類のピースがあるスライドパズルを動かしてできるだけ大きな(=頂点数の多い)木を作ろう！ もし全てのピースをつなぐ木を作った場合、作った早さも得点になるぞ！ 問題文 atcoder.jp 最初に浮かんだアイデア ①山登り １操作では点数が変わらず、７操作だと変わる 空きマスを上下左右に1マス動かすことを1操作と考えると、1操作だけではスコア（盤面がもつ最大の木）が変化しないことが多い 7操…
AHC011に参加しました。 atcoder.jp 問題はSliding Tree Puzzle。 スライドパズルの問題です。 得点は37.4Mで理論値の75%弱。 登録4073人、提出961人中、59位でした。（暫定テスト62位） 問題 木（グラフ的な意味で）が書いてるスライドパズルを完成させてね。 完成した場合は手数が少ないほどいいよ。 考察（初期） 基本はデカい15パズル。 同じパネルが複数あるのと、木が成立さえすればいいので解が複数ある。 MM120前後に似た問題があったような。あれは回転だったか。確か端から順に作っていって、探索が利くサイズになったら探索という解法がメジャーだった。こ…
TL;DR pythonのsimannealパッケージを使うと一瞬で実装できるます． 作ってくれた人ありがとうます． 背景 ラボメンに，遺伝子パーツの選択の相談をされた． 30種くらいの遺伝子パーツの中から，10個くらい良さげなペアを選んでほしいとのこと． 各々の遺伝子パーツは，入力分子とそれに応答する素子で構成される．応答素子は対応する入力分子以外にも応答する可能性があるため，この応答交差性を最小限にするようなパーツの組み合わせを選択したいという問題になる． 選択基準としては，遺伝子パーツ間の距離が定義されていて，選択したものの間の距離の最小値を最大にするというタスクになりそう． ここcs.…
読み流した論文のメモ。黒色はメモ、緑色は感想、赤色は特に面白いと思ったもの。32報 Synthetic Biology Transcription/Translation Control RNA Synthetic Biology Cell-free / Reconstruction Optogenetics Protein Engineering CRISPR/Cas Metabolic/Signal Pathway Engineering DNA / Biophysics Alternative Hosts / Strain Engineering Miscellany Computati…
ALGO ARTISプログラミングコンテスト(AHC010)に参加しました。 結果は1位/1400人*1で、優勝でした。初優勝なのでとてもうれしいです。 #AHC010 優勝しました！！！！！！！ pic.twitter.com/9uyghQy1dE— takumi152💉💉💉 (@takumi152) 2022年4月24日 ということで、以下に今回の解法や感想について書いていきます。 問題 解法（簡易版） 解法（もっと詳しく） 乱択DFSによるループ経路の変更 曲線(1)レールの場合 曲線(2)レールの場合 直線レールの場合 その他 焼きなまし法 解の持ち方 初期解 状態遷移 評価関数 結果…
第8回 Asprova プログラミングコンテスト お疲れ様でした。 暫定テストでは得点率99.2536%で2位、システムテストでは得点率99.2106%で4位でした。 問題概要 円環状に繋がったコンベアの生産スケジュールを組む問題です。 何種類かの製品があり、作る製品を変える間は別の製品を作ることができません。また、同じ形状の製品は同時に一定数までしか作ることがきません。 スケジュールの長さと作業員の手間の両方を最小化します。2つの指標の優先度はテストケースごとに異なります。 円環状というのが特徴的で、周期をフックの数に合わせることで作業員の手間が減るようになっています。 方針 1色ずつ順番に…
Seed=0 の出力 AtCoder Heuristic Contest 002 の解説です。 コンテスト中は2,786,732点で380位、コンテスト後は6,019,141点で6位相当のスコアを出しました。ここではコンテスト後の解法を紹介します。 紹介する解法は一例です。もっといい解法があると思います。 問題概要 マスのグリッド上にタイルが敷き詰められています。各タイルは のいずれかの大きさです。各マスには得点が設定されており、そのマスを通ったときに得点を得ることができます。 からスタートするような経路で、各タイルをたかだか一度しか通らないもののうち、得点ができるだけ高いものを求めてください…
Seed=0 の出力 (turn=850) Recruit 日本橋ハーフマラソン 2021 A問題 の解説です。 A問題について、コンテスト中は311,660点で17位、コンテスト後は346,841点で1位相当のスコアを出しました。ここではコンテスト後の解法を紹介します。 問題概要 長さ の配列 が与えられます。 とします。 を自由に選んで を のように更新する処理を最大 回まで行えます。 の値をできるだけ小さくしてください。 方針 最初の 回で をできるだけ小さくし、最後の 回で全ての要素が小さくなるように調整しました。 優先度付きキューを用いた、ある種の貪欲法で処理しました。 なお、この解…
Seed=0 の出力 京セラプログラミングコンテスト（AtCoder Heuristic Contest 006） の解説です。 コンテスト中は1,764,699点で57位、コンテスト後は2,110,386点で10位相当のスコアを出しました。ここではコンテスト後の解法を紹介します。 紹介する解法は一例です。もっといい解法があるかもしれません。 問題概要 デリバリーサービスを題材とした問題です。 注文が1000件入っており、 番目の注文は にあるレストランから への配達依頼です。移動にはマンハッタン距離の分だけ時間がかかります。また、任意個の料理を同時に運ぶことができます。 50件の注文を処理で…
絶対に勝てない6x6リバーシを作りました。あなたは黒番、AIが白番です。 絶対に勝てない6x6リバーシを作りました！ ぜひ挑戦してみてくださいhttps://t.co/Ul5n3q9jMp— Yusuke Endoh (@mametter) December 30, 2021 これは何？ 6x6の盤面のリバーシは後手必勝 *1 であることが知られています。 このAIは白番（後手）で完璧にプレイします。つまり黒番のあなたは絶対に勝てません。無力感を楽しんでください。 技術的な話 このAIはWebAssemblyになっているので、全部あなたのブラウザの上で動いてます。真のサーバーレスです。 AIの…
ja.wikipedia.org
shindannin.hatenadiary.com
ja.wikipedia.org
www.colun.net
zellij.hatenablog.com
jetbead.hatenablog.com
gasin.hatenadiary.jp
qiita.com
oumpy.github.io
