思考のジャンプ幅が狭いなら,飛ぶ回数で補えばいいじゃない!!

非情報系30歳が競技プログラミングやWeb開発を始めるとどうなるか?

AtCoder Beginner Contest 131 E - Friendships

目次

結論

  • さまざまなグラフを書いてみる.

  • グラフ理論に対する知識・理解を深める.スターグラフの存在を知っている(もしくは図として描ける)かどうか?

  • 構築問題のアプローチ方法の一つとして,条件を満たす上限値・下限値を理論的に導出できないか を試す.

  • 上記で得られた上限値・下限値から,目標に近づけられないか試す.

はじめに

  • AtCoderで出題された問題を復習しています.

  • 公式解説や上位陣による解説ブログを読んで,自分に足りなかった部分や得られた知見を消化してアウトプットしようと思います.

想定読者

  • 解説を読んで解き方はわかったものの,なぜその方法を思いつけるのか?と思った方.

筆者の実力

記事の特徴

  • なぜその発想に至ったのか,どうしたら解法を詰められるかといった点について,筆者なりの解釈をつづります.

  • 試行錯誤した過程から,得られた前提知識や着眼点を言語化していきます.

  • 間違いや勘違いなどがございましたら,ご指摘・ご指導いただけると幸いです(大歓迎です).


問題のリンク

E - Friendships (500点)

発想・解法とそれらを引きだすための方法・解釈

この問題の難しいところ

  • 該当する条件を一つ出力せよ(いわゆる構築系の問題.問題を見た瞬間に(´;ω;`)ウッ…となる方も多いのでは?)という形式である.

  • 前提として,グラフ理論に関する深い知識と理解が求められる.

最初の一歩は?

  • さまざまなグラフの形状をノートなどに書き出してみる.

考察のキモ(Key Insight)は?

  • 完全グラフ(すべての頂点からあらゆる辺が貼ってある)のときに,条件を満たす頂点対の数が最小となる.

f:id:hiro_kato:20190623214155p:plain
完全グラフ

  • スターグラフ(ある一つの頂点からのみ辺が張られているグラフのこと)の存在を知っている,もしくは,自力で気がつく.そして,条件を満たす頂点対の数が最大となることを証明できる(確証が持てる)かどうか.

    • 頂点の組み合わせの上限が N(N - 1)/2個 である.

    • 条件から「グラフは単純かつ連結である」である. N頂点のグラフが連結であるためには, N - 1個の辺が必要である.

    •  N(N - 1)/2 - (N - 1)を変形すると, (N - 1)(N - 2)/2となる.

f:id:hiro_kato:20190623214144p:plain
スターグラフ

  • スターグラフに対して,任意の頂点間に辺を張ると,条件を満たす頂点対の数が1減る.これは,最短距離が1となるため.

どうしたら思いつけそうか?

  • さまざまなグラフの形状をイメージできるようにする.

  • 条件を満たさない場合を列挙する.もしくは,条件を満たす場合で,上限値や下限値となる場合を列挙する.

  • 仮説の妥当性を確かめるため,数式でチェックしてみる.

実装のポイントは?

  • スターグラフを表現するため,ある頂点 iからのみ辺を張った場合の頂点対をリストや配列などで用意する.

  • 頂点対が Kとなるまで,スターグラフに任意の頂点対(ある頂点 iを含まない)を追加する.

Python3による回答例

# -*- coding: utf-8 -*-


def main():
    n, k = map(int, input().split())
    max_comb = (n - 1) * (n - 2) // 2

    # 頂点対の上限よりも大きい場合は,条件を満たさない
    if k > max_comb:
        print(-1)
        exit()

    ans = list()
    candidates = list()

    # スターグラフの頂点対を生成
    for i in range(1, n):
        ans.append((1, i + 1))

    # スターグラフの頂点対を減らすための頂点対の候補を列挙
    for i in range(1, n - 1):
        for j in range(i + 1, n):
            candidates.append((i + 1, j + 1))

    # 頂点対がKとなるまで,上記の候補を追加
    for i in range(max_comb - k):
        ans.append(candidates[i])

    m = len(ans)
    print(m)

    for i in range(m):
        print(ans[i][0], ans[i][1])


if __name__ == '__main__':
    main()

得られた知識・知見

  • さまざまなグラフの種類(完全グラフ,スターなど)の存在.

  • 構築問題に対するアプローチ方法の一つとして,条件を満たす上限値・下限値を列挙することがヒントになりうる.

  • 上記で求めた上限値・下限値から,目標に近づける.

感想

  • 本番で初めて4完(60分,1WA)した勢いでE問題を開いてみたところ,見事に返り討ちにされました.解説を聞けば分かった気がするものの,自力で思いつくためには相当な精進が必要なのだろうと思いました(小並感).

参考

drken1215.hatenablog.com

記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが,@k_hiro1818までご一報ください.

更新履歴

  • 2019/06/23 作成
  • 2019/0x/xx 更新