前回の【基礎編】*1の記事では、ビームサーチの中でも一般に広く用いられていると思われる実装例を紹介しました。基本的にボトルネックとなるのは状態のコピーであり、コピーコストを軽くしたりスコアだけ先に計算してコピーを減らすなどして高速化を図りま…

7/30 追記：一部の実装を変更して高速化しました。(ビームサーチ内で毎回配列を定義するコストが無視できなかったため、一度だけ定義して毎回中身を全て消去する形にしました) ヒューリスティックコンテストでよく用いられるビームサーチという手法がありま…

少し時間が経ってしまいましたが、先日 yukicoder score contest 6 を開催させていただきました。今回はテスターは yunix さんにお願いしました。 優勝者は terry_u16 さんでした、おめでとうございます！ 問題概要 縦スクロール型のシューティングゲームを…

ヒューリスティックコンテストでは、一部の数値が与えられないタイプの問題が出題されることがあります。多くの場合はインタラクティブ形式の問題で、少しずつ与えられる情報で数値を予測していくことになります。 (例：AHC003, HTTF2022予選, HTTF2023本選,…

ABC158-F問題です。公式解説とだいぶ違う方針だったので書き残したいと思います。問題概要：数直線上に$\ N\ $個のロボットがあり、$i\ $番目のロボットは座標$\ X_i\ $にいる。各ロボットは起動すると右に$\ D_i\ $だけ動く。他のロボットにぶつかるとその…

競技プログラミングにおいて、行列演算が活躍する場面はそれなりにあります。 もちろんその都度配列を用意しても良いのですが特に行列の積の計算などは面倒で、やっぱり構造体で定義したくなりました。 二次元の行列で簡単な演算ができるように、構造体を書…

ABC171のF問題からです。このアプローチ(特に後半部分)を見かけなかったので書いてみました。問題概要：文字列$\ S\ $の好きな位置に好きな英小文字を$\ K\ $回挿入して得られる文字列は何種類あるか？ ・$|S| \leq 10^6$ ・$1 \leq K \leq 10^6$まずは小さ…

今回初めてyukicoderでコンテストを開催できました。testerの皆さん、参加者の皆さん、ありがとうございました。 難易度としては、ABCの点数で 300 - 300 - 400 - 400 - 500 - 600 くらいを想定していました。 全探索、データ構造、DPなど、色々な分野から出…

はじめまして、platinumと申します。 少し時間が空いてしまいましたが、10/10のHHKBコンテストで青コーダーになることができました。 今まで色変記事というものを書いたことはなかったのですが、皆さんの記事に刺激を受けて私も書いてみたいなと思いました。…