😇

ABC198 E - Unique Color

2021/04/15に公開

AtCoder

tech

問題のリンク

この問題を解ける様になるには具体的に以下の精進が必要です

木の定義を理解する
色(整数)の管理の仕方を理解する
一筆書きのように、木を走査する方法を理解する

1について

木の定義を理解するためのStepは以下です。

無向グラフ、有向グラフの問題を解いてグラフに対する抵抗感をなくす (ここは気合)
1.で解いている中で「木」という言葉が文中に出てきて、なんとなく「木」というのがあるんだな、という意識をする
無向グラフのようにいろんな辺を行き来することがないんだな、というのを、幅優先探索とかをソラで書く練習をするなかで、納得が行くまでグラフの問題を解き続ける
「木グラフ違い」とググるとか本を読んだりして「木」に対する解像度が徐々に上がる
「木は、N頂点で辺がN-1本、閉路がない」といった言葉の意味が、自分の経験として徐々に分かる
「木」「グラフ」の問題が好きになる

Step1が関門です。グラフはinputで受け取ることすら覚えにくいので、考えることを放棄しがちです。なのでまず、Step1を突破するためには以下を何も見ずに、書けるようになることをオススメします。inputで悩むと問題を解くモチベーションがなくなり、苦手意識がついちゃうので、inputを解決することは良い手だと思っております。最終的にはコピペしてもいいので、頭の中で、以下を復唱するのも良い練習かと思います。

N, M = map(int, input().split())
graph = [[] for _ in range(N)]

for _ in range(M):
  a, b = map(int, input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1) #無向グラフの場合

同様に、幅優先探索や深さ優先探索に関しても、書き方がよくわからず思考に集中できないとかありますので、ぜひ同じやり方で、何も見ずに書けるように精進しましょう。本番ではコピペしてもよいのですが、何も見ずに書く練習をしていないと、本番でそれを使って少しだけ直す、とかが焦ってできなくなるので、練習においては理解に重きを置きましょう。(本番では体が勝手に動いてコピペしてます)

解く問題は、[グラフ入門] (https://kenkoooo.com/atcoder/#/contest/show/74afe01c-55a5-424d-ad1d-f0291b0f489f) からはじめていくのが良いかと思います。

2について

1も大事ですが、こちらも大事です。色々問題を解いていると気づくと思いますが、整数の登場回数を管理してチェックするということは結構多いです。方法としては、以下があるかと思います。

配列の添字の数字を管理したい数字に見立て、Array[3] += 1とかする。
setを使い、かっこよく管理
Counterを使い便利に管理
辞書 {} で管理

できることはほぼ同じにはなるのですが、自分の得意な管理の仕方を身につけることが大事かと思います。また、配列だと、10^^9とかまで入れようとすると入らないので、辞書で管理をする必要も出てきます。管理の仕方は、身に付けないと本番で辛い思いをすることが多いと思います。今回私も、この管理のせいで解けなかったので... 整数の管理の仕方は典型としていいと思っております。

個人的に汎用性が高いと思っているのはCounterです。Counterですと、以下のように、配列のindexのような意識をせずに、値を雑に管理できちゃいます。しかもデフォルトで０が入ってくれるので、存在チェックとしても使えます!

import collections
l = []
C = collections.Counter(l)
print(C[0]) #0
C[0] += 1
C[10**9] += 2
print(C) #Counter({1000000000: 2, 0: 1})
C[0] -= 1
C[10**9] -= 1
print(C) #Counter({1000000000: 1, 0: 0})

if C[1] == 0:
    #存在チェックとしても使える
    print("1は登場していない")
    
if C[10**9] >= 1:
    print("10**9は一回以上登場している")

配列でも同じことが出来ます。
array = [0] * N
で初期化し、添字に対し、array[1] += 1とかしていくってことですね。はじめはこれでも良いとは思います。

setに関しては、使えるとかっこいいのですが、数字の管理が上記のように行うのが難しいと思われるので個人的に、最近まで使ってはいたのですがやめようかと思います。汎用性でいくと、数字の登場回数を使いこなすようにしておくほうが、他の問題にも適用しやすいと考えたためです。特に今回の問題もそうですが、訪問したことを解除するために、
st.remove(1)とかしてしまうと、
array[1] = 2だったとして、array[1] = 0となるようなことをしてしまうので、本来はarray[1] -=1 でarray[1] = 1としたいのに、setだとそれがうまく出来ません。
これが原因で、解法はすぐに浮かんでコードも合っていたのにその数の管理で間違えていました。setを使うのをやめて配列で登場回数を数えるという判断ができず、最終的に解けないという苦い思いをしてしまいました。

3について

ABC054 C One-stroke Path を解きましょう。この問題は、学びが非常に多いので家宝にしましょう。

以上1, 2, 3を精進していたので、ABC198 E - Unique Colorはすぐに解法は浮かびました。ただ、2の理解が甘く、思った以上に苦戦してしまいました。2を典型として意識づけて覚えることで、問題によって管理の仕方が変わるといったことをやめたいです。

1について

2について

3について

Discussion