EAFP

~ Easier to Ask for Forgiveness than Permission ~

Atcoder ABC285をpythonで解いてみた

目的

Atcoder ABC285に出場したので、その結果、感想、復習を兼ねて記事を書きました。特に、自分としてパフォーマンスが優れなかった!と感じた際には、必ず書くというのを今年続けようと思っています。

atcoder.jp

解いたコードで、気になって色々修正もしたものは下記に置いてあります。動作確認済みです。

github.com

結果

ABCDの4完で、Dで大量のWAを出しながら、ギリギリで通すことができましたが、E問題には時間をかけて取り組むことができませんでした。

図1. ABC285の結果

D問題に関しては、方針はすぐ立ったものの、WAを取るにあたっての考察がゆるく、問題を解くのに時間がかかったと思っています。

振り返りに関しては、A, B問題は簡単であったと感じるので、解答のみに留めます。

A問題

  • グラフをリストで表現した際に、0-indexで書いてしまい、1 WA出してしまったのは反省点(7分かかった)

atcoder.jp

B問題

  • 問題文の意味を理解するのに苦戦し、15分程度時間をかけてしまった

atcoder.jp

C問題

与えられた文字列(ex. A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...) が、辞書順に並べた際に、何番目になるか?を求める問題

atcoder.jp

考察

まず、各文字は A-Z で与えられるので、26通りあることが、わかります。基数変換を書いたことがあったので、これは 1-indexed な26進数とみなせるのでは?と考えて解きました。

qiita.com

基数変換のロジックは上記のサイト他、多数で紹介されているため、ここでは割愛します。

def id_to_int(s):
    num = 0
    for i, ss in enumerate(s[::-1]):
        num += (ord(ss) - ord("A") + 1) * pow(26, i)
    return num


S = input()
print(id_to_int(S))

上記のように、文字列を辞書で何番目に来るか?に変換することで、コンテスト内で6分程度の時間で、解くことができました。

atcoder.jp

D問題

ユーザ名の遷移をグラフとして表現し(問題文の意図通りに考えると、有向グラフであるが、今回の条件では無向グラフとして扱っても解くことができる)、閉路のある成分があるか?という問題

atcoder.jp

考察

まず、問題文を読み、入力例を見ながら紙にユーザの遷移を書いたことで、下記がわかりました(だいたい5分くらい?かかったかなと)

  • 遷移を扱うので、有向グラフとして扱えそう
  • 入力例2 を見る感じで行くと、閉路がある場合は、Noとなりそう

その上で、有向グラフの閉路検出方法としては

  • DFS/ BFSで巡回し、今まで訪ねた要素に到着するか?どうかで判定する
    • 以前、leetcodeで解いた際に使った フロイドの循環検出 でも解くことができると思ったが、戻ってくる要素の場所を知りたいといったニーズもないので、今回は使わなかったが、今思い返すと使った方が楽に解けたかも?と思う

leetcode.com

  • トポロジカルソートを行う
    • 知識としてはあって、書いたこともあったが、空でかけるほどの自信はなかったので今回は選ばなかった

output-zakki.com

  • UnionFindを使う
    • 無向グラフの平路検出で使える。今回のグラフは問題の制限上、一直線になるか、円になるか?しかないので使えそうだなと思ったが、若干自信なく、最初は選択しなかった

output-zakki.com

以上より、DFSをまず採択し、問題を解き進めました。この時、変更前/ 変更後のユーザ名はユニークであるため、下記のような1つの要素から、2つの辺が伸びることはないです。

図2. 要素の遷移

つまり、各成分は下記の3つのどちらかの形になるはずで、成分中に閉路が1つでも発見できれば、Noになるはずです。

図3. グラフの形

そこで、下記のようなコードを書き提出したのですが、WAが6つでてしまいました。

atcoder.jp

コンテスト中は問題の原因には、はっきりわからなかったのですが、おそらく、探索開始の要素の条件を指定していないので、下記のように探索してしまい、閉路と誤認しているのではないのか?と思いました。

図4. 成分の途中からDFSした場合

WAを出しながらも、カイゼンしたものの、DFSではコンテスト中には解くことができず、UnionFindを使った方法に方針転換しました。ちなみに、コンテスト後下記のように改良し、無事に解くことができました。

from collections import defaultdict
from sys import setrecursionlimit

from pypyjit import set_param

set_param("max_unroll_recursion=-1")
setrecursionlimit(pow(10, 9))


def dfs(cur):
    visited[cur] = True
    if not edge[cur]:
        return
    s_set.remove(cur)
    for nxt in edge[cur]:
        if visited[nxt]:
            print("No")
            exit()
        dfs(nxt)


N = int(input())
edge = defaultdict(list)
in_cnt = defaultdict(int)
visited = defaultdict(bool)
s_set = set()
for _ in range(N):
    S, T = input().split()
    in_cnt[S] += 0
    in_cnt[T] += 1
    edge[S].append(T)
    s_set.add(S)
deps = [k for k, v in in_cnt.items() if v < 1]
if not deps:
    print("No")
    exit()
for dep in deps:
    dfs(dep)
if s_set:
    print("No")
    exit()
print("Yes")

atcoder.jp

ポイントは、下記の2点かと思います。

  • 入次数をカウントし、入次点0(= rootになるべき要素)から、DFSするようにした
  • 完全に閉路なグラフ(= 図3. の一番下のような形)の場合、入次点0の要素がないため、探索しないことになるので、各要素を探索したか?のstatusをsetで管理し、もし閉路が見つからなくても、探索していない要素があればNoとする

寄り道しましたが、コンテスト中UnionFindを使い、下記のように解きました。自分の持っているUnionFindのライブラリでは、UnionFindの要素はindexが数値で、かつListで管理していたため、defaultdictを使って、index numberが連続値でなくとも使えるようにしたのと、keyがstringだったため、intに変換し利用しました。

from collections import defaultdict


class UnionFind():
    def __init__(self):
        self.parents = defaultdict(lambda: -1)

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


def str_to_int(s):
    num = 0
    for i, ss in enumerate(s[::-1]):
        num += (ord(ss) - ord("a") + 1) * pow(26, i)
    return num


N = int(input())
uf = UnionFind()
for _ in range(N):
    S, T = map(str_to_int, input().split())
    if uf.same(S, T):
        print("No")
        exit()
    uf.union(S, T)
print("Yes")

無事、下記の通り、解くことができました。図3. にある通り、今回は3パターンのグラフの形しかなく、無向グラフとみなしても、有向グラフと同じ閉路が検出できるため、UninonFindが使うことができました。この辺りは、感覚でやっていましたが、同僚と毎週やっている勉強会で指摘され、改めて認識することができました。

atcoder.jp

E問題

atcoder.jp

考察

(解いたら載せます)

まとめ

今回は、D問題で多くの時間を使い、かつ多くのWAを出してしまったことで、自分の期待するperfomanceが出ませんでした。 考察の詰めの甘さが課題かと思っているので、引き続きこのような復習を繰り返し、見通しの良い考察と方針を立て、より早く問題が解けるようにしたいと思います。

Atcoder ABC284をpythonで解いてみた

目的

Atcoder ABC284に出場したので、その結果、感想、復習を兼ねて記事を書きました。

