30歳で競プロに目覚めた霊長類のブログ

チンパンジーと一般人のあいだ

Atcoder Beginner Contest 075

5日ぐらい前のやつです。

結果

A,B,Cの3完。タイム23:33。302位。
レート変動なし。

感想

水色コーダーになってから初めてのABC。
これから青コーダーを目指すにあたってサクッと全完する... つもりが、
D問題で迷宮に陥り、時間切れ。
精進しなきゃ。。

A One out of Three

A - One out of Three

素直にif-elseする問題。(説明になってない)

A,B,C = map(int,input().split())
if A == B: print(C)
elif B == C: print(A)
else: print(B)

すごいと思ったのが、if文を使わずにXOR演算で print(A^B^C) みたいに解いた人がいたらしい。
確かに、同じ数を偶数回XORするとその数は消えるから、答えが残るね。
絶対に思いつかないな〜。

B Minesweeper

B - Minesweeper

いわゆるマインスイーパの爆弾の位置が与えられて、空きマスについて、8近傍に爆弾がいくつあるかを求める問題。

これも基本的なif-elseとfor文が使えればできそう。
でもABCのBにしては実装量が少し多い。

H,W = map(int,input().split())
src = [input() for i in range(H)]
 
ans = []
for row in src:
    ans.append(list(row))
 
dxy = [(-1,-1),(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1)]
for y in range(H):
    for x in range(W):
        if src[y][x] == '#': continue
        c = 0
        for dx,dy in dxy:
            if x+dx < 0 or x+dx > W-1 or y+dy < 0 or y+dy > H-1: continue
            if src[y+dy][x+dx] == '#': c += 1
        ans[y][x] = c
 
for row in ans:
    print(''.join(list(map(str,row))))

2行目のsrcに文字列の配列を読み込んでいるけど、
Pythonだとsrc[0][1] = '1'みたいな文字列への代入ができなくて、
仕方なく答えを書き出す用のansという配列の配列を用意してる。
最終的にansを結合して出力してる。(なんか微妙な気が。。

あとは、8近傍の調べ方がいくつかテクがあるっぽい。
解説のソースコードを抜粋すると、↓の書き方だった。

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

でもこれ、うまく説明できないけど、なんかモヤっとする...。
dx[i]dy[i]はセットで意味をなすので、(dx[i],dy[i])みたいにまとめたいと思ってしまう。

というわけで、せめてもの抵抗として(笑) (dx[i],dy[i])とタプルでまとめたコードを貼り付けた。
でも、カッコで囲ってるぶん、タイプ数が少し多いような。
競プロは早さを競うのだからうだうだ言ってられませんがな。

次からは素直にdxdyでやるか。(ズコー

ちなみに、上で載せた私のコードは実はブログ用に書き直してて、本番でAC取ったのは愚直なif-elseの山。

(おまけ)ACは取ったけど載せるのをためらったコードは↓
Submission #1682548 - AtCoder Beginner Contest 075

C Bridge

C - Bridge

二重辺や自己ループのない無向連結グラフがあって、取り除いたら連結じゃなくなる辺がいくつあるか。
以下私の回答。

N,M = map(int,input().split())
es = []
for i in range(M):
    a,b = map(int,input().split())
    a,b = a-1, b-1
    es.append((a,b))
 
parent = None
def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]
def is_same(a,b):
    return root(a) == root(b)
def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    parent[ra] = rb;
 
ans = 0
for i in range(M):
    parent = [k for k in range(N)]
    for j,e in enumerate(es):
        if j == i: continue
        a,b = e
        unite(a,b)
    a,b = es[i]
    if not is_same(a,b):
        ans += 1
print(ans)

Union-Findを使って解いた。
Union-Findは、競プロ歴5ヶ月の私が知ってる知識をざっくり説明すると、

  • グラフのある頂点とある頂点が繋がってるかどうか高速に判定するよ
  • 辺がない状態から、辺を追加しながら構築するよ。構築の途中でも判定できるよ
  • 判定も追加もほぼ定数時間(ちょうはやい)。アッカーマン関数(とてもでかい)の逆数だとか
  • 初期化するのだけO(N)かかるよ(N:頂点数)

上記コード中に出てきたroot()is_same()unite()がUnion-Findだけど、
スニペットに入れてたやつそのままなのでかなり楽できた。

あとは、全ての辺をループして、辺eを除いたグラフでUnion-Findを構築して、
辺eの両端が繋がってるかを判定していけばいい。

計算量は、辺ごとにUnion-Find初期化+構築でO(N+M)なので全体でO(M(N+M))かな?
NもMも小さいので大丈夫!

ちなみに、想定解ではUnion-FindじゃなくてDFSで解いてたみたい。
DFSは思いつかなかったので両方思いつくようになりたい。