以前からときどき考えています。完成はしていません。基本的には距離の短いほうから探索するだけだと思うので、それを典型的な DP っぽく書いてみます。dp[v][d] := 頂点 v までの距離がちょうど d の walk が存在するかどうかとしてみます。都合で path で…

https://atcoder.jp/contests/asprocon4 に参加しました。今回の問題設定で最初に思いつく方針は第3回同様焼き鈍しなんですが、最近焼き鈍し以外の方法を試したい気持ちがあったので別の方針を考えていたらうまくいきませんでした。それで結局残り時間が少な…

https://atcoder.jp/contests/kuronekoyamato-contest2019 に参加した。登録してないと問題文が読めないみたいですが。 問題1 クエリ数がまあまあ多いので全点対間最短距離だと思い、有向グラフを作って Warshall-Floyd をした。頂点数 2000 ぐらいにしかな…

第3回 Asprova プログラミングコンテストに参加しました。1位だったようです。最後にパラメータをいじって数回提出したら900万点ぐらい上がってしまった結果なので、3位から上のスコアに本質的な差を感じられず、その点は運がよかったなあという感想になりま…

マラソンマッチ始めてみました。問題文 問題概要 縦 H 横 W のグリッドがあります。各マスに 9 以下の非負整数が書いてあります。マスのいくつかを塗って、塗られたマスに書いてある数の合計を大きくしてください。ただし 縦 h 横 w のどの長方形も塗られた…

年末年始は Asprova Programming Contest をやってました。なんか問題文が軽い気持ちで読むには重すぎる感じなのですが，短くまとめると いくつかの設備を備えた工場があり，そこでいろんな製品を生産しています 各製品はいくつかの工程を経て完成します 各…