焼きなまし法

ドイツのzib研究所の設立者であられるマーティン・グレッシェル先生は、しばしば講演でクイズを出されます。以下はその抜粋です。回答は生成AI（Gemini 2.0 Flash Thinking Experimental）に作ってもらいました。 最初の整数方程式系は？ 最初の整数方程式系を考えた「人」を特定するのは非常に難しい問題です。なぜなら、数学の歴史は長く、アイデアは徐々に発展していくものだからです。しかし、いくつかの重要なポイントを考慮することで、より良い理解が得られます。 初期の段階: 古代バビロニア: 紀元前2000年頃の粘土板には、複数の未知数を含む連立一次方程式を解く問題が記録され…

はじめに NearMeの相乗りサービスの特徴として、事前予約の注文が入るたびに相乗りの最適化を行っているという点があげられます。 これは、特定の時間で締め切りして一気に相乗りを決めるという素朴な方法に比べると、 相乗り状況が事前に把握できることで配車手配しやすくなったり、直前まで最適化できたりするといったメリットがあります（参考１、参考２）。 一方で、最適化の観点では、注文のたびに最適化しようとすると計算リソースが限られてしまうので、妥協した解に留まる可能性あります。 特に、現実装では計算量を減らすため、入ってきた注文に対して時間的・空間的に近しい注文同士で再計算していますが、 その場合、部分…

2024年12月9日(月) 18時頃に起きたのを覚えている。JOIによる精神の疲弊がだいぶ効いていたらしい。いや寝れたのが朝になってたというのが大きいのだが。正直まともなことは何もしていなかった。言葉にするなら自暴自棄が似合うと思う。一応ボーダーは通っているのではと思っているので動画用のプロッド的なのを作成して後はゲームをしていた。眠かったのでさっさと寝ようと思ったのだがYoutubeを見ていたら、「Mouthwashing」というゲームの解説を見てしまった。チャンネルが「鬱ゲー解説」みたいな名前だったので、あんまり見ない方がいいなと思いつつも開いてしまった、視聴後自暴自棄の行動の全てを後悔し…

この記事は、MMA Advent Calendar 2024 2日目の記事です。 こんにちは。dyktr_06 です。 今回は、Heuristic Contest のススメということで、AtCoder Heuristic Contest が面白いので布教しよう！というモチベーションで記事を書き始めました。 この記事は、主に以下のいずれかに当てはまるような人向けに書いています。 Heuristic Contest が気になっている AtCoder Beginner Contest などの Algorithm のコンテストには参加したことがあるが、Heuristic のコンテストには参加したことが…

(1)ヒューリスティックの問題を解くことが、楽しいと思えるか。 (2)突発性難聴の後遺症で平衡感覚が狂っている中で、長時間の実装ができるか。 (3)土日をヒューリスティックのコンテスト参加に使って、体力がもつか。 そもそも、(1)が結構怪しい。 焼きなまし法やビームサーチなど、基本を知らずに数年前に1度コンテストに参加したが、正直問題を解いていて面白いとは感じなかった。 ほとんど仕事の感覚だった。 基本を知って、数理最適化の勉強がある程度進んで、そこで自分が楽しいと思えるかどうかは、やってみないと分からない。 過去問を本番のつもりで解いてみるのが良さそうだと思う。 (2)については、某痛み止め…

11月4日(月) 10年前の小学生の時代から長らく使い続けていたカーテンを買い替えることを決め、ニトリに向かった。家を出る前に欲しいカーテンのサイズを測っており、これを買えばいいかなというのは決まっていたがその日買うつもりはなく店を出る。その後現在通っている高校の一個前の母校に寄ってみたくなり向かう。3年前の自分は毎日を耐え忍ぶことに手いっぱいで、駅周辺を散策したり近くの川を楽しむことなく退学したため、母校に通っていた人達はどんな景色を見ていたのか気になり見に行った。その川は多摩川というのだが川の道路に上がった瞬間に美しい景色が視界に入ってきて驚いたのを覚えている。まちカドまぞくのアニメで多摩…

