問題 D - All Your Paths are Different Lengths 考えたこと なんかbit的な考え方？という臭いがしたのでとりあえずとおき、辺の長さをとしていい感じの有効グラフを構築してみます。 いい感じの有向グラフ 頂点間に長さのパスができあがっているので 残りの…

問題 D - Worst Case 考えたこと ペアの組み合わせとしてはと、 とだけど後者のペアをなるべく作ればペアの数を増やせる。 前提条件 ① よって ② とおく rが平方数の場合 なのでの組を作れません。未満は使用できるので個の組を二つ作れます*1。 の場合、が使…

※texにキーワードリンクが張られて数式が認識されない場合があるため見づらくなってます。脳内補間おなしゃっす 問題 D - AtCoder Express 考えたこと 便宜のためを区間と書きます。 区間速度の修正 区間 の速度が [tex:v{i+1}] なので、区間 で出しても良い…

問題 D - 井井井 考えたこと の盤として各マスが何回使われるか考えます*1。 とりあえず1行しかないとして考えてみると、 マスは回使われます。マスから一個、マスから一個選んでつなげた場合にマスを含みますね。 列についても同じように考えることができる…