グラフ系の問題: ABC166 C - Peaks / ABC068 C - Cat Snuke and a Voyage

問題1

atcoder.jp

問題タイプ

グラフ

• グラフの問題に慣れるのに良い問題.
• それぞれの展望台と繋がっている道のグラフを作って、それらを比較する.

気を付けるところ

• 展望台Nから展望台N'を比較する際に、道がある全ての展望台より自展望台が高い場合のみ、countをインクリメントすること.
  • 展望台N > 展望台N'がひとつでも見つかればカウントインクリメント、ではWAになるので注意.
• 一つも道がつながっていない展望台も "良い展望台"としてカウントすることを忘れずに.

サンプル

n,m = map(int, input().split())
h = list(map(int, input().split()))

path = [[] for _ in range(n)]

for i in range(m):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    path[a].append(b)
    path[b].append(a)

cnt = 0
for i in range(n):
    # 道が1つもない独立展望台
    if len(path[i]) == 0:
        cnt += 1
    else:
        isHigher = True
        # 現在の展望台から道がある展望台の高さをチェック
        for j in path[i]:
            # 自展望台より高いものがあればFalse
            if h[i] <= h[j]:
                isHigher = False
        # すべて自展望台より低かったのでカウント
        if isHigher:
            cnt += 1
        
print(cnt)

---

問題2

atcoder.jp

問題タイプ

• めっちゃいいグラフの問題だと思いました.

気を付けるところ

• 最初、結局は片道で 島1 → 島N' → 島Nとなればよいから、グラフを片道しか作らないとかいう試みをしてみましたが、全然だめでした.
• グラフ問題はちゃんと島1 → 島N'の関係を作ったら、反対の島N'の関係も作らないといけないということがよくわかりました.
• この問題は、島1 → 島N'への関係性を把握した上で、島N'の関係性から島Nの関係があるかどうかを見極める問題.
• setを使うのもアリなようだが、初学者のワイは普通に配列でやったけどACでした.

n, m = map(int, input().split())
path = [[] for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    path[a-1].append(b-1)
    path[b-1].append(a-1)

# 島1の関係のある島をループさせる
for i in path[0]:
    # 島N'(島1と関係がある島)の中に、島Nへの関係があるかチェック
    if n - 1 in path[i]:
        # あればOK
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

問題3

atcoder.jp

問題タイプ

• 有向グラフ、サイクル、有向閉路.
• ある頂点から進んで同じ頂点へ戻ってくる（ループする）ようなグラフを見つけ出す問題.

気を付ける点

• なんのこっちゃ問題を見ても全く意味不明でした.
• 答えがあることが保証されているので、まずはN回ループさせてみるのがよいらしい.
  • そうすると、どこかでサイクルになるパターンが見つかる.
• その後は、サイクルになっているindexをansのarrayに加えて、一度出現したところは0などに上書きしておくと、サイクルになっている関連indexを探し出すことができる.

サンプル

N = int(input())
# 最初のindexを0埋めにしておく
A = list(map(int, ("0 " + input()).split()))
# 出発地点はどこでも実はよい
now = 1

# 予めN回移動する
for _ in range(N): 
    now = A[now] 
B = []
# グラフのindex箇所が0でない限りループ
while A[now] != 0:
    # 現在のindexのグラフ値を取得
    tmp = A[now]
    # 現在のindexのグラフ値を0に上書き
    A[now] = 0
    # 次の関連があるindexを保持
    now = tmp
    # サイクルグラフ用のarrayに追加
    B.append(now)

# Output
print(len(B))
print(*B)