ABC393 振り返り

はじめに

皆さんはオーパーツというものを知っていますか？

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

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

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

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

A問題-Poisonous Oyster

解法

高橋くんと青木くんの体調から当たる牡蠣を探す問題

$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

解法

文字列$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

解法

$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

解法

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で無事入茶することができました！
やったね