特に、緑になってから約10ヶ月程度立ちましたが、rateが上下し一向に向上の兆しが見られない原因として 復習が足りないのではないか?という仮説を立て、今年からはrateが下がった際には、記事を書く!というのを自分に課していこうと思っています。

atcoder.jp

解いたコードで、気になって色々修正もしたものは下記に置いてあります。動作確認済みです。

github.com

結果

ABCの3完で、D問題は方針は概ね合っていたものの、考察が足りないため解けず(後述します) E問題に移ったが、時間内に解くことができずタイムアップとなってしまいました。

図1. ABC284の結果

ABCまでは、10分程度で解け、Dも方針立てるのに5分程度でしたし、E問題も緑diffであったことを考えると、5完したかったところですが、これができないあたりに課題を感じました。

自分の今のレベルからすると、A, B問題は簡単であったと感じるので、解答のみに留めます。

  • A問題

atcoder.jp

  • B問題

atcoder.jp

C問題

N 頂点 M 辺の単純無向グラフのうちに、連結成分が何個あるか?という問題

atcoder.jp

考察

連結成分とは何か?に関しては、下記に記載があるので、ここでの説明は割愛させていただきます。

algo-method.com

まず、連結成分を求める際に Union-Find を使おうと考えました。Union-Findを利用することで、辺で繋がれた頂点同士を1つのグループとして扱うことができるためです。 ここでは、DFSや、BFSを使って要素を探索することで、解答することでも可能だと考えましたが

amateur-engineer-blog.com

Union-Findを使えばより簡単(手元にUnion-Findを実装したクラスがあり、与えられた辺を近接リストにして処理せずとも、辺の情報のみで解答可能)にできると考え、下記のように実装しました。

# いつも使っているUnionFindのClass(下記を参照にし、一部変更したりして利用している)
# https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if x < y:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x


N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    u, v = map(int, input().split())
    # 要素同士を1つにまとめる処理
    uf.union(u - 1, v - 1)
# N個の要素の親を確認し、親要素の種類を数え上げる
ans = set()
for i in range(N):
    p = uf.find(i)
    if p not in ans:
        ans.add(p)
# 親の要素の種類数が答えになるので、出力する
print(len(ans))

atcoder.jp

これにより、時間内に問題を解くことができました。 時間計算量: O(N + M)、空間計算量 O(N + ansに格納される要素数) であると考えます。

実際は、Union-Findのfindを繰り返して、計算するよりも、Union-Findのクラス内で保持している self.parents のうち、-1 である要素を数え上げることでも、答えはわかる上に、都度findしない分早くなると思われます。 しかし、find自体は、下記の両方の工夫をして実装しており、実質 O(1) 程度の速度で実行可能であると考えると、ほぼ差は出ないと考えました。

algo-method.com

が、後々やってみる(下記がカイゼン後の提出結果)と50ms程度の速度向上が見られました。 これは、range(N) を作成したり、ans 内に すでに同じ要素があるか? findでの処理はO(1)に近づくとはいえ、完全に1ではない といったあたりが関係していると思われます。

atcoder.jp

D問題

正整数 N =p2 × q (素数 p,q) と因数分解可能な N が T個与えられるので、それぞれで、p, q を求めて出力せよ!という問題

atcoder.jp

考察

まず、 1 <= N <= 9 × 10^18 と非常に巨大であることから、N全てを探索することも、ルートを取ったとしても間に合わないと思いました。

つまり、通常よく実施する素因数分解では間に合わないため、別の方法を考える必要があります。

amateur-engineer-blog.com

ちなみに、解説にもある ポラード・ロー素因数分解法という高速に素因数分解する方法を使えば解けるようですが、自分は知らなかったためそのような選択はしませんでした。

次に着目した点に関しては、1/3 乗 であれば 106 程度に収まるため、計算可能ではないか?と思い、エラストてネスの篩を用いて、N1/3 の範囲の素数を求め、それらを使って素因数分解できないか?を考えました。

club.informatix.co.jp

理由としては、 N = p * p * q となるため、p か q のどちらかは必ず上記の範囲内の素数として発見できると考えたためです。 ここまでは良かったのですが、問題を解いている際は、pにのみ着目して考えてしまい、pが小さい際には、qはこの範囲を超えてしまう・・・どうしよう・・・と思って色々考えて時間を潰してしまいました。

反省としては、p か q のどちらかになるのであれば、その逆を求めることは簡単なはずなのに、その発想に至らず解くことができなかった。後々言われるとわかるけど、その場では思いつかなかったと言うところになります。

では、どうすればいいのか?というと、106 程度 の素数のうち、Nを割り切ることができる最大の数を x としておいたときに - N % x2 = 0 であれば、p = x である - そうでなければ、q = x であり、 p = √(N/x) である

ということになり、問題を解くことができます。

from math import sqrt

# エラストてネスの篩を用いて素数を列挙する関数
def sorted_prime_list(limit):
    limit += 1
    primes, is_prime = [], [True] * limit
    for i in range(2 ** 2, limit, 2):
        is_prime[i] = False
    for p in range(3, limit, 2):
        if not is_prime[p]:
            continue
        primes.append(p)
        for i in range(p * p, limit, p):
            is_prime[i] = False
    return primes


