ACL Beginner Contest 参加ログ・感想

本番は時間が合わず参加しなかったが、いつも通りメモを残しておく

内容
結果
どう考えたか + α
その他のおすすめの書籍
- アルゴリズムの参考書籍
- 最近ポチった書籍

内容

Python3でやっている。
参加ログ。
所感。
コンテスト中に何を考えたか。
コンテスト後に解説をみたり、少し整理したりしたくらいの内容。
問題の詳細で細かく書こうと思うものは別記事とする。
E以上はとりあえず現状自力では無理なのでDまで。解けるようになってきたら更新するかも

結果

ABC完。参加すればよかったと後悔。 Pythonを使っている人は、基本ACLを使いながらやるわけではないのであまり関係ないが使えないわけでもないらしい（Cython使いの方々が頑張ってくれている。）

twitter.com

仕様が変わるたびにやり方が変わりそうな気はしている。

どう考えたか + α

A - Repeat ACL

問題タイプ：文字列操作

同じ文字列を複数回繰り返すだけなので 文字列 * 回数 で繰り返せばいいだけ。

k = int(input())
s = 'ACL'
ans = s * k
print(ans)

B - Integer Preference

問題タイプ：範囲の包括条件

要するに、 a ... c ... b (dとbの大小はどちらでもいい) a ... d ... b (aとcの大小はどちらでもいい) c ... a ... d (dとbの大小はどちらでもいい) c ... b ... d (aとcの大小はどちらでもいい) となっているパターンはYesでありそれ以外はNoなので愚直に書けば

a, b, c, d = map(int, input().split())
if a <= c <= b or \
    a <= d <= b or \
    c <= a <= d or \
    c <= b <= d:
    print('Yes')
else:
    print('No')

もしくは aかcの大きい方とbかdの小さい方の大小関係で決まっているので、そのように書く

a, b, c, d = map(int, input().split())
if max(a, c) <= min(b, d):
    print('Yes')
else:
    print('No')

C - Connect Cities

問題タイプ：Union-Find

この問題と似ていると考えた。

blacktanktop.hatenablog.com

つまり、Union-Findでグループ分けするイメージである。なので、rootの数を数えて、その間を結べば良いのでrootの数 - 1となる。（今回は最小の繋がりで良いので直接つながっている必要がないから）例えば GroupA GroupB GroupCとなる時に

GroupA…GroupB...GroupCとつながれば十分なので（どういう組み合わせでもよい）

def find(target):
    if parent[target] < 0:
        return target
    else:
        parent[target] = find(parent[target])
        return parent[target]
def is_same(x, y):
    return find(x) == find(y)
def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x == root_y:
        return
    if parent[root_x] > parent[root_y]:
        root_x, root_y = root_y, root_x
    parent[root_x] += parent[root_y]
    parent[root_y] = root_x
def members(n, x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]
def get_size(x):
    return -parent[find(x)]
def get_root():
    return [i for i, root in enumerate(parent) if root < 0]

n, m = map(int, input().split())
parent = [-1 for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    union(a, b)
ans = len(get_root()) - 1
print(ans)

Union-Findわからんっていう場合は、以下の書籍をおすすめする。具体的には11章データ構造(4)：Union-Findに詳しく書かれている。

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

作者:大槻兼資
発売日: 2020/10/02
メディア: 単行本（ソフトカバー）

その他のおすすめの書籍

アルゴリズムの参考書籍

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

いわゆる、螺旋本。Aizu Online Judgeの問題を題材に解説されている。自分としては、 Aizu Online Judgeは最近はβ版運用中で、構成がアルゴリズムの項目ごとに問題がタグ付けされているようなイメージで、ここら辺弱いから集中的にやってみようっていう感じでできるので、いいと思っている。（AtCoderもそんな感じのリスト作って欲しい）ただ、この書籍はC++で書かれているのでPythonでやる場合はあくまでもその過程の考え方を参考にし自分で実装する必要がある。（AOJも解いているので、記事にしていこうかなぁ）

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

作者:渡部有隆
発売日: 2015/01/30
メディア: Kindle版

くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、