問題 問題概要 マスの床に または のタイルが敷き詰められている。 同じタイルは 2 回以上踏むことはできず、各マスごとに踏むことで得られる得点が決まっている。 上下左右に好きな回数だけ移動し、通過したマスに対応する得点の総和を最大化せよ。 やったこと 4 方向のうち移動できるマスに移動するという DFS を時間の許す限り繰り返す→3865159点 ここで面白かったのは、探索順をランダムにするとスコアが下がってしまうということだった。おそらく方向を偏らせることで開始マスから遠いところに行けるため、広いスペースを使えるのではないかと考えている。 上の DFS を 1500 ms くらい行って発見…

去年はチーム Takenoko (17 + ytqm3 + Cyanmond) で出たが、今年はチーム Calamari (17 + Cyanmond + shiomusubi496) で出た。この名前は、使うスパコンが SQUID という名前でこれはイカの意味があるらしいので、英語でイカ料理を表す Calamari を提案したところ他に案がなく決まった。 1 日目 この日は鉄緑会の校内模試があったようなので、後半は自分が回収した。どちらにせよ初日はスパコンまで到達しないので、深夜労働などをしてもらった。 問題概要を把握した。問題としては、 森林火災のモデルがある 初期状態が与えられる。具体的…

前提 この記事でいう「H」は、ヒューリスティック(Heuristic)の頭文字をとったものです。 決して卑猥な意味ではないということを念頭に置きながら、お読みいただけると幸いです。 Prologue お久しぶりです。UnionFind教信教者ことまっちゃラテ🍵です。 いつもABCに本気になりながらレートが全く増えずに泣いていた(実際は泣いていません)私が！！ 今回、AHC036に参戦しました。気分転換替わりです。 (いや、レート減らないっていうから...！！) AHC参加者さんたちは必ずといっていいほど記す「冒険記」を、パクr 参考にしながら、個人的な情緒を勝手に混入させながら記そうと思い、こ…

まず前回のシーディング記事 大型大会のシーディングについてのこの一年の思考 - jak_amano’s diary からシーディングにおいて認識していた課題は以下となります。 直近の対戦を考慮してシーディングすること 強さ順にシーディングすること オンライン強豪の考慮 古豪の考慮 関東関西とそれ以外の地域の差の考慮 海外勢の強さ推定 国内選手の海外大会遠征結果の反映 このうち、オンライン強豪の考慮（スマメイトのレート考慮やオンライン大会結果の考慮）については、オフ大会のみ考慮すべきという現行に対して強い異論が見当たらなかったため特に対応しておりません*1。 篝火12においてのシーディング方式説…

前回の記事ではCTから顎骨・歯のSTLデータを切り出しました。 lacramy.hateblo.jp このデータを活用するため、今回は口腔内スキャンのデータとの重ね合わせをしていこうと思います。 マッチング（重ね合わせ）とは？ STLデータについて軽く説明 形状と座標 どうやって重ね合わせているのか（脱線） Medit designを使ったマッチング Medit linkの登録 Medit linkのインストール Medit designのインストール データの取り込み 患者の登録 ケースの登録 サンプルファイル データの取り込み medit designについて medit designの起…

ALGO ARTIS プログラミングコンテスト2024 夏(AHC035)に参加しました。 atcoder.jp 問題名はBreed Improvement。穀物の交配シミュレーションでした。 結果は提出1024人中9位で、短期AHCでは最高記録。 問題 ビジュアライザ(各作物の評価項目のレーダーチャート) 6×6の畑に種を植えてね。 隣接した作物同士でそれぞれ新しい種を作るよ。 新しい種を作るときは、15項目の評価項目をそれぞれいずれかの親から各50%で引き継ぐよ。 10回のサイクルで至高の種を1つ作ってね。 考察 この問題の元ネタは…アストロノーカじゃな？*1 遺伝時の引継ぎは評価項目ごと…