T = int(input())
N = [int(input()) for _ in range(T)]
# 何度も素数列挙をするのは効率が悪いので、1度で実施する
primes = sorted_prime_list(min(max(N), 3 * pow(10, 6)))
for n in N:
    p_or_q = 2
    for prime in primes:
        # prime が n^(1/3) を超えてしまうような範囲は探索する必要がないのでbreakする
        if pow(n, 1 / 3) + 1 < prime:
            break
        if n % prime == 0:
            p_or_q = max(p_or_q, prime)
    ans = (p_or_q, n // p_or_q ** 2) if n % p_or_q ** 2 == 0 else (round(sqrt(n // p_or_q)), p_or_q)
    print(*ans)

atcoder.jp

これにより、問題を解くことができました。 時間計算量: O(XloglogX + T * primesのlength * round(sqrt)の計算量 )、空間計算量 O(x + x以下の素数の数 + 2 * T) であると考えます。 X = min(max(N), 3 * pow(10, 6)) とし、sqrtの計算量に関しては色々調べましたが log程度かそれ以下なのはわかったのですが、わからず・・・

ちなみに、高速で平方根も止める方法は色々あるようでその辺りは興味深かったです。

takashiijiri.com

E問題

N 頂点 M 辺の単純無向グラフを探索し、パスの本数を数えよ!という問題

atcoder.jp

考察

まず、要素1 からの経路を探索していくことを考えたので DFS を用いて解こうと考えました。pathの数をKとした際に、求める答えが min(K,10 ^6) であるが故に、106 以上のpathを回る必要がないということが条件に書かれているためです。

そのため、書き慣れた再帰を用いたDFSの関数を書き、通った要素を再度通らないように vis というリストを用意し、通った箇所は True とするようにして状態管理を行いました。

from collections import defaultdict
from sys import setrecursionlimit

from pypyjit import set_param

set_param("max_unroll_recursion=-1")
setrecursionlimit(pow(10, 9))


def dfs(cur):
    global ans
    if ans >= limit:
        print(limit)
        exit(0)
    for nxt in edge[cur]:
        if not vis[nxt]:
            vis[nxt] = True
            ans += 1
            dfs(nxt)
    vis[cur] = False


N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    edge[u - 1].append(v - 1)
    edge[v - 1].append(u - 1)

ans, limit = 1, pow(10, 6)
vis = defaultdict(bool)
vis[0] = True
dfs(0)
print(ans)

しかし、何度やってもTLEしてしまいます・・・

atcoder.jp

ダメ元で、python3で提出したら通りました。

atcoder.jp

pypyでの再帰は遅い問題は指摘されていましたが、pypyjit でパラメータを設定することで回避できるという話も見かけていて、今までこれを使って回避できたと思っていたのですが

qiita.com

今回に限ってなのか、そもそもさほど効果がなかったのか?の深掘りはできていませんが、こういうこともあるのだろうな。というところで、調査はやめてしまいました。

doc.pypy.org

もし、この辺り詳しい方いれば教えて欲しいです。

まとめ

今回は、Dでコケてしまい、その後軌道修正できずに終わってしまうという悔しい結果になりました。整数問題というか、Dのようなタイプの問題が苦手て、自分のrateよりも低い問題でも解けなかったりすることが多いので、この辺り解けるようにしていければと思っています。

また、考察をより深く!早く!立てて手戻りなく、スムーズに解けるようになるというのも課題なので、コンテスト中も、普段別の問題を解く時も、復習で記事を書く際も、この辺りの能力を高めていけるように、頑張っていければと思いました。

いつか、水色になれる日を夢見て、今後もAtcoderを頑張っていければと思います。

Atcoder ABC264をpythonで解いてみた

目的

Atcoder ABC264に出場したので、その結果、感想、復習を兼ねて記事を書きました

atcoder.jp

解いたコードで、気になって色々修正もしたものは下記に置いてあります。動作確認済みです。

github.com

追記

UnionFindは、Unionする際に座標圧縮をしており、O(1) で find できているようです。unionする際に、rankで結合していないので、その分計算量は遅くなると思いますが。

algo-method.com

結果

ABCDの4問完で、E問題は方針はあってるものの、bugが取れずタイムアップしました。 その後Dに取り組みましたが、途中まで間違った方針で解いていて、気づいた時には時遅しでタイムアップしてしまいました。

図1 ABC264の結果

簡単なので、A問題は解答のみに留めます

atcoder.jp

B問題

  • 15 * 15 マスのgridのうち(これは問題文より状態が与えられる)、R, C が与えられる(左上から初めて、縦 R 番目、横 C 番目)ので、それが何色か答える問題

atcoder.jp

考察

問題としては大きく2つの解き方があると思います。15 * 15 = 225(通り) なので、愚直に計算しても計算量としては問題ない量になります。

  1. 愚直に、15 * 15 のgridを描いて、R, C が何色か答える方法(ref: 公式解答2の方法)
  2. 法則を見つけて、R, C が何色かを1発で答える方法(ref: 公式解答1の方法)

自分は、2. の方針で解きましたが、ここで25分以上使ってしまい、後々解答時間が減っていってしまいました。

まず、 チェビシェフ距離 というものを知っていればよかったのですが、自分は知らずにここを0 から考えることになってしまったというのが2. で考える上では非常に厳しかったです。本来であれば、 1. で愚直に早く解いて次に行くべきでしたが、気がついたら多くの時間を使ってしまっていました。

ja.wikipedia.org

色々試行錯誤しましたが、中心の白い点(R, C) = (8, 8) の点を中心に(左上の点を (1, 1) だと考えた場合 ) 考えていくことに辿り着きました。 x, y = abs(R-8), abs(C-8) で考えると、中心を原点とみなした場合に、第一象限のみを考えればいいということがわかります(それぞれ対象で同じ法則で色が決まるので)。 また、y = x の線を引くと、第一象限の中でも、線対象になっていることがわかります。

図2. 中心の白い点を起点に考えた場合

従って、中心からの縦の距離(abs(R - 8))、横の距離(abs(C - 8)) を考えた際にそれぞれの値の偶奇を考えれば、色がわかるということに辿り着きました

R, C = map(int, input().split())
if (R, C) == (8, 8):
    print("white")
else:
    dr, dc = abs(R-8), abs(C-8)
    if dr <= dc:
        # NOTE: 横長の場合は、横の距離で判定する
        print("white" if dc % 2 == 0 else "black")
    else:
        # NOTE: 縦長の場合は、横の距離で判定する
        print("white" if dr % 2 == 0 else "black")

atcoder.jp

コンテスト後にリファクタリングしましたが、上記のコードは下記のようにもっと簡単にすることができます。

atcoder.jp

これにより、時間内に問題を解くことができました。

C問題

  • 任意の2次元配列A, Bが与えられ(サイズはBの方がAよりも小さい)、Aのうち任意の行/ 列を削除した際に A = B にすることができるか

atcoder.jp

考察

Aの配列のうち、縦から H2個、横から W2個 それぞれ選んで2次元配列A' を作り、それがBと一致するか?を考えました。 H1, H2 <= 10 のため、組み合わせを考えても (10C5) ^ 2 = (252) ^ 2 < 90,000(= 300 ^ 2) なので、十分計算できると考えました。 python だと from itertools import combinations で 組み合わせの場合のtupleを返してくれる組み込み関数があるので利用しました。ない場合は、再帰などを用いて求めることになると思います。

from itertools import combinations

H1, W1 = map(int, input().split())
A = [list(input().split()) for _ in range(H1)]
H2, W2 = map(int, input().split())
B = [list(input().split()) for _ in range(H2)]

for hc in combinations(range(H1), H2):
    for wc in combinations(range(W1), W2):
        flags = True
        for i, h in enumerate(hc):
            for j, w in enumerate(wc):
                if B[i][j] != A[h][w]:
                    flags = False
        if flags:
            print("Yes")
            exit()
print("No")

atcoder.jp

2重ループのうち、途中で違ったらbreakした方が早いので、コンテスト後に下記のようにリファクタリングしました(9 msしか差がないので微妙なところですが)。

atcoder.jp

公式解説ですと、bit全探索で (2 ^ 10) ^ 2 = 1,048,576 通りを全探索していますが、これでも十分間に合います。ただ、Aうちで、選ぶ行/ 列 は Bの縦/ 横の大きさと同等のため、無駄に探索することになり計算量が大きくなってしまいます。

atcoder.jp

D問題

  • "atcoder" という文字列を並び替えられた入力 S を、何回隣り合った文字を交換することで "atcoder" に戻せるか。最小の交換回数を求めよ。

atcoder.jp

考察

解説を見ると、「転倒数」という問題を知っていれば、O(nlogn) で解くことができます。

atcoder.jp

ただ、自分は知らずに、BIT(Binary Indexed Tree) もライブラリとして持っていないので、バブルソート(O(n2)) を実装する形で解きました。

ja.wikipedia.org

今回は、 "atcoder" = 7文字 だったので、O(n2) でも十分解くことができました。しかし、文字数(それぞれユニークであることが必要だが)がより長くなる場合には、解くことができません。また、バブルソート的にswapした回数が最小になるか?に関しても確信はないまま(まぁ、たぶん大丈夫だろう)という気持ちで提出しました。

scrapbox.io

S = list(input())
target, ans = list("atcoder"), 0
while S != target:
    for i in range(len(S)-1):
        cur, nxt = S[i], S[i+1]
        if target.index(cur) > target.index(nxt):
            S[i], S[i+1] = nxt, cur
            ans += 1
print(ans)

atcoder.jp

コンテスト後に、stringで都度index取る方法だと効率悪いので、dict(辞書型、他の言語で言う連想配列(= hashmap)) で解く方法にリファクタリングしました。

atcoder.jp

E問題

  • N + M 個の node と、E 本の辺が与えられる
    • 1~N 番目の node は街で、 N + 1 番目 ~ N + M 番目のノードは発電所
  • 1つの辺を切っていく(X個の辺を最終的に切る)
    • 発電所につながっている node は電気が通っている
    • 電気が通っている 街の数を常に出力せよ

atcoder.jp

考察

まず、問題を読んでUnionFind Tree(以下、UnionFind)を使って解くことを考えました。これは、「根を持つ木」を高速に生成でき、根が発電所であればOK(電気が通っている)、そうでない場合は NG(電気が通っていない)と考えました。

ja.wikipedia.org

ここで、UnionFind の性質と、発電所が N + 1 番目以降の node である問題特性から 2 つのポイントがあったと考えます。

  1. UnionFind では、2つの木を結合(Unionする)ことはできるが、分割はできないので、全て辺が切れてしまっている状態から、結合していくのがよい(= 逆から見る)
  2. 結合した根は、必ずindex番号が大きいものになるように工夫する必要がある(= 発電所かどうか判定するため)

また、都度出力する必要があるので、その際にどのように考えればいいかと、下記の2パターンになる。最初に、電気が通っている街がいくつあるのか?は、O(NlogN)程度で求められると考え(全ての街の親nodeを調べて、親が発電所であれば+1する)、その後辺を突合するたびに街の数を加算していく & その数を配列に保持し、最後に逆順序にして出力すればいいと考えました。

  1. 繋げるそれぞれの木の根が、両方発電所、もしくは両方街の場合は、電気が通っている街は変わらない
  2. 繋げるそれぞれの木の根が、どちらか発電所の場合は、根が街の木の大きさ分(= 街の数)加算する

図3. 電気が通る街の数が増えるパターン

ちなみに、下記の実装にもありますが、木の大きさは O(logN) 程度で求められると考えられる(findがO(logN)で、見つけた親のsizeを求めるのは、配列へのアクセスなのでO(1))ので、なんとか間に合うのではないか?と考えました。ここのサイズの大きさをどう求めるか?に関しては知らなくてコンテスト中に調べて辿り着きました。

note.nkmk.me

ただ、時間内には下記の方法で実装したものの、サンプルと答えが合わず、残り時間もなくてタイムアップしてしまいました。

from collections import defaultdict


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] < self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]


