drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder500点 ABC-E 構築 考察：補集合を考える 最適化の考察：「≦ K であること」と「= K となる実例」を示す グラフ 水色diff 制約条件:距離K以下の2頂点 木の問題に対してパスの場合から考える NoviSteps1Q 順位表メタ読みスキルも大事かもしれない。「たくさん通しているのだから、きっと単純な方法があるに違いない」という感じの 問題へのリンク 問題概要 頂点の連結な無向グラフのうち、その間の最短経路長が 2 となっているような二頂点の組がちょうど 組であるようなものを構築せよ。 存在しない場合は -1 と出力せよ。 制約 考えたこと この手の構築を安定して解くためには、まず典型的なグラフたちに対して「最短経路長が 2 となる組数はどうなってるか」を観察するのが良さそうな気がする。そんな代表的なグラフとして パス スターグラフ (今回の肝...今回に限らず検討すべきグラフ！！！) 完全グラフ 完全二部グ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2019%2F06%2F22%2F232000" title="AtCoder ABC 131 E - Friendships (1Q, 水色, 500 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/d/drken1215/20190622/20190622230718.png Hatena Blog https://hatena.blog 2019-06-22 23:20:00 rich https://drken1215.hatenablog.com/entry/2019/06/22/232000 1.0 100%