【AtCoder】ABC291 のA,B,C,D,E における Python解説

ABC 291 のA,B,C,D,E 問題を解くために考えたこと、ACできるPython3(PyPy3)コードを紹介します。

この記事は @u2dayo さんの記事を参考にしています。見たことのない方はそちらもご覧ください。とても勉強になります。

また、問題の難易度を表す指標を [Atcoder Problems](https://kenkoooo.com/atcoder/#/table/tsuru1471) から引用しています。このサイトは勉強した問題を管理するのにとてもオススメです。

質問やご指摘はこちらまで
Twitter : [Waaa1471](https://twitter.com/Waaaa1471)

作者プロフィール
Atcoder ：[緑 944](https://atcoder.jp/users/tsuru1471) 
230227 現在

# 目次
[はじめに](#はじめに)
[A.camel Case](#acamel-case)
[B.Trimmed Mean](#btrimmed-mean)
[C.LRUD Instructions 2](#clrud-instructions-2)
[D.Flip Cards](#dflip-cards)
[E.Find Permutation](#efind-permutation)


## はじめに

特にC問題以降になると、競技プログラミングに典型的な前提知識、少し難しい数学的考察が必要になり始めます。
しかし、公式解説ではこの部分の解説があっさりしすぎていて競技プログラミング(Atcoder)を始めたばかりの人にはわかりにくい、難しいと感じるのではないでしょうか。

またC++がわからないと、コードの書き方を勉強することが難しいです。一応、参加者全員のコードを見ること自体は可能ですが、提出コードは必ずしも教育的ではありません(ここで紹介する記事も本番で提出したものとは全く異なります)。そんなものから初学者が解説もなしになにか得ることはとても難しいと思います。実際適当に何人かのコードをみたものの、意味がわからずに終わった経験があるのではないでしょうか。

この記事がそんな方々の勉強の助けになればよいなと思っています。



# A.camel Case
[問題ページ](https://atcoder.jp/contests/abc291/tasks/abc291_a)

難易度： 灰色 8 

## 考察
入力文字列 _S_ に含まれる唯一の大文字の位置を求めるためには、_S_ の先頭から順に大文字が検出できるまで調べていけばよいでしょう。python では **isupper()** 関数で文字列の大文字判定が可能です。

ただし、_S_ に含まれる文字の位置は _1_ 始まりであるのに対して、index番号から求めた位置は _0_ 始まりです。したがって、出力時にこのズレを調整する必要があります。

## コード   
pypy3
96 ms/2000 ms
```php
S=input()
for i,s in enumerate(S):
    if s.isupper():
        print(i+1)
```


## 補足 
- enumerate() 関数
[Python, enumerateの使い方: リストの要素とインデックスを取得](https://note.nkmk.me/python-enumerate-start/)
文字列、イテラブル(リストなど)から要素とその位置を同時に取得したいときに利用します。

- 文字列の大文字、小文字判定
[Pythonで大文字・小文字を操作する文字列メソッド一覧](https://note.nkmk.me/python-capitalize-lower-upper-title/)

# B.Trimmed Mean

[問題ページ](https://atcoder.jp/contests/abc291/tasks/abc291_b)

難易度：灰色 32

## 考察

昇順に点数を並べたときの前から _N+1_ 番目 ～ _4N_ 番目までの計 _3N_ 個の平均点を求めればよいです。

そのために、まず該当する点数のみを抽出します。入力の数列 _X_ をソートして、[ _N : 4N_ ] の範囲でスライスすればこれを実行できます。
後は全要素を足し合わせて _3N_ で割れば目的の平均点が得られます。

index 番号が _0_ 始まりであること、[ _a : b_ ] の範囲でスライスすると _a  ～ b-1_  の位置が抽出されることに気を付けます。


## コード
pypy3
69 ms/2000 ms
```php
N=int(input())
# 昇順にソートして、N+1  ～ 4N 番目までを抽出
X=sorted([int(x) for x in input().split()])[N:4*N]
ans=0
for x in X:
    ans+=x
print(ans/(3*N))
```

## 補足
- ソート
[Pythonでリストをソートするsortとsortedの違い](https://note.nkmk.me/python-list-sort-sorted/)
- スライス
[Pythonのスライスによるリストや文字列の部分選択・代入](https://note.nkmk.me/python-slice-usage/)

## C.LRUD Instructions 2

[問題ページ](https://atcoder.jp/contests/abc291/tasks/abc291_c)

難易度 ： 灰色 188

## 考察

**過去到達したことのある全ての座標** を管理しておけば、「 現在地に一度でも訪れたことがあるか 」を「 **現在地がこれに含まれるか** 」で判定できるようになります。
ただし、全体で _N_ 回判定を行うことになるので **1度の判定を高速に行う必要があります**。 そこで、過去到達したことのある全ての座標を **集合** で管理します。集合であれば要素検索を $O(1)$ で行えるためです。

注意点としては、座標 _x_ , _y_ は **hashable (ハッシュ可能) なオブジェクトであるタプル型の ( _x,y_ ) の形で集合に格納します**。リスト型の [ _x,y_ ] の形で格納することはできません。

## コード
pypy3
123 ms/ 2000ms
```php
N=int(input())
S=input()
# 現在位置
x,y=0,0
# 既出位置を管理
X=set()
X.add((0,0))

for s in S:
    if s=="R":
        x+=1
    
    if s=="L":
        x-=1
    
    if s=="U":
        y+=1
    
    if s=="D":
        y-=1
    
    if (x,y) in X:
        print("Yes")
        exit()
    
    X.add((x,y))

print("No")
```

## 補足
- 計算量
[Pythonistaなら知っておきたい計算量のはなし](https://qiita.com/Hironsan/items/68161ee16b1c9d7b25fb)
リスト内要素検索では $O(k)$ かかってしまう点など覚えておきましょう

- hashable
[公式ドキュメント hashable 項目](https://docs.python.org/ja/3/glossary.html#term-hashable)
辞書や集合の要素は hashable でなければなりません。

 

# D.Flip Cards

[問題ページ](https://atcoder.jp/contests/abc291/tasks/abc291_d)

難易度：<font color="Maroon"> 茶色 720 </font>

## 考察

カードの並べ方を前から順に決定する場合 _i_ 番目のカードの置き方は _i-1_ 番目のカードの値にのみ依存します。したがって

$dp[\ i\ ][\ x\ ]$ : $i$ 番目のカードの値が $x$ となる置き方の総数 

で状態を定義することで、以下のように遷移に忠実に全状態を決定することができます(**動的計画法**)。

$dp[\ i\ ][\ x\ ]$ += $dp[\ i-1\ ][\ x\ 以外\ ]$

## 計算量

遷移数は定数回なので計算量は全体で $O(N × max(max(A),max(B)))$ となります。
$ A,B ≦ 10^9 $ より、このままでは間に合わないことがわかります。 

ボトルネックは管理すべき状態が多すぎることです。どうにかしてカードの値よりも種類が少ない「 何か 」で状態を定義することができないでしょうか。

そこで、**カードの値を「 番号 」と「 置き方 」 に紐づけて記憶し、置き方からカードの値を取得可能とすることで、カードの値の代わりに「 置き方 」で状態を定義できるようにします**。

つまり _i_ 番目の置き方が _j_ ( 表 or 裏 ) となるカードの値を管理するテーブル : $AB[\ i\ ][\ j\ ]$ を作成し、_i_ 番目のカードの置き方が _j_ ( 表 or 裏 ) となる置き方の総数 : $dp[\ i\ ][\ j\ ]$ で状態を定義し直します。

これにより状態数は _2N_ となるため、計算量は全体で $O(N)$ に改善されました。


## コード
pypy3
381 ms /2000ms
```php
N=int(input())
AB=[]
for _ in range(N):
    a,b=[int(ab) for ab in input().split()]
    AB.append([a,b])

MOD=998244353
dp=[[0,0] for _ in range(N)]
dp[0][0]=1
dp[0][1]=1
for i in range(1,N):
    for j in range(2):
        if dp[i-1][j]:
            for k in range(2):
                if AB[i-1][j]!=AB[i][k]:
                    dp[i][k]+=dp[i-1][j]
                    dp[i][k]%=MOD

print((dp[-1][0]+dp[-1][1])%MOD)          
```

## 補足

- 動的計画法 ( DP )
・[動的計画法ってなに？　(導入)](https://algo-method.com/descriptions/44)
・[典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～](https://qiita.com/drken/items/a5e6fe22863b7992efdb)
こちらで動的計画法の概念を勉強することができます。
分かるようになったら、アルゴ式 1～2章で練習してみましょう
[動的計画法 ( DP )](https://algo-method.com/courses/7)



# E.Find Permutation

[問題ページ](https://atcoder.jp/contests/abc291/tasks/abc291_e)
難易度 ： <font color="green"> 緑色 1069 </font>

## 考察

_A_ は順列であるので $A_1 < A_2 < ... < A_n$ のとき、$A_1 =1 , A_2 = 2 .... , A_n = N$ と決定できます。 
したがって、「 _A_ を一意に特定すること 」と「 **_A_ の要素の大小関係を一意に特定すること** 」は同値であることがわかります。

ここで、_A_ の要素間の大小関係は _X_ , _Y_ によって、$A_{X} < A_{Y}$ と決定されますが、$これを\ A_{X} ← A_{Y}\ 、つまり「\ 頂点\ A_Y から頂点\ A_X$ に有向辺を張ること 」と解釈します。なぜなら、「 **こうして構築した有向グラフの頂点を入次数順に探索した順番** 」と 「 _A_ の要素の大小関係 」 とが一致する かつ、前者は**トポロジカルソート**で求めることができるからです。 
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3012066/51493fb5-5a8c-d903-7330-7982c7d95696.png)
以上より、この問題は「  **_A_ の要素をトポロジカルソートして並び替えた順番が一意に定まるか** 」判定する問題であると解釈することができました。
「 _A_ の順番が一意に定まること」と 「 **常に、同時に複数の頂点を探索できないこと** 」が同値であることに注目すると、探索中、現在何個の頂点を同時に探索可能であるか管理すれば、この問題を判定できるとわかります。

## コード
pypy3
478 ms/2000 ms
```php
from collections import deque
N,M=[int(nm) for nm in input().split()]
que=deque()
# 有向グラフ
G=[[] for _ in range(N)]
# 入次数
table=[0 for _ in range(N)]
for _ in range(M):
    x,y=[int(xy)-1 for xy in input().split()]
    G[y].append(x)
    table[x]+=1

# 探索可能頂点数
tmp=0
for i in range(N):
    if table[i]==0:
        tmp+=1
        que.append(i)

if tmp!=1:
    print("No")
    exit()

order=[0 for _ in range(N)]
rem=N
while True:
    now=que.popleft()
    tmp-=1
    order[now]=rem
    rem-=1
    # 全位置を決定できたら終了
    if rem==0:
        break
    for nex in G[now]:
        table[nex]-=1
        if table[nex]==0:
            que.append(nex)
            tmp+=1
        
    if tmp!=1:
        print("No")
        exit()

print("Yes")
print(*order)
```

## 補足
- トポロジカルソート
[トポロジカルソートのアルゴリズム（閉路のない有向グラフDAGのソート）](https://algo-logic.info/topological-sort/)

    ※ 個人的にアルゴ式の例題は教育的でないのでオススメしません。
この問題やこちらの[類題](https://atcoder.jp/contests/abc223/tasks/abc223_d)で練習すればよいと思います。
念のためネタバレ防止で、abc 220 ～ 225 の c or d と記します。

# 終わり

また見てくれよな !!!