N, M, E = map(int, input().split())
conn = defaultdict(tuple)
for i in range(E):
    U, V = map(int, input().split())
    conn[i] = (U-1, V-1)
Q = int(input())
dis_conn = []
for _ in range(Q):
    X = int(input())
    dis_conn.append(conn[X-1])
    del conn[X-1]
uf = UnionFind(N+M)
for k in conn:
    uf.union(conn[k][0], conn[k][1])
cnt = 0
for i in range(N):
    if uf.find(i) >= N:
        cnt += 1
ans = [cnt]
while dis_conn:
    u, v = dis_conn.pop()
    u_par, v_par = uf.find(u), uf.find(v)
    if (u_par < N and v_par < N) or (u_par >= N and v_par >= N):
        pass
    elif u_par >= N and v_par < N:
        cnt += uf.size(v)
    elif u_par < N and v_par >= N:
        cnt += uf.size(u)
    ans.append(cnt)
    uf.union(u, v)
print(*ans[::-1][1:], sep="\n")

結論言うと、UnionFind の union 関数に間違いがあり、if self.parents[x] < self.parents[y]: ではなく if x < y: とすべきでした。 大元のライブラリでは、木のnode数で比較していたのに気づかず、雑に書き換えてしまったのが原因でした。そのため、unionした際に、根がindex番号が必ずしも大きいものにならず、発電所が木の中にあっても、根にならないパターンを生み出してしまい、答えが合わなかったです。

atcoder.jp

コンテスト後は上記のように修正し、無事問題を解くことができました。

感想

結果として、4完し緑パフォでrateが若干上がりましたが、E問題ほぼ解けていたのにも関わらず、落としてしまい自分としては悔いの残る形になりました。

図4. ABC264の成績

特に、B問題までに時間かけすぎており、ここを高速化することで今後はrateが上がることが期待できるので、愚直に綺麗でなくても解くことをする。そして、DやEで出る水色下位(1400 diff以下)の問題を解くことでrateをさらに上げることができると思うので、引き続き精進していければいいなと思いました。

水色はまだまだ先として、早くコンテスト中にE問題解けるようになりたいな。

Atcoder ABC254をpythonで解いてみた

目的

Atcoder ABC254に出場したので、その結果、感想、復習を兼ねて記事を書きました

atcoder.jp

解いたコードで、気になって色々修正もしたものは下記に置いてあります。動作確認済みです。

github.com

結果

ABCの3問完で、Cで2回WAをしてしまいました。 その後Dに取り組みましたが、途中まで間違った方針で解いていて、気づいた時には時遅しでタイムアップしてしまいました。

図1 ABC254の結果

解説

それぞれ、どのような形で解いたのか解説していきたいと思います。A,Bは解答のみの記載にとどめます。

Submission #32199306 - AtCoder Beginner Contest 254

Submission #32207205 - AtCoder Beginner Contest 254

C問題

atcoder.jp

数列Aが与えられ、i番目とi+K番目の項を交換することを繰り返し、昇順にsortできるか?と言う問題です。まず、残念なことに 次の操作を 0 回以上何度でも行えます を読み飛ばし、WAを叩きますww

Submission #32213937 - AtCoder Beginner Contest 254

WAした瞬間に、問題文を読み直して、間違いに気づけたのはよかったです。 と、同時にこれKで割った余りのindex番号同志でしか、交換できないことに気づきます。下図のようなイメージを持ちました。

図2 ABC254 Cの方針

が、数列には重複した数が入るにもかかわらず、 set を用いて実装してしまい、WAします。すぐに気付けましたが、こういう提出はしないようにしたいです。。。

Submission #32220281 - AtCoder Beginner Contest 254

なので、重複を許容するためにdefaultdictを用いて下記のように実装し、無事解けました。

from collections import defaultdict

N, K = map(int, input().split())
A = list(map(int, input().split()))
if K == 1:
    print("Yes")
    exit()
dict_set = defaultdict(lambda: defaultdict(int))
for i, a in enumerate(A):
    dict_set[i % K][a] += 1
A.sort()
for i, a in enumerate(A):
    if dict_set[i % K][a] > 0:
        dict_set[i % K][a] -= 1
        # NOTE: 試験中はこれで出したが、実際には不要な部分をコメントアウト
        # if dict_set[i % K][a] <= 0:
        #   del dict_set[i % K][a]
    else:
        print("No")
        exit()
