ARC111

AtCoder Regular Contest 111 - AtCoder ARC111, A, B, Dの3問でした。事前の調整をミスって電話が来てしまうミス(?) CのREはDのコードを間違えてCに提出したもの。

A - Simple Math 2

• 考えたこと
  • $10^{18}$かと思ったら $10^{10^{18}}$
  • M^2であまりを取れば良い
  • ループ検出？M^2のテーブルを作ると10^8だからダメそう
  • ダブリングで良さそう
• AC python

def main():
    N, M = map(int, input().split())
    M2 = M * M
    doubling = [10 % M2]
    for i in range(60):
        doubling.append(
            (doubling[-1] ** 2) % M2
        )
    ret = 1
    for i in range(60):
        if N % 2:
            ret *= doubling[i]
            ret %= M2
        N //= 2

    print(ret // M)

B - Reversible Cards

• 考えたこと
  • 色がグラフの頂点、カードが辺、辺のどちらかの頂点を塗ることができる、塗る頂点を最大化したい
  • 典型的なグラフの形をいくつか考える
    • パスでも木でも辺の本数だけ異なる色を選べる
    • ループなら全部選べる
    • 自己辺がある頂点は必ず塗られる
    • 位数1の頂点は必ず塗っても最適
    • それ以外は？
      • 決まってない辺を選んで2通り試す？
      • 20万本の辺が全部バラバラであるケースで2^200000でヤバい
    • 自明な上限として辺の数
    • 連結成分に分ける
      • 異なる連結成分は何も影響しないから
      • 連結成分ごとに解けば良い
      • 連結成分は連結であるのでE>=V-1
        • E=V-1の時、色はE
        • それより大きい時、色はV
    • 自己辺ある時は？
      • 気にしなくて大丈夫
      • 普通に辺の数を+1するだけで良い
      • 上記の計算にマッチする
• 実装
  • UnionFindで連結成分を求めながら辺の数をカウント
  • 頂点の数と比較して答えを出す
• AC python

def main():
    N = int(input())
    init_unionfind(400000 + 1)
    numEdge = [0] * (400000 + 1)

    for _i in range(N):
        a, b = map(int, input().split())
        ra = find_root(a)
        rb = find_root(b)
        if ra == rb:
            numEdge[ra] += 1
        else:
            unite(a, b)
            rc = find_root(a)
            numEdge[rc] = numEdge[ra] + numEdge[rb] + 1

    from collections import Counter
    ccs = Counter(find_root(a) for a in range(1, 400000 + 1))
    ret = 0
    for cc in ccs:
        V = ccs[cc]
        E = numEdge[cc]
        if E == V - 1:
            ret += V - 1
        else:
            ret += V

    print(ret)

• コンテスト後Twitter
  • https://twitter.com/mathbbn/status/1347922997600948226?s=21
    • 辺を頂点にして二部グラフ
    • 二部グラフの最大マッチングに帰着するので最大流で解ける
    • TLEギリギリらしい
  • 「どうしたらグラフだという発想が出るのか」

    • なるほど、どうしてだろう

    • 自分のメモを見返したら、特にはっきりした「気づき」を経ることなく、サンプルを絵に描いて理解しようとする流れでグラフになってた

    • 

    • あえて言葉にするなら、この問題はカードの順番を入れ替えても答えに影響しないし、裏表を変えても影響しないので、与えられた配列の形を維持する必要性がないよね、ということで、もっと柔軟な形で持つ感じ

  • 木かどうかの判定で良い理由の簡潔な証明
    • 連結成分の全域木を考える
    • これを根つき木に変換すると、各辺で深い方の頂点を選ぶことで根以外の頂点が塗れる
    • 全域木以外に辺があるなら、その頂点の片方を塗って、その頂点を根にすれば全部の頂点が塗られる

Cがよくわからないので飛ばしてDへ

D - Orientation

• 考えたこと
  • ある頂点から到達可能な頂点の数が与えられていて、辺を方向づけする
  • 当たり前だけどaからbに辺がある時にca<cbになることはあり得ない
  • そんな簡単なはずはないと思うが、とりあえずそれで実装してみる
  • ああ、イコールの場合にどちら向きにするかが自明ではないのか
    • サンプル1が親切
  • 到達可能頂点数がイコールである頂点の間のグラフが与えられて、それを強連結成分にする
  • 辺を深さ優先探索すれば良い(頂点ではなく)
  • 辺の深さ優先探索をループで書いてバグらせた、自信を失ったので再帰で書いて通した python

def main():
    _N, M = map(int, input().split())
    from collections import defaultdict
    edgelist = []
    for _i in range(M):
        frm, to = map(int, input().split())
        edgelist.append((frm - 1, to - 1))

    CS = list(map(int, input().split()))

    answer = {}
    edges = defaultdict(list)
    for v1, v2 in edgelist:
        if CS[v1] > CS[v2]:
            answer[(v1, v2)] = "->"
        elif CS[v1] < CS[v2]:
            answer[(v1, v2)] = "<-"
        else:
            edges[v1].append(v2)
            edges[v2].append(v1)

    for v1, v2 in edgelist:
        if (v1, v2) not in answer:
            answer[(v1, v2)] = "->"
            answer[(v2, v1)] = "<-"

            def visit(e):
                (v1, v2) = e
                for v3 in edges[v2]:
                    if v3 == v1:
                        continue
                    if (v2, v3) in answer:
                        continue
                    answer[(v2, v3)] = "->"
                    answer[(v3, v2)] = "<-"
                    visit((v2, v3))
            visit((v1, v2))
    for v1, v2 in edgelist:
        print(answer[(v1, v2)])

C - Too Heavy

• 全く方針が立たず提出に至らなかった
• 考えたこと
  • 一つ構築せよ問題、きっと貪欲法
  • NlogNくらいになるのかな？
  • 交換して大丈夫なら交換する？
    • 自分が持ってる荷物の本来の持ち主が持っている荷物を自分が持てるなら交換？
    • 解があるのに交換できない事態に…
  • 最も重いものから動かす？
    • それを持って良い人が限られる
    • 重いものを渡す時に帰ってくるものが重いかもしれない
• コンテスト後Twitter

  • 重い荷物から順に、正しい持ち主にわたすようにすればいいね！　渡される側は、正しい荷物になるから重さを気にする必要はなくて、渡す側は軽い荷物と交換になるから、その後も困らない

    • https://twitter.com/kyopro_friends/status/1347908488945496064?s=21
    • なるほど「重い順」と「本来の持ち主」の両方か…
• 考察
  • どんな貪欲法をやれば良いか気づくにはどうすれば良いか
  • 端から埋めるパターン
    • 今回の問題は人間の並び順には意味がないので無視するべきだった
    • 今回の場合の「端」は並び順ではなく荷物の重さ
  • Twitterを見ていると「最も力の弱い/強い人」というパターンも。
  • 最も重いものを本来の持ち主に動かした時に疲れる心配がないことに気づかなかった
  • 最適であることの証明、下界に一致

E

• 考えたこと
  • 
• コンテスト後のTwitter
  • floor sum