ABC393 振り返り

# はじめに
皆さんはオーパーツというものを知っていますか？
>「オーパーツ」は、主に出土品などが、考古学上その成立や製造法などが不明とされたり、当時の文明の加工技術や知見では製造が困難あるいは不可能に見える場合に使われる。正式な考古学用語ではなく、そういった出土品の存在を強調し、通説に疑義を唱える意図で主に使われる。
Wikipediaより引用

オーパーツについては、信じるも信じないも自分次第な都市伝説が色々ありますが、
僕が思うにオーパーツができる理由は誰も製造方法を残さなかった (残らなかった) からだと思うんですよ

かくいう僕も、AtCoderで前に提出したコードを見てると何でこう書いたんだっけ？と思うことが多いんですよ。コンテスト中はコメントとか書かないし
こうやってオーパーツは出来上がるのかと痛感するわけですよ

なので、オーパーツを作らないためにも？記事に解法を残すことにしました！
わかりやすく書くつもりですが、わかりづらかったらごめんなさい。オーパーツ奢ります


# [A問題-Poisonous Oyster](https://atcoder.jp/contests/abc393/tasks/abc393_a)
### 解法
高橋くんと青木くんの体調から当たる牡蠣を探す問題



$S_1, S_2$が`sick`なら二人とも食べた牡蠣$1$が悪さをしていて、$S_1, S_2$が`fine`なら…と素直に全通り書きました。場合分けミスりそうで怖かった

ちなみに牡蠣は`sick`になるのが怖いので食べたことありません

### コード
```abc393_a.py
S1, S2 = map(str, input().split())

if S1 == "sick" and S2 == "sick":
    print(1)
elif S1 == "fine" and S2 == "fine":
    print(4)
elif S1 == "sick" and S2 == "fine":
    print(2)
else:
    print(3)
```

# [B問題-A..B..C](https://atcoder.jp/contests/abc393/tasks/abc393_b)
### 解法
文字列$S$から`A`,`B`,`C`が等間隔で並んでいる箇所を求める問題

まずは間隔を決めて、そのまま横にずらすことで数えました
for文の$i$が間隔で、$j$の値を先頭にしてwhile文で順番に数えています

$j$から2個先の位置に迷ったような気がする

### コード
```abc393_b.py
S = list(input())
N = len(S)
cnt = 0

for i in range(N):
    j = 0
    while j + 2 * (i + 1) < N:
        if S[j] == "A" and S[j + (i + 1)] == "B" and S[j + 2 * (i + 1)] == "C":
            cnt += 1
        j += 1

print(cnt)
```

# [C問題-Make it Simple](https://atcoder.jp/contests/abc393/tasks/abc393_c)
### 解法
$N$頂点、$M$辺の無向グラフから、辺を取り除いてグラフを単純にするには何本取り除けば良いか数える問題
単純というのは自分自身に返ってくる辺や重複する辺がないこと

まずは、辺を一つずつ見ていきます
重複する辺はそれぞれの頂点の繋がりを管理しておいて、もうすでに繋がっているなら取り除くのでカウントします
自分自身に返ってくる辺は、事前に頂点の繋がりに自分自身を追加しておいてから辺を見ているので、上の処理と同じようにカウントされます

事前の追加をせず、`if u == v: cnt += 1`みたいに書いておくほうが良さそう？

### コード
```abc393_c.py
N, M = map(int, input().split())
G = [set() for _ in range(N)]
cnt = 0
for i in range(N):
    G[i].add(i)
for _ in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    if v in G[u] or u in G[v]:
        cnt += 1
    G[u].add(v)
    G[v].add(u)
print(cnt)
```
# [D問題-Swap to Gather](https://atcoder.jp/contests/abc393/tasks/abc393_d)
### 解法
`0`,`1`からなる文字列$S$から隣り合う文字を選んで入れ替えることで`1`の塊を作る
塊を作るための操作の最小値を求める問題
>例えば、`0100101`だと
`0100101 0回目`
`0010101 1回目`
`0001101 2回目`
`0001110 3回目`
のように3回で塊を作れる

まずは$S$内の`1`の位置を調べます (コードでは`pos`に入っている)
そして、`pos`の中央から左右に広げるように調べていき、2つの位置の差から必要な操作回数を求めます

>`0100101`の例だと`pos`は`[1,4,6]`になります
つまり、4番目の`1`の両隣 (1つ隣) に1,6番目の`1`を持ってきたいということです
もう少し多く`1`がある場合は2つ隣、3つ隣…と持っていくわけです
移動に必要な操作回数は`pos`の2つの位置の差からわかるのですが、上にも書いた通り移動させるのは1つ隣まででいいので、その分を後で引きます
例えば、`pos[1] - pos[0] = 3` だけど1つ隣まででいいので、`3 - 1 = 2`になります
同様にして、`pos[2] - pos[1] - 1 = 1`なので`2 + 1 = 3`が答えです

真ん中の1に寄せるのが最小値じゃね？と何となくで書いたら合ってました。正直、勘です

### コード
```abc393_d.py
N = int(input())
S = list(input())
pos = []
for i in range(N):
    if S[i] == "1":
        pos.append(i)
mid = len(pos) // 2
wid = 1
cnt = 0
while mid - wid >= 0 or mid + wid < len(pos):
    if mid - wid >= 0:
        cnt += abs(pos[mid] - pos[mid - wid]) - wid
    if mid + wid < len(pos):
        cnt += abs(pos[mid] - pos[mid + wid]) - wid
    wid += 1
print(cnt)
```
# 最後に
危ない場面もありましたが何とかD問題まで解くことができました
時間内にD問題まで解けたのは初めてです！本当に良かった！

ちなみに、AtCoder Beginner Contest 393で無事入茶することができました！
やったね


https://music.apple.com/jp/album/%E3%81%8A%E3%81%AF%E3%82%88%E3%81%86%E3%82%AA%E3%83%BC%E3%83%91%E3%83%BC%E3%83%84/480158616?i=480158623