print("Yes")

Submission #32223209 - AtCoder Beginner Contest 254

ポイントは下記だと考えます。個人的には、C問題だけど、結構難しかったなと思いました。

  • K=1の時は、絶対sortできるのでTrue
  • K>=2 の時は、交換できない項が発生するので、交換できる項のグループ(= index番号をKで割った余り)をkeyとしたdefaultdictで保持し、重複もするため、どの数字が何個あるかという情報を保持する(= defaultdict(lambda: defaultdict(int)))
  • Aをsortした数列を用意し、1つづつ、該当のグループ内に数値があるかを確認する、なければFalse、あればそのグループ内の数字のcntを減らし、次に進む
  • 全て完了すればTrueとなる

自分は、sortしたAと比較しましたが、グループ分けしたそれぞれの配列をsortしてみるという方法でもできます。下記の解説が詳しいです。

www.youtube.com

E問題

atcoder.jp

E問題は、試験中取り組まなかったのですが、解説見ずに挑戦し解くことができました。 ポイントは、下記だと考えます。

  • kが3以下と少ない
  • 出次数が3以下が保証されいている

そのため、下記の図のように探索範囲が狭い(3通り * 2通り * 2通り= 12通り)ことがわかります。

図3 ABC254 E なぜ、探索範囲が狭くて済むのか?のイメージ

そのため、隣接リスト等でグラフ構造を変数で保持できて、BFSが使えれば、TLEせずに解くことができます。水色diffですが、一見すると難しそうですが、上記に気付けさえすれば、正直茶色レベルでもおかしくないのかな?と思うような問題でした。

from collections import deque

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
ans = []
Q = int(input())
for _ in range(Q):
    x, k = map(int, input().split())
    cnt, finds, queue = x, set([x]), deque([(x-1, 0)])
    while queue:
        cur, dis = queue.popleft()
        for nxt in edge[cur]:
            if dis + 1 > k or nxt + 1 in finds:
                continue
            cnt += nxt + 1
            finds.add(nxt+1)
            queue.append((nxt, dis + 1))
    ans.append(cnt)
print(*ans, sep="\n")

Submission #32247915 - AtCoder Beginner Contest 254

D問題

atcoder.jp

個人的には、解けそうと思って勘違いあって、時間潰してしまいましたが、結局解説見ないと解けなかったです。シンプルだけど整数苦手でこの手の問題落としがちだなぁと思っています。

図4 ABC254 Dでまず考えたこと

まず、i, j の全探索は上記の通りでTLEするので、どのようにして効率よく考えられるか?を考えます。 そこで、平方数は 5 *5 みたいに(1, 25), (25, 1), (5, 5) の3通りで、それぞれN以下のもの探せば良さそうと思ったのですが。この時、36みたいなパターンもあることを抜けてサンプル通らず、実際全探索で書いてみて、22 * 33 みたいなの、どう数え上げよう。。。と思って時間切れになりました。

atcoder.jp

www.youtube.com

公式解説や、かつっぱさんの動画でも解説されていますが、平方数とはなんぞや?何と何書けたら平方数になるの?というところがポイントな気がしています。

図5 平方数と掛け合わせたら、平方数になる場合に関して

解説だとわかりにくいのですが、要は平方数は素因数分解した際に、すべての次数が偶数になるものである。そして、i*jが平方数になる場合は、i, jをそれぞれ因数分解した際にできる最大の平方数(=解説では、約数の内最大の平方数といっている)と、それ以外と考えた時に、それ以外のもの同志を掛け合わせて平方数にする必要がある。ということは、それぞれは同じ数でないといけない!ということがわかると思います。

from collections import defaultdict

N = int(input())
cnt = defaultdict(int)
for i in range(1, N+1):
    j = 2
    while i > 1 and i >= j*j:
        while i % (j*j) == 0:
            i //= j*j
        j += 1
    cnt[i] += 1
ans = 0
for k in cnt:
    ans += cnt[k]*cnt[k]
print(ans)

Submission #32289363 - AtCoder Beginner Contest 254

コードにすると上記のように非常にシンプルになります。ポイントは下記だと思います。

  • 1 ~ N までの数のうち、約数のうち最大の平方数であるもので、自分自身を割った数(解説で言う i/f(i)) のそれぞれの個数を調べる
    • 例えば、4や9は cnt[1] += 1される
  • i, jは同じ k 同士である必要があるので、それぞれの掛け合わせることで、場合の数が求められる

ということで、無事に解けました。計算量は最大でもO(N3/2) かなと思います。が、若干怪しい。。。O(NlogN)な感もある気がする? ちなみに、大きい順から割ったり、事前の計算結果を使ったら早くなるのでは?と思ってtryしましたが、sqrtが重いのか、効果はありませんでした。

atcoder.jp

感想

入緑して、また伸び悩んできたなと思います。ここからはE問題を解くか、Dまでを早解きのどちらかを続けて水パフォ以上を出し続けないとrateが上がらないので、定型90問で飛ばした問題を解き直したり、時間を見つけて水色diff埋めをして、力をつけて、E問題を解けるようになりたいと思います。

自分のこと、それなりのエンジニアだと思ってたけど、緑コーダーになるのに1年かかった話

はじめに

2021年2月6日(ABC191) からAtcoderに参加し、2022年3月12日に緑色になりました

その後も、無事なんとか緑色で維持し続けています(2022年4月23日 rate 817)

atcoder.jp

巷では、数ヶ月で水色等になる人もいる中で、時間かけてるし、結構頑張っているけどなかなか結果が出ない人も多いのではないかと思います。 そういった人に対して「こういう人もいるんだ」とか「もう少し頑張って続けてみよう」とか思っていただければいいなと思って書きました。

進歩の速度は人それぞれで、かけられる時間も環境によってマチマチの中で、自分なりにやってきたことを共有し、1人でも多くの人に参考になることがあれば嬉しいです。

スペック

著者のスペックに関しては下記になります

  • エンジニア歴 約8年

    • NW & Securityの研究開発
      • インフラ構築や運用も経験
    • 様々な事業会社で開発(基本Web系)
      • Tech Leadも経験
    • SRE チームも立ち上げ、SRE & DRE(Data Reliability Engineer) として業務に従事
      • チームリーダも経験
    • MLエンジニアとしていくつかのProjectを経験
      • マーケティング関連(バイオ関連のデータソース)で、必要な予測モデルを生成し、納品
      • セキュリティ観点でのモデルを作成し、不正ユーザや、bot検知するモデルを作成し、実際に運用
    • PM/PL業でのマネジメント経験も少々
  • プログラミング

  • 家族構成 子供2人

    • 妻との共働きで、家事育児もあるため、エンジニアリングの勉強時間は限られている

取り組んだキッカケ

Atcoderに取り組んだのは、数年前に外資系の会社でSoftware Engineerの面接を受けたことがキッカケになりました。 自分自身、様々な業務でエンジニアとして働いてきて、それなりに自分のスキルに自信を持っていましたが、全く何も通用せず散々たる結果になりました。

qiita.com

