ポリオミノ

はじめに しばらくブログを書いてなかったのでAHC参加ネタを投稿。 先日Atcoder Heuristic Contest 030（AHC030）に参加し最終56位という結果だったが、提出した基本方針に二乗誤差を最小化する焼きなましが含まれていた。この方法では二乗誤差の計算を何度も行うことになるためその計算時間が肝になるのだが、線形代数ライブラリのEigenを使うと下手に差分計算するより愚直に全計算した方が速かったりする*1。とはいえ、少し工夫して差分計算にもEigenを活用すれば、状況によっては愚直計算よりも速くなる。 ということで、本記事では実際にAHC030で使ったEigenによる二乗誤…

今日はデイドクの日 はい、おはようございます。僕です。今日もなにか書きましょうか。さて、世の中にはデイドクなるゲームがありましてですね。 www.daydoku.com Daydokuは、カレンダーと戦略的な配置を組み合わせたデイリーパズルです。ゲームには、10個のポリミノ（テトロミノ3個、ペントミノ7個）とカレンダー（日、月、平日）が登場します。プレーヤーは、毎日、カレンダーグリッド内のすべてのポリオミノを、現在の日に対応するマスだけが見えるように、巧みに配置する必要があります。日めくりカレンダーのパズルを解きながら、問題解決能力と空間推理力を高めてください。 っていうゲームらしいです。つま…

THIRDコン2023（AtCoder Heuristic Contest 030）お疲れ様でした。2,140,937,483,257点で優勝です！長期コン初優勝なのでめちゃくちゃ嬉しいです。 今回も解説記事を書きます。 ビジュアライザ (seed=0, score=386,322点) 問題概要 前提知識 エントロピー 条件付きエントロピーと相互情報量 解法 1マス掘り戦略 複数マス占い戦略 パラメータチューニング 日記 感想 問題概要 掘ったり占ったりして油田の位置を当てて石油王になってね（そこまでは言ってない）。 atcoder.jp 前提知識 この記事は以下の前提知識を必要としています（…

・クイズの作問のために「音MAD」単体で検索してみたらパッと見た検索結果にちょっと落ち込むなど ・謎解きのチケットを買った。謎解きに行くのはいつものことなんだけど初演に行くのは初めて。評判も知らずに行くのは期待と不安が残るがもし超面白かった場合世界で初めてそれを体験した人間になる。デバッガー除いてね。 ・まぁなにはともあれ大々的に宣伝しているのでつまらないってことは無いと思います。ポリオミノパズルなど苦手な部分はあるかもしれないけど。 ・ワンタイムパスワードが7,8桁ぐらいあるの意味不明なんだけど ・ ・出前館でマック頼んだんだけどこれ黒塗り世界宛て書簡？ちなみに検索したけど完全に該当する単語…

AHC030 に参加してみて、ついでに参加記録を書いてみようと思い立った。 問題 atcoder.jp N x N マスの島に埋蔵されている油田プールの形状を答えよ 油田はポリオミノ型をしており、事前に形状と向きが判明している 掘削は確定した埋蔵量が得られるが、コスト 1 かかる 占いは指定したマスの集合の数に基づいたコスト 1/√k で合計埋蔵量を得られるが、マスの数が増えるほど情報の分散も大きくなる 単純に解く サンプルコードいわく、全セルを一度掘ってもコスト超過になることはない (0, 0) から1セルずつ掘る Score: 12_696_000_000 https://atcoder.…

解説 最終解法の概要 ざっくり埋蔵量把握 埋蔵量0位置による油田配置箇所絞り込み 埋蔵量1以上位置による油田配置箇所絞り込み 埋蔵量オーバーを加味した油田配置箇所絞り込み 油田配置可能箇所による埋蔵量0位置の確定 1マス掘り場所取得・実行 その他の工夫 提出コード 参加記 はじめに 1.問題 2.開始直後の考察 3.貪欲解 4.複数マスの考察 5.エラー率調査 6.1マス掘り戦略再検討 7.ボツになった戦略たち 8.1マス掘り戦略再々検討 9.おわりに 解説 最終解法の概要 (基本)1マスずつ掘って、油田の位置を絞り込んでいく解法です ざっくり埋蔵量把握 Mが6以上 かつ 埋蔵総量がエリア(N…

SGP Round1はハタンするわ立ち回りミスるわで全然ダメでした。 その反省を生かしてASC本選はうまくいったのでまあいいか。 気を取り直してPGPのプレビューです。久々の本格参戦ですぞ。

ども。コモノです。 この1週間、クッソ忙しいという日々を過ごしておりました...しばらくは多分低浮上になりそうですかねぇ..仕事との付き合い方というより時間の作り方を上手くならないと遊ぶ時間が取れねぇという現実に突き当たっております。 この1週間はというと、Xのタイムラインをチラ見して「(ↀωↀ)‼️‼️」となっては仕事にもどる...を繰り返しておりましたが忘れちゃならん情報もあったりした1週間。あぁ忘れないとも。先取りというか振り返りになっちゃってますが、備忘録がてら今週気になったボドゲ情報まとめます。 フロストヘイヴン 日本語版制作発表 画像引用：フロストヘイヴン【日本語版】 – CMON…

最近、実装重たい全探索問題多いね！ 問題へのリンク 問題概要 下図のようなポリオミノが 3 個与えられる。いずれも 4 × 4 グリッドにおさまるサイズであり、入力は 4 × 4 グリッドで与えられる。文字 '#' に対応する部分が与えられるポリオミノに対応する。 これらのポリオミノに対し 回転は OK 左右や上下への平行移動は OK 裏返しはなし というルールのもとで、4 × 4 グリッド内部に配置してい。下図のように、はみ出さないように敷き詰めることができるかどうかを判定せよ。 考えたこと 各ポリオミノについて 回転を加味した 通りのパターンについて 平行移動をすべて考慮する という全探索…

atcoder.jp Bondo416さんのAtCoder Beginner Contest 322での成績：888位パフォーマンス：1601相当レーティング：1468→1482 (+14) :)#AtCoder #ABC322 https://t.co/wyNXHatD9T— ボンド@競プロ (@bond_cmprog) September 30, 2023 A - First ABC 2 全探索をして一番初めに見つかったindexを答える 提出コード void solve() { int N; string S; cin >> N >> S; REP(i, N - 2) { if (S.s…

AtCoder Beginner Contest 322 - AtCoder B - Prefix and Suffix 問題文通りに愚直にやる #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define endl '\n' int main() { int n,m; cin >> n >> m; string s,t; cin >> s >> t; auto t1 = t.substr(0,n); auto t2 = t.substr(m-n); int ans = 3…

やった回: ABC322 成績: ABCD4完 / 1ペナ / 104:50(ペナ込み) パフォーマンス: 1033 何とか前回のつらみを取り返しました。 手を出せていないE問題も一応問題文は読んでいて、何となくABC317-D*1みを感じつつもそのままコンテスト終了。後で解いてみようとは思っていますが今日のところは右目が眼精疲労に因ると思われる職務放棄を始めたのでこの記事を仕上げたら寝ます。 A問題: ABC322-A First ABC 2 atcoder.jp String#byteindexを使って最初の"ABC"の出現位置を探索。 今回の制約上問題なかったので実害はなかったのだけど、…