焼きなまし法

※今回の記事は専門じゃないことを記載しているので、間違いがあるかもですが、その際はコメントいただけると幸いです。 さて、今更感がありますが、東芝のSBMなるソルバーを使ってみました。 www.global.toshiba このSBMというのは量子コンピュータ（イジング方式）が得意な計算を 普通のコンピュータでできるようにしてみたアルゴリズムのことだそうです。 イジング方式は組み合わせ最適化問題が得意（超早い）ということで 実用性はいったん置いておいて、とりあえずポートフォリオ最適化を 整数計画にアレンジした際のやり方をメモしました。 ノリ的にはalpacaさんがarXivにあげている以下の論文…

真面目にマラソンに取り組むのは初めてでしたが、やってみると結構楽しいですね。 留年が決まって何もする気が起きず、とにかく暇だったので集中して取り組めました。 留年の話は気が向いたら書きます。 先日開催されたAHC001に参加し、最終スコア989,360,207,620点、順位は32位でした。 コンテスト中に考えていたこと、やったことをだいたい時系列順に書いていきます。 問題概要 atcoder.jp やったこと まずは正の得点を得る（823,090 点） 大事です。 入出力形式を理解できているかの確認は重要なので、簡単な解で試します。 ちなみに私は、初回の提出で配列の長さが足りずにREを出しま…

pic.twitter.com/ELVX3lR1Ty — kr (@kryInit) 2021年3月25日 5秒で約2e6回まわるループの中で、1000回に一回書き出し、(おそらく)60fpsで描画したものを画面収録。 はじめに おや、もしやあなたはコンテスト参加中の私ではないですか？ であればこちらを見ると良いかもしれませんね。 そうではないあなたは・・・ご自由にゆっくりしていってください。 考察(過程) ヒューリスティック系の問題を考える時、まず最初は自分が手でやるならどんなふうにやるかを考えます。 一番初めに思い浮かんだことは、(皆さんはpower pointなどに画像を貼っている場面を…

2021/3/6-2021/3/14に開催されたAtCoder Heuristic Contest 001に参加しました。 atcoder.jp 普段は、いわゆるマラソン系のコンテストに参加することはありませんでしたが、今回は記念すべきAtCoderヒューリスティック系の第1回目という理由のみで、参加をすることにしました。 ちなみに、私がAtCoderを初めたての頃、ヒューリスティックコンテストの入門編コンテストが開催されて参加はしたのですが、結局0点で終了という残念な結果しか残せませんでした。 devgenjin77.hatenablog.com よって、今回は少なくともまともに得点を取ると…

競技プログラミングコンテストサイトである AtCoder のマラソン部門のコンテストに参加してみました： atcoder.jp 本記事では、コンテスト参加者の使用しているプログラミング言語はどういうものがあるのかを順位から調査してみました。

AtCoder Heuristic Contest 001 (AHC001) の参加記を書くはずだったのですが、記念すべき第1回ということで「マラソンに初めて参加したけど、感想戦TLで周りが何を言っているか分からない……。」という方が多そうな気がして、気付いたら初心者向け解説記事*1を書き始めてしまっていました。 ふぁぼ圧、強すぎませんか https://t.co/DuGViXzI80— TERRY (@terry_u16) 2021年3月15日 参加記はまた後日書きます。→書きました。 www.terry-u16.net 問題概要 はじめに 正の得点を得る（823,090点） 山登り法を導入…

今までHTTF、ハル研プロコン、AHC、などのマラソン型競技プログラミングコンテストに参加してきました。初参加から一年以上が経ったでしょうか。個人的には普段のアルゴと呼ばれる分野のコンテストよりマラソンの方が向いている(相対的な順位がよい)と感じており、比較的力を入れてきました。 本記事では、マラソンに取り組むときに考えていることを自分の振り返りも兼ねてまとめます。 短期型では制限時間以内に実装できる範囲の中で得点の期待値が高そうなものを選ぶことが重要になりますが、今回は長期型、2週間ほどのコンテストにおける戦略にフォーカスします。 有名問題との類似性 最も簡単な解 単純な貪欲 山登り法 その…

03/08(月) 先週日曜日はWriteUpをいくらか書いたら力尽きた。コードゴルフ大会中は週記を書く作業もストップしていたが、溜めてしまったものを書いて投稿する気力もなく、午前7時に就寝。 午後7時に起床。まだ眠かったので再入眠し、結局午後11時半まで寝た。これでもまだ眠い気がする。寝すぎただけかもしれない。 まずWriteUpの残りを書いた。次に、先週の週記を完成させつつ、タイミングを見失っていたICPCチーム紹介ドキュメントに関連する記事を投稿し、模擬地区予選に関する記事も書いて投稿した。 kotatsugame.hatenablog.com kotatsugame.hatenablog…

これはAtCoder Heuristic Contest 001に参加した記録です。 最終段階で48,919,878,271点、暫定順位は120位でした。 動画 pic.twitter.com/wJlg25nbiR— ぬるぬし (@00nuushi) 2021年3月14日 コンテストのトップページ atcoder.jp やってみるまでは学会前だしそんなにやらないだろうなと思っていたのですが、あまりに楽しいので空き時間はAHCのことを考えない時間がないくらいには取り組みました。あまりマラソン型コンテストは参加したことありませんでしたが、AHCは今後もやっていきたいなと今は思っています。

楽しい

AtCoder Heuristic Contest 001に参加した！技育祭でchokudaiさんが「ヒューリスティックスコンは自分の書いたプログラムを育てるのが楽しい」のようなことを言っていたけれど、かなり実感した。 atcoder.jp 一週間のうち、最初の3日と最終日にがっつり取り組んだ。ICPC模擬地区があったり、技育祭が三日間あったりで取り組んでない時間のが長かった。 システス前46,877,146,209点で431位。 やったこと 一日目 二日目 三日目 最終日 自分用人々の知見まとめ hakomoさん TERRYさん TERRYさんによる初心者向け解説 takumiさん じろうさ…

AtCoder Heuristic Contest 001 - AtCoder Heuristic Contest の初開催おめでとうございます。 楽しませていただきました。 seed: 1 方針 greedy に初期解を求め、少し山登り法をします 実行時間の前半、 1. を繰り返しそのうちの最良解を後半の初期解とします（多スタート） 後半、「キック近傍+少しの山登り」を近傍とした山登り（これは少しではない）をします 山登り法 広告の位置サイズを変更して良くなっていたら遷移する、ができるので焼きなまし法系だなあと思います。 近傍 1: 広告 1 つを最適化 要素を 1 つ 2 つ変えるというの…