有名なOSS commiterでも試験が解けずに落ちてしまうことがあるようです。 自分の場合は、一応情報系のことを大学で勉強しましたが、例えば「木構造」がどういうものなのかは知っていても、0からフルスクラッチで書いたことはなかったですし もし必要があれば、組み込みや3rd partyのライブラリを使って解決してました。

また、アルゴリズムに関しても、「ダイクストラ法」を知っていて、机上の手計算しながら説明はできるが、実際コードに短時間で落とし込むのは難しいといった感じでした。 計算量や、メモリ効率に関しても、そこまでシビアな中で開発しなかったのでその辺りも結構なんとなくできてしまったのかな?とも思います。

itnews.org

コーディングテストに関しては賛否があるようですが、シリコンバレーを中心としたIT企業では現状実施されていますし、自分自身「データ構造やアルゴリズム全然わからん」ってことに気づけたので、ちゃんと勉強したいな!と思うようになりました。

Atcoder 緑色のレベル感

過去、Atcoder社 社長のchokudaiさんは下記のように述べています

chokudai.hatenablog.com

緑色 (Cランク R800~1199 上位30%) 緑色になれれば、「競技プログラミングに熱心に取り組んでいる人」と考えて問題ないでしょう。 if、forはもちろん、それを組み合わせて2次元配列に対して操作をしたり、深さ優先探索幅優先探索などのキューや再帰を使った実装も出来る。 簡単な動的計画法の問題や、数学的に工夫する問題など、計算量の工夫も出来始める。

が、近年の参加人数の増加により、全体の底上げが図られているような気がしており 下記でも述べられていますが、若干上振れしていると自分も思っています

zenn.dev

個人的には、chokudaiさんのブログで言うところの緑と水色の中間くらいかな?と思ったりします

緑色になるまで

ratingの遷移は下記の通りですが、3つのステージに渡って、やったことを紹介できればと思います。

  1. 第一時成長期(約 3ヶ月)
  2. 伸び悩み期(約 8ヶ月)
  3. 再成長期(約 1ヶ月)

図1. Atcoderのratingの遷移

当初の計画

qiita.com

まず、上記の記事を見てどのように勉強していくかの計画を立てました。 正味、結構エンジニアやってきてるし、半年くらいで水色くらいにはなれるだろ!って思ってました(笑)

プログラミング言語としては、C++でいくか、Python3(pypy)のどちらを使うか迷いましたが、自分の使い慣れた言語がいいと思い、Python(pypy)でやることにしました。 C++と違い、速度面、競プロでよく使う標準ライブラリがない(ex. python では multisetがない) などの問題はありましたが、緑になる分にはそれほど大きな問題はないかなと、現時点では思っています。

第一時成長期(約 3ヶ月)

やったこととしては

  • 毎週 Atcoder Begineer Contest(ABC) に参加する

    • 下の子が0歳児の中、妻にはだいぶ迷惑をかけたが、なんとか時間を確保した
      • お風呂入れる時間が押してしまって、参加が遅れたりしたこともあったり、旅行先のホテルで寝かしつけた後、参戦したりしたこともあった
  • コンテスト以外の時間での、勉強時間の確保

    • なるべく毎日1時間以上コードを書く(2時間程度が理想)
    • 空き時間の確保や、他の趣味の時間を削る等で対応
  • 参加したコンテストの解説記事を書く

    • 結構時間とられるので、今はやめてしまってますが、近いうち再開しようと思っています。。。

kazu0716.hatenablog.com

github.com

github.com

github.com

qiita.com

この辺りは、 レッドコーダーが教える、競プロ・AtCoder上達のガイドライン で紹介されているものを踏襲した感じになります。 ただ、あまり勉強せずともABCのC問題くらいまでは解けることが多かった。が、D問題から先はさっぱりという感じでした。

図2. 茶色コーダになるまでのコンテスト結果

ABC Likeなコンテストでミスをしてratingを下げたこともありましたが、順調にrating を上げていき茶色になることができました。 また、基本データ構造の計算量に関しては知らないと、正しく計算量の見積もりができないので、下記を頭に叩き込みました。

wiki.python.org

伸び悩み期(約 8ヶ月)

茶色になってからですが、rating が伸び悩みます。ABC で C問題までしか解けないというのもあり、パフォーマンス相当のrating になったというのが大きな原因かと思いました。 なので、方針としては下記の2つを進めていくことにしました。

  • 早く、正確に現在解ける問題を解けるようになる
    • AtCoder Problems で、C問題までを早く、正確に解くことを進めた
    • 対象は、現行の形式になった、ABC126 よりも新しいものとした
      • 3ヶ月程度で完了した(2021/8/23 commit)

github.com

D問題以上特には、競技プログラミングでよく用いられるアルゴリズムやデータ構造が理解し、使いこなせる必要があるので、分野別 初中級者が解くべき過去問精選 100 問を解き進めるのですが、新しいアルゴリズムを勉強して理解して、例題を解くのは自分にとっては大変でした。

英単語や文法の暗記系と違って、アルゴリズムという取っ付きにくいものを理解して、使いこなせるようになるには、まとまって集中する時間を確保しないと難しく、隙間の30分やって、別の時間60分という形で進めると非常に効率が悪かったです。 子持ちで、フルタイムの仕事もあるので、平日/休日で決まった時間を確保することが難しく、特に育児は突然予期せぬことが起こるので、その都度対応する必要があったので、その度にストレスを感じてました。

また、「自分が解けなかった問題の復習」に関してもそうですが、解説読んでも理解できないし、考えているときに中断して、また再開して・・・という感じで、非常に苦しかったです。

停滞期に突入する

Atcoder ProblemでのD埋めも終盤に差し掛かり、必要なアルゴリズムも一通り勉強終わったけど、中々D問題がコンテスト中で解けないといったことが続きました。 正直、結構問題解いてるし、自分で解く分には解けることもあったので、なんでなのかなーと思ってましたが、そこまで深く考えてなかったです。

が、いよいよABCのD埋めも終わったところで、解いている問題量に対して、結果が伴ってきてない実感が強くなりました。 結論言うと、解いて終わりで復習してないってのが原因だと思うのですが、2度同じ問題解く気がしなかったので、競プロ典型 90 問を解くことにして、さらに演習を進めると言う選択をしました。 今思うと、勉強法を見直すべきだったかなーと思うので、今後取り組む人は、一度解いた問題も復習すると良いと思います。コンテスト後に解けなかった問題解いて、さらに1週間後解いてみるとかすると良いかなと思います。

また、解けなかった時に、解説見てもわからない時に、Youtubeでの解説動画を見てましたが、これをみて分かった気になっていたと言うのもつまづきの原因かもしれません

www.youtube.com

ガムシャラに問題を解き進める

競プロ典型 90 問を進めていきます。最初は★5以下の問題を解いていましたが、まずはD問題をコンテスト中に解けることが目標なので、★4以下にして、90問解きました。解いた問題に関しては、READMEにまとめてみたので、興味ある人はみていただけると良いかと思います。

github.com

また、DPが苦手だなーと思ったので、Educational DP Contest / DP まとめコンテストにも取り組みました。あまり難しい問題までやっても解けないので、J問題までやりました(「最適化問題」以外にも使えることがわかるという説明があったので。)。

github.com

非効率かもしれないですが、Dを埋めた後取り組んだのもあって、それなりにスムーズに解き進められて、かつ過去問の類題もあったので良い復習になったのかなと思います。

定期的にCでコケるが続く

ratingは長期的に見ると、少しづつ上がっているのですが、上がっては下がるを繰り返していました。これが、停滞期の原因であることに気づくのがとても遅かった気がします。

下記をみると顕著なのですが、定期的に -30 前後を食らっています。これは、C問題が解けなかったり、めちゃくちゃに時間かかったコンテストになります。

図3. 停滞期のコンテストの結果

コンテスト中に解けなかった問題で、かつ灰色difficulty(rate: 400以下の人で50%の確率で解けると思われる問題)を見返してみると、基本的な数学/ 情報科学の基礎力があれば解けるような問題でした。

なおかつ、コンテスト中に全く歯が立たない!と言うことではなく、サンプルは通ったけど、WAが取れずに終了してしまうという傾向があることがわかりました。 ミスの傾向としては、下記がある気がしています。

  • 問題文の読み間違い/ 勘違いをしている(ex. 前提となっている条件を見落として、勝手に問題を複雑にしている)
  • コーナーケースを想定できていない(ex. N=0の場合の場合分けなど)
  • 単純な実装ミス

debug 力は一朝一夕では身につかないので、この辺りの記事も見ながら気をつける!ということを続けました。

qiita.com

また、Cコケは不可避で起こったら、復習して周辺知識深め、また次頑張ればいい!と言う風に割り切ることにしたことも良かった気がします。 あまり、rating に拘らず、楽しんでやる心を改めて思い出して取り組むようにしました。

ここまで、勉強したアルゴリズム/データ構造に関して触れていないですが、2 個の基本アルゴリズムをマスターする!で触れられてるもの以外、特に勉強していないです。強いてあげると、

from pypyjit import set_param
set_param("max_unroll_recursion=-1")

といったことを +a で勉強しました。

再成長期(約 1ヶ月)

停滞期ながらも、ひたすら精進を続けていたら急にD問題が解けることが続くようになりました。 原因はわかりませんが、今まで解いてきた問題が身になったということに尽きるのかなと思います。

図4. 再成長期のコンテスト結果

また、停滞期であっても続けられたのは、前職のOB/OGのSlackで競プロやるメンバーのチャネルがあって、そこで結果を報告しあったり、教えてもらったりしたこと。 現在の会社でも、毎週競プロの勉強会を主催し続けてきたこと、その中で自分より遥か上の人たちの知識や、考え方を吸収したり、教えてもらえたこと。 が大きかったなーと思います。結構1人でやると、辛いし、なにやってんだろ?って思うことも多かったんですが、仲間がいることで乗り越えられたような気がします。

まとめ

1年以上の時間をかけて、合計600問以上の問題(取り組んだ問題は、下記にまとめています)を解くことで、緑色コーダになれました。進歩の速度は人それぞれで、他の人のブログをみると3ヶ月とかでなっている人も多い中だと、自分は相当遅い方かな?と思います。

github.com

ただ、アルゴリズム/ データ構造の自力だったり、かけられる時間だったりで、この期間は大きく変わるかな?と思うので、他人と比べず、自分のペースで精進続けられればいいかなと思います。 もし「全然茶色から抜けられない」とかって人がいれば焦らずコツコツ続けるのがいいかなと思います。モチベーション管理が難しければ、友達や職場で勉強会立ち上げて取り組んでみるのは1つ選択肢としてあるかもしれないです。

競プロって、データ構造/ アルゴリズム仕事にしたりしない場合、使わないし意味ないんじゃないか?みたいな議論もあります。が、個人的には、下記の点において大きく能力が向上したと感じるので、1エンジニアとしてやってよかった、今後の実務に生きる!と感じています。

  • 計算量/ メモリ効率も見積能力の大幅な向上
  • 問題を考察し、実装に落とす速度の大幅な向上
  • 基本ライブラリや言語仕様に詳しくなった
  • 実装速度の大幅な向上
  • コーナーケースの想定考察力向上(テスト書くときとかに役立ちそう)
  • コードを実行しない中でのdebug能力(静的解析)の大幅な向上

今後ですが、水色になるにあたっては、問題の考察力がたらないので、しっかり考察して筋の良い実装方針立てる力を磨いていければと思います。 水色いつなれるかわかりませんが、色変したらまた記事を書こうと思います。

長文にもかかわらず、最後まで読んでくださりありがとうございました。

Leet code 141. Linked List Cycleを解いてみた

目的

  • 競プロの勉強の成果を図るべく、コーディング面接対策のために解きたいLeetCode 60問を解いた問題を解説していく
    • せっかくなので60問解説できるように頑張る

1kohei1.com

  • 今回は 「141. Linked List Cycle」をpython3で解いた
    • といっても、python3 以外で解く予定は今のところないw

問題

leetcode.com

日本語訳

Linked Listの先頭であるheadを指定して、Linked ListにCycle(= 閉路 )が含まれているかどうかを判断します。

次のポインタを継続的にたどることによって再び到達できるノードがリストにある場合、Linked ListにはCycleがあります。 内部的には、posは、tailの次のポインターが接続されているノードのインデックスを示すために使用されます。 posはパラメータとして渡されないことに注意してください。

Linked ListにCycleがある場合はtrueを返します。 それ以外の場合は、falseを返します。

前提知識

連結リスト(Linked List)

今回は「単方向連結リスト(singly-linked list)」を扱う

問題では、ListNodeが下記のように定義されており

  • val: Nodeの値
  • next: 次のListNode

で構成されている コードでは下記のようになる

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

イメージ図にすると下記のようになっており、ひたすらnextをたどり続け、 next = None となったら List の終端となる

図1. Linked List

Atcoderでは、pythonで標準で用意されている List のみ利用していたが、実際には 他言語 配列(array) に近いもので 例えば、index番号を指定して O(1) で値が取得できるといった特徴は Linked Listにはない機能であったりする

docs.python.org

そのため、少し戸惑ったが、localで問題を解く環境を再現するために下記のようなコードを書いて対応した(leetcodeの問題を解く分には不要であるが、ローカル環境でdebugしたかったために作成した)

class LinkedList:
    def __init__(self):
        self.head = None

    def add(self, val: int) -> None:
        if self.head is None:
            self.head = ListNode(val)
            return
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = ListNode(val)

    def create_loop(self, pos: int) -> None:
        """
        pos is 0-indexed
        """
        if pos == 0:
            Exception("Couldn't create self-loop")
        cnt, cur = 0, self.head
        dep, end = None, None
        while cur:
            if cnt == pos:
                target = cur
            dep = cur
            cur = cur.next
            cnt += 1
        if dep is None or target is None:
            Exception("Couldn't create loop")
        dep.next = target

    def show(self) -> None:
        cur = self.head
        while cur:
            print(cur.val)
            cur = cur.next

例えば、 add で値を Linked Listに追加する場合は、Headから値を辿り、 終端(next = None) の箇所を見つけたら ListNodeを作成し値を設定し、nextを更新する

create_loop では、pos(問題では与えられない) を指定し、終端を pos に連結する。posに相当する ListNodeは終端まで探索する途中に出現するので、出現した段階で保持しておく

当初のアプローチ

問題としては、Cycleの有無を判定すれば良いので、headから探索し、探索した ListNodeを set() で保持しておく

wiki.python.org

setは高速(平均 O(1))で、同一の要素があるかどうかを探索できるため、nextが既に探索済みであれば、それはCycle があると判断できると考えた

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        """
        Use hash table

        Time complexity: O(n)
        Auxiliary Space: O(n)
        """
        cur, s = head, set([])
        while cur:
            if cur in s:
                return True
            s.add(cur)
            cur = cur.next
        return False

コードとしては上記のようになる。 The number of the nodes in the list is in the range [0, 10^4] とあるので、 finds = [False] * pow(10,4) といったlistを用意しておき、探索した箇所をTrueにしていくといったアプローチでも同様に解くことができると思われる。

この際には、計算量としては O(N) になるが、set() に探索した ListNodeを保持するため、メモリ効率は悪い(O(N)) コードとなっている。 Follow up: Can you solve it using O(1) (i.e. constant) memory? とあるため、より不要な値を保持せず解く方法がないかを考えた。

フロイドの循環検出法 を用いたアプローチ

考えるにあたって、下記を見て様々な loop の検出方法があることを知る

www.geeksforgeeks.org

その中に、フロイドの循環検出法(Floyd's cycle-finding algorithm) というものがあることを知る。 下記の、記事が非常にわかりやすいが、要はウサギ(1度に2step進む)と亀(1度に1step進む)を同時に、同じLinked List上を進ませた場合に、Cycleがある場合はウサギと亀はどこかのNode上で出会うといったことである。

note.com

コードに書き起こすと下記のようになるが、headもしくはhead.nextがNoneの場合はCycleは作成できないのでFalseとなる。 その後は、slow = head, fast = head.next として slowは1つづつ、fastは2つづつ進めていき、それぞれが同一のListNodeとなった段階でwhile文を抜けTrueを返すというコードを書いた

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head is None or head.next is None:
            return False
        slow, fast = head, head.next
        while slow != fast:
            if slow.next is None:
                return False
            slow = slow.next
            for _ in range(2):
                if fast.next is None:
                    return False
                fast = fast.next
        return True

2つのアプローチの結果

比較は下記になるが、Leetcodeでは提出のたびにRuntime(速度)もMemory(メモリ使用量)も変わるため、参考までに

  • 当初のアプローチ: 52 ms 17.8 MB
  • フロイドの循環検出法を用いた場合: 58 ms 17.5 MB

フロイドのアプローチの方がメモリ使用量が少ないことが伺える。 これは、保持する値がslow, fastでそれぞれ1 ListNode のみを保持するからだと考えられる。

まとめ

今回は、「141. Linked List Cycle」を解説してみた。 実際、解くことは簡単であった(easyなのでそれはそうなのだが)が、メモリ効率まで意識してAtcoderでは解いていなかったので良い経験になったのと LinkedListを自分で作ってみるみたいな経験は、今までしたことなかったので良い勉強になった。

解説したコードに関しては下記にあるので、もしローカルで動かしたい場合は利用してみると良いかもしれない。

github.com

次回は、「142. Linked List Cycle II」を解説してみようと思う。

leetcode.com

Atcoder-ABC226をpythonで解いてみた

目的

  • Atcoderで上を目指すべく頑張っている中でABC226を解いたので、解説してみる
    • pypy7.3を使って解いている

A問題

atcoder.jp

考察

  • 問題文通りに解けば良い

実装

X = input().split(".")

if int(X[1][0]) <= 4:
    print(X[0])
else:
    print(int(X[0])+1)

結果

B問題

atcoder.jp

考察

  • 与えられる中で同じ数列がある場合があるので、それを除外してcntする
    • 今回はsetに対して、tuple型にした数列を入れていき、重複を排除した
    • setの要素としてはimmutableである必要があるためtupleを利用(listだとダメ)

docs.python.org

実装

N = int(input())
ans = set([])

for _ in range(N):
    length, *line = map(int, input().split())
    ans.add(tuple(line))

print(len(ans))

結果

コンテスト中は、謎にlength別にsetを用意して重複排除してた

C問題

1WA出してしまったが、なんとか解くことができた

atcoder.jp

考察

  • 技がN個あり、それらを覚えるためには、事前に覚える必要な技がある

    • i番目の技を覚えるのに必要な技は、i=1, 2, ... , i-1 であることが保証されている
    • そのため、後ろから探索していけば良さそうな気がする
  • 技Nの習得な、技をDFSでたどっていき、習得までに必要な時間をcountしていく

    • 既に覚えた技を2重で習得し、2重で時間をcountしないために、習得した技であるかの状態を保持する

実装

N = int(input())
master = [False]*N
A, T = [], []
ans = 0

for _ in range(N):
    t, k, *a = map(int, input().split())
    T.append(t)
    if k == 0:
        A.append([])
    else:
        A.append(list(a))

ans = 0
stack = [N-1]
while stack:
    cur = stack[-1]
    if not A[cur]:
        stack.pop()
        if master[cur]:
            continue
        master[cur] = True
        ans += T[cur]
    else:
        nxt = A[cur].pop()-1
        if master[nxt]:
            continue
        stack.append(nxt)

print(ans)

結果

コンテスト中は、変数取得が余りよろしくない感じだったw

D問題

C問題に時間使ってしまって解けなかったが、時間あっても解けなかったと思う

atcoder.jp

考察

  • 全ての各点の間を移動できるような、ベクトル(a,b)を数え上げる

    • ベクトルの種類を最小にする必要がある
    • (2,4) みたいな操作は (1,2) を二回実行でも実現できる
      • つまり、(2, 4) は (1, 2)に包含される
  • 傾きが同じ成分のベクトルを1つにまとめることを考える

    • 割り算を使うと誤差が発生する
    • (a,b) の最大公約数(gcd(a,b))で割ることのがいいらしい
      • (2, 4) -> (1, 2) になる

atcoder.jp

実装

from math import gcd

N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)]
ans = set([])

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        dx, dy = P[i][0]-P[j][0], P[i][1]-P[j][1]
        g = gcd(dx, dy)
        ans.add((dx//g, dy//g))

print(len(ans))

結果

gcd使って、傾きの同じベクトルをまとめられることに気づけば、実装は容易

まとめ

  • 絶賛停滞中w

f:id:kazu_0716:20211113185025p:plain
ABC226 結果

  • 解いていた思うのは、下記なので今後修正していきたい

    • B, C解くのでも結構時間がかかっている

      • 問題を読解し、要件(=何をすべきか)を見極めるまでが、結構遅い気がする
      • 立てた方針を実装するのに時間がかかっている
        • どう実装するのか、考えている場合より、作ったものが思った通りの結果が出なくてdebugしている時間が長い気がする
    • 緑diff以下の問題を埋めていて

      • 確かに、解説見ずに解けることも増えてきたが、1時間以上かかる場合も多い
        • 原因はB, Cのところと同じ場合が多い
  • 沼にハマらないようにコードを書くのと、ハマっても抜けられるように鍛錬していくぞ!