【AtCoder】ABC225をPython3で解説（ABCD）

ABC225のA-D問題の解説。

https://atcoder.jp/contests/abc225

## 目次
[A - Distinct Strings](#a---distinct-strings)
[B - Star or Not](#b---star-or-not)
[C - Calendar Validator](#c---calendar-validator)
[D - Play Train ](#d---play-train)


## A - Distinct Strings

https://atcoder.jp/contests/abc225/submissions/me

### 解説

長さが3の文字が与えられ、これを並び替えた種類は何通りあるかという問題。

もし`aaa`ならば、並び替えてもすべて同じ文字になるので、1種類。つまり、文字の種類が1種類のときは、1種類となる。

もし`aab`ならば、`b`の位置は、`aab`と`aba`と`baa`となる。したがって、文字の種類が2種類のときは、並び替えた文字列は3種類になる。

もし`abc`ならば、すべてのアルファベットが違うので、全通りを考えなければならない。したがって、`abc`,`acb`,`bac`,`bca`,`cab`,`cba`の6種類となる。

以上のことを実装する。

まず、同じアルファベットはどうやって判定するか。文字列を一度`list()`にいれて、それぞれの文字列を分割する。`'aba' -> ['a', 'b', 'a']`のようになる。

これを`set()`にいれると、重複したアルファベットはまとめられる。この`set()`の長さで以上のことを`if`文で判別し、答えを出力する。


### コード
```python
def main():
    s = list(input())
    
    if len(set(s)) == 1: # ex) aaa なら並び方は1種類
        print(1)
    elif len(set(s)) == 2: # ex) aab なら並び方は3種類
        print(3)
    else: # ex) abc なら並び方は6種類
        print(6)
        
if __name__ == '__main__':
    main()
```

## B - Star or Not

https://atcoder.jp/contests/abc225/tasks/abc225_b

### 解説

1つの頂点から、他のすべての頂点に1本ずつ辺がでている木、になっているかを判別する問題。

入力は`a, b`で、頂点`a`から頂点`b`へ辺が伸びているということを示す。

どうやって判別するかだが、1つの頂点からすべての頂点に辺が出ているということは、頂点`a`と頂点`b`の数を数え、ある頂点の数が、`n-1`個の辺と等しくなっているかどうかを判別してあげると良い。

したがって、これを実装したものが以下のコードである。

### コード
```python
def main():
    n = int(input())
    check = [0] * n
    
    for _ in range(n-1):
        a, b = map(int, input().split())
        check[a-1] += 1
        check[b-1] += 1
    
    if (n-1) in check: # 辺の数がn-1本のものがあればOK
        print('Yes')
    else:
        print('No')
        
if __name__ == '__main__':
    main()
```

## C - Calendar Validator 

https://atcoder.jp/contests/abc225/tasks/abc225_c

### 解説

与えられた`B`が`A`の一部であるか判定する問題。
`A`は次のような形になっている。

```python
 1  2  3  4  5  6  7
 8  9 10 11 12 13 14
15 16 17 18 19 20 21
...
```

`B`がこの形になっているのをどうやって判断すれば良いか。
`A`の規則性を見てみると、行は1ずつ増え、列は7ずつ増えていることがわかる。これを用いて判定する。

行と列を判定するため、それぞれに配列を作る。

行に関して、判定したい値をαとしたときに、その行数は${α-1}/7$の小数点以下切り上げの値になる。また、列に関しては、列数は${β-1}$を7で割ったあまりに1を足した値となる。

この2つに関して、以下のコードのように、規則性が崩れた場合は、`No`を出力してあげると良い。

### コード
```python
def main():
    n, m = map(int, input().split())
    B = []
    for i in range(n):
        B_row = list(map(int, input().split()))
        B.append(B_row)
    
    x = [[] for _ in range(n)]
    y = [[] for _ in range(n)]
    
    for i in range(n):
        for j in range(m):
            x[i].append((B[i][j]+6)//7) # 6足して値を切り上げ
            y[i].append((B[i][j]-1)%7+1) # 連番になっているか
            
    ans = 'Yes'
    
    for i in range(n):
        for j in range(m):
            # どれか一つでも引っかかったらアウト
            if 0 < i and x[i][j] != x[i-1][j]+1: # xの列で1の差を見る
                ans = 'No'
                break
            elif 0 < j and y[i][j] != y[i][j-1]+1: # yの行で1の差を見る
                ans = 'No'
                break
            elif 0 < j and x[i][j] != x[i][j-1]: # xの行が等しいか見る
                ans = 'No'
                break
            elif 0 < i and y[i][j] != y[i-1][j]: # yの列が等しいか見る
                ans = 'No'
                break
                
    print(ans)
    
if __name__ == '__main__':
    main()
```

## D - Play Train

https://atcoder.jp/contests/abc225/tasks/abc225_d

### 解説

番号のついた電車が`N`個あり、入力された各クエリに対して操作をする問題。

・`1 x y`：電車xの後部と電車yの前部を連結
・`2 x y`：電車xの後部と電車yの前部を分離
・`3 x`：電車xが含まれる電車のすべての番号を先頭から出力する

電車の前部と後部については、それぞれリストを用いて管理し、連結していない部分に関しては$-1$を代入しておく。

まず、query1の場合、`back`と`front`のそれぞれのインデックス番号の場所に、入力された電車の番号を代入する。

次に、query2の場合、先程車両番号をいれたが、今回は分離したいので、`back`と`front`どちらにも$-1$を代入する。

最後に、query3の場合、その入力された車両番号をもつ連結された電車を先頭から出力する。車両番号をある変数に入れ、`front`のなかからその電車番号のインデックスに当たる数字を探し、これをさらに変数に代入する。これを、変数が`-1`、つまり、非連結部分まで繰り返すことで、先頭車両を探し出すことができる。

先頭車両がわかったので、先程行ったことを最後尾の車両（-1：非連結部分）まで行う。こうすることで、入力された車両番号をもつ連結された電車の先頭から値を出力できる。

### コード
```python
def main():
    n, q = map(int, input().split())
    front = [-1] * (n+1) # 非連結部分は-1
    back = [-1] * (n+1)
    
    for _ in range(q):
        query, *xy = map(int, input().split())
        
        if query == 1:
            x, y = xy
            back[x] = y # back_iは後列車を表す
            front[y] = x # front_iは前列車を表す
        elif query == 2:
            x, y = xy
            back[x] = -1 # 非連結部分は-1なので、それぞれに値を代入
            front[y] = -1
        elif query == 3:
            x = xy[0]
            while front[x] != -1: # 前列車がなくなる（先頭車両）まで探す
                x = front[x] # 前列車の番号をxに代入
            ret = [x] # 先頭車両の番号
            while back[x] != -1: # 後列車がなくなるまで探す
                x = back[x]
                ret.append(x)
            print(len(ret), *ret)
            
if __name__ == '__main__':
    main()
```

## 編集後記

queryの問題をたくさん解いて練習したい...。まとめようかな。