Python：初心者がARCに参加したら0冠で悔しかったのでAだけでも拾おうの回

# 初めに
AtCoderに参加した記録を残します。どのような考察をしながら問題に取り組んだかを記録していますので、必ずしも教育的なコードとは限りません。
始めたばかりの人など、どなたかの助けになれば嬉しいです。

## 成績
ARC159 0冠...
ABCじゃないことに直前で気づいたけどせっかくなので参加。やっぱりARC難しいね。
コンテスト後になんとかAはAC。

# 目次
[A - Copy and Paste Graphy](#a---copy-and-paste-graphy)




# A - Copy and Paste Graphy
[問題ページ](https://atcoder.jp/contests/arc159/tasks/arc159_a)
始点と終点の組がQ個指定されるので、有効グラフGにおいての最短経路を求める問題。有効グラフGはN×Nの隣接行列A（N<=100）をK回縦横に並べた隣接行列で表される。

## コンテスト中の考察
頂点数がNKで、K<=10^9なので取り合えず全探索したら間に合いません。今回の問題の特性上、同じような構造が出現することがなんとなく予想されます。ゴールから逆算して考えてみると**u%N == v%N**（u, vは任意の頂点）の場合、uとvに到達可能な頂点候補は同じになるので実際に考慮するべき頂点はかなり小さいと思われます（と思われるとかこういうガバガバ見積もりしてるから解けない）。
具体的な実装としては有効グラフGを逆向きに辿れるように、Gと全て逆の有効辺を持つG'を考え、G'に対してBFSを行います。この問では上述の通り、
> **u%N == v%N**（u, vは任意の頂点）の場合、uとvに到達可能な頂点候補は同じになる

のでG'のkeyはNあれば十分であると言えます。
これで解けそうな感じするんだけど、TLEが取れない…。

## コンテスト中のコード
```a.py
from collections import deque

N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
Q = int(input())
back_G = {i: set() for i in range(N)}
for i in range(N):
    for j in range(N):
        if A[i][j] == 1:
            k = 0
            while k*N+i+1 <= N*K:
                back_G[j].add(k*N + i)
                k += 1
                
for _ in range(Q):
    s, t = map(int, input().split())
    q = deque([(t-1, 0)])
    back_visited = set()
    mod_u = set()
    while q:
        u, depth = q.popleft()
        back_visited.add(u)
        if u%N in mod_u:
            if s-1 in back_visited:
                print(depth)
                break
            continue
        mod_u.add(u%N)
        if u%N in back_G:
            for v in back_G[u%N]:
                q.append((v, depth+1))
        if s-1 in back_visited:
            print(depth)
            break
    if not(s-1 in back_visited):
        print(-1)
```

## 改善点
### 着想面
構造が循環、keyがNのmod数分考慮すれば十分であるという考察はそこそこ的を射ているのですが、今回の問題ではkeyだけではなく、valueもNのmod数分考えるだけで良いようです（ついでにいうと、別にゴールから考える必要もない）。なぜそもそも両方mod取ってはいけないと思ったかというと、[コンテスト](https://atcoder.jp/contests/arc159/tasks/arc159_a)の入力例１のように
> N=3, s=1, t=4

の場合 modを取ると情報が潰れてしまうように思えたからです。
このようなケースを考えると、どちらかは圧縮せずに扱わないといけないように思われます。確かに何も考えずにmodを取るだけではダメなのですが、問題が発生するのは実は**始点だけ**なのです。なぜ始点だけが異端であると言えるのでしょうか？
コンテスト中は気づくことができなかったのですが、それは、始点だけ**グラフのルールに従って発生した頂点ではない**からです。入力例１を用いてもう少し噛み砕いて説明すると、4という頂点に到達可能であることがわかっている場合、グラフのルールに則って到達したのであれば、構造が循環しているので、同様に1にも到達可能です。一方始点は頂点１つのみが与えれられるので、他のノードの存在を確定させるような情報の膨らみを持たないわけです。
このような観点で考えると、異端なのが始点のみであることにも直感的に納得できるのではないでしょうか？
話をまとめると、経路探索は基本的に s%N -> t%N に対してBFSを行えばよいことになります。コーナーケースは先ほど述べた理由から、 s%N==t%N の場合だけです。ただし、この問題では
> s!=t

であることが保証されているので、単純にsを到達可能判定の集合に含めなければコーナケースを回避できることがわかります。
着想が甘かったなぁ。解いてる時はもっとコーナーケースあると思ってしまった...。

### コード面
かなりシンプルになった。GはAの隣接行列を順方向で辞書に変換している。通常のBFSと違うのは、dequeに初期値ではなく、初期値の隣接点を与えているところでしょうか？
```a_fix.py
from collections import deque

N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
Q = int(input())
G = {i: set() for i in range(N)}

for i in range(N):
    for j in range(N):
        if A[i][j] == 1:
            G[i].add(j)

for _ in range(Q):
    s, t = map(int, input().split())
    s = s-1
    t = t-1
    q = deque()
    for v in G[s%N]:
            q.append((v, 1))
    visited = set()
    ans = 0
    while q:
        u, depth = q.popleft()
        if u%N in visited:
            continue
        visited.add(u%N)
        for v in G[u%N]:
            q.append((v, depth+1))
        if t%N in visited:
            print(depth)
            break
    if not(t%N in visited):
        print(-1)
        
```


# 終わりに
把握ミスでARC参加したとは言え、0冠は流石に悔しかったので意地で頑張ってみました。私と同様に初心者だけど参加して何も得られなかった...という人がこの記事を読んで笑顔で競プロ続けられることを祈ってます！
書き始めたばかりで拙い部分も多いですが、みなさんと楽しく盛り上がれたらいいなと思っていますので、　今後ともよろしくお願いいたします！