競技プログラミング

はじめに 実装中心で．テンプレは別記事．

AtCoder Heuristic Contest 044お疲れ様でした。149,801,634点で2位です。やったー！ 今回も軽めに解説記事を書いていきます。 ビジュアライザ (seed=0, score=998,314点) 問題概要 解法 概要 解の持ち方 評価関数 近傍 コンテスト中の立ち回り 問題文を読みつつ環境整備（～0h07m） 雑焼きなましを実装（～0h23m） 2点swapを実装（～0h28m） 考察とリファクタ（～1h24m） 近傍の改善（～1h59m） 温度バグ修正（～2h09m） パラメータチューニング（～3h38m） 感想 問題概要 いい感じに掃除当番を決めてね。 at…

問題G - Maximize Distance解法問題の言い換え答えで二分探索することを考えると、頂点 から頂点 への最短距離を 以上にする場合に重みを変更する辺の本数の最小値を求めることになる。 値 燃やす埋める の場合頂点 からの最短距離が である頂点集合と である頂点集合に分割し、異なる集合に属する頂点を結ぶ辺の本数を最小化する問題に帰着できる。 これは最小カット問題そのものである。 燃やす埋める問題は最小カット問題に帰着できるが、逆に最小カット問題を燃やす埋める問題に言い換えることを考える。 頂点 の値は 、頂点 の値は 、頂点 から頂点 への辺があるとき、 の値が 、 の値が ならば…

実装中心で．テンプレは別記事．

問題文 https://atcoder.jp/contests/abc397/tasks/abc397_d 問題概要 正整数 $n$ が与えられる．正整数の組 $( x, y )$ であって，$x^3 - y^3 = n$ であるようなものを一つ報告せよ．存在しない場合はその旨を報告せよ． 制約 $1 \leq n \leq 10^{ 18 }$

実装中心で．テンプレは別記事．

始めに 問題 解法概要 他に試した解法とスコア 始めに 時間無制限でChokudai Contes 003を解きました。本番一位相当(score=7525)の解法の覚書きです。 問題 50x50サイズのマス目に〇と×と点が書かれています。点ブロックが消滅すると、〇ブロックと×ブロックは下に落下します。点ブロックを+ブロックか-ブロックに置き換えることができます。+ブロックは消滅しない普通のブロック、-ブロックはその位置に固定されるブロックです。任意の点ブロックを+ブロックや-ブロックに置き換えることで、落下後の〇の最大連結成分と×の最大連結成分の和を最大化してください。 下記は初期状態と落下後…