甲斐性なしのブログ

うどんくらいしか食べる気がしない

競技プログラミング

二乗誤差を評価値とする焼きなましの差分計算をEigenで行う(Atcoder Heuristic Contest 030)

はじめに しばらくブログを書いてなかったのでAHC参加ネタを投稿。 先日Atcoder Heuristic Contest 030(AHC030)に参加し最終56位という結果だったが、提出した基本方針に二乗誤差を最小化する焼きなましが含まれていた。この方法では二乗誤差の計算を何度…

HTTFで超球面上の最適化を試してみた話

はじめに AtCoder上で開催されたフューチャー社主催のヒューリスティックコンテストHACK TO THE FUTURE2022(HTTF)に参加した*1。問題等詳細は以下を参照。 atcoder.jp この問題は大きく分けて各作業者のスキル推定と作業スケジューリングという2つの要素が…

競プロとかに使うアルゴリズム実装メモ(幅優先・深さ優先探索、union-find、最小全域木)

はじめに 以前の記事にて最短経路問題を解くアルゴリズムの実装を書きましたが、今回はその続きとしてグラフアルゴリズムの中でも幅優先探索、深さ優先探索、union-find、最小全域木問題を解くアルゴリズム2種について実装を書いていきます。 例によって、自…

競プロ関係の雑メモ 2018/9/9

はじめに 以前と同様、atcoderの400~500点問題穴埋め時のメモに加え、ABC109参加のメモです。 ARC088-D Wide Flip 区間[l - 1, r]を反転させた後、区間[l, r]を反転させると、l - 1番目の1文字のみ反転させることができる。同様に区間[l, r + 1]を反転させ…

競プロ関係の雑メモ 2018/9/1

はじめに 競プロの問題解いてて、解けなかった問題は何故解けなかったのか、何故その発想が出なかったのかを記していく自分用メモです。atcoderの400、500点くらいの問題なら、解けないなりにもボチボチ近いところまでは行けてるっていうパターンが多いので…

競プロとかに使うアルゴリズム実装メモ(最短経路探索系)

はじめに ここ1年くらい、ちまちまとatcoder中心に競技プログラミングに参加してたりします。ABCのD問題を解くのがやっとなのにAGCに突撃して爆死するってことを繰り返し続け、未だに緑コーダーです(パフォーマンスも1200前後がやっと)。こりゃまずいとい…