俵言

しがない社会人が書く、勉強とかのこと。最近は機械学習や kaggle 関連がメイン。

ARC037復習 (A,B,C)

開催は4/18だったので一ヶ月近く前のやつですね。

arc037.contest.atcoder.jp

このときもなかなかにボロボロでありました。解説聞いたけどちゃんと復習終わってないからやることに。 ただD問題は参加時にそもそも問題を読むことすら出来なかったのでまたそのうちに。

A - 全優

未来視した点数が80点を下回るならその分だけ勉強時間を割いてあげましょうって問題。

まあAはいいですよねAは。

N = int(raw_input())
m = map(int,raw_input().split(" "))
print sum([0 if m[i] >= 80 else 80 - m[i] for i in range(N)])

lambda式使えばさらにまとめられるなーと思いましたけど特に意味はなかった。

N = int(raw_input())
print sum(map(lambda x: 0 if int(x) >= 80 else 80 - int(x), raw_input().split(" ")))

B - バウムテスト

与えられた無向グラフにおいて閉路を持たない連結成分(木)の個数を求める問題。

一応通したものの、見返すと40行ぐらいのなかなかひどいコード書いてました。pythonは可読性が売りなのにこれは無い。

方針としては、木を節点の集合(set())で表すことにして、

  • 辺の両端の二節点のどちらも既存の木に属してない → 新しく木を生成
  • 辺の両端の二節点の片方だけが既存の木に属している → 属してない方をその木に属させる
  • 辺の両端の二節点の両方が既存の木に属している→
    • 属している木が同じ → 閉路があるので木ではない
    • 属している木が異なる → 和集合をとって一つの木にする

それで最後に木の数と一度も使われてない節点の数の合計を返すって方針でした。

N, M = map(int,raw_input().split(" "))
tree_num = 0
tree_set = []
unused = set(range(1,N+1))
for i in range(M):
    u, v = map(int,raw_input().split(" "))
    if u in unused:
        unused.remove(u)
        if v in unused:
            unused.remove(v)
            tree_set.append([1,set([u,v])])
            tree_num += 1
        else:
            for j in range(tree_num):
                if v in tree_set[j][1]:
                    tree_set[j][1].add(u)
                    break
    else:
        if v in unused:
            unused.remove(v)
            for j in range(tree_num):
                if u in tree_set[j][1]:
                    tree_set[j][1].add(v)
                    break
        else:
            for j in range(tree_num):
                if u in tree_set[j][1]:
                    for k in range(tree_num):
                        if v in tree_set[k][1]:
                            if j == k:
                                tree_set[k][0] = 0
                            else:
                                tree_set[j][0] &= tree_set[k][0]
                                tree_set[j][1] |= tree_set[k][1]
                                tree_set.pop(k)
                                tree_num -= 1
                            break
                    break
print sum([tree_set[i][0] for i in range(tree_num)]) + len(unused)

うん、クソですわ。対比の為に置いたけどこれはひどいw 同じ方針でももっと綺麗に書けると思うんですけどめんどくさくなっちゃいました。

で、解説で説明された方針は幅優先探索(dfs)を行うってものでした。探索済みのものにチェックして行って、探索中に探索済みにものに出会ったらそれは閉路だろって方針。 実装してみて分かったんですが、単純に全節点を始点としてdfsを行い、一度も探索済みの節点に出会わなければ1を返すってだけで良かったんですね。

def dfs(here, before):
    is_tree = True
    if searched[here]:
        is_tree = False
    else:
        searched[here] = True
        for next in link[here]:
            if next == before:
                continue
            is_tree &= dfs(next, here)
    return is_tree

N, M = map(int,raw_input().split(" "))
tree_num = 0
searched = [0 for i in range(N)]
link = [[] for i in range(N)]
for i in range(M):
    u, v = map(int,raw_input().split(" "))
    u -= 1; v -= 1
    link[u].append(v)
    link[v].append(u)
print sum(dfs(i,-1) for i in range(N))

さっきより大分すっきりしました。シンプルにかける方が筋が良いって言葉が耳に痛い。

C - 億マス計算

N2マス計算を行ったとき小さい方からK番目の数を求める問題。

1≤N≤3.0*104 であるため当然ながら全部を計算することは不可能ですよね。オンタイムのときは行成分と列成分をとりあえずソートすると何か出来そうな気がする、ぐらいしか思いつかなくてもう何も出来ませんでした。

「小さい方からK番目の値がXである」を「X-1以下の数はK個未満だがX以下の数はK個以上ある」って感じで言い換えるの身に付いてないっすねえ。「X以下の数がK個以上あるような最小のX」を見つければ良いっていうのは言われてみればなるほどなんですけど、その場で思いつくのはなかなか出来ない。早く身につけたい発想ですね。

探索は上の方針で二分探索を行えば良いので、あとは「X以下の数がK個以上ある」判定をどう行うかって話だったんですけど、高橋ジグザグ法も聞いてなるほどーてなりました。答え聞いたら当たり前のことではあるんですけど、ああいうのを思いつける人になりたい。

def check(X):
    count = 0 
    j = N - 1
    for i in range(N):
        while j >= 0 and a[i] * b[j] > X:
            j -= 1
        count += j + 1
    return count >= K

N, K = map(int,raw_input().split(" "))
a = map(int,raw_input().split(" "))
b = map(int,raw_input().split(" "))
a.sort()
b.sort()
left = 0
right = 10**18
while right - left > 1:
    mid = (left + right) / 2
    if check(mid):
        right = mid
    else:
        left = mid
print right

この前やったABC002やその前のABC023でも二分探索の復習したんで、次はオンタイムで解けるようにしたいです。今日のARCも頑張ります！