AtCoder Beginner Contest 180 - 平凡な社会人の日記

目的

ABC180を題材として競技プログラミングにおける考え方、解き方について共有することで競技プログラミングを知らない人に雰囲気を掴んでもらう。同じレベルの人や強い人にアドバイスをもらう。できれば競技プログラミング仲間が欲しい。

さっちゃんです。ABC180について感想、考えていた事について書きます。まだ解いていない人や、問題の雰囲気を見たい人は次のページに飛んでください。(問題は書いてないので、この記事だけ見ても面白くないかもしれません。)
atcoder.jp

目的
1. 感想
2. A(box)
3. B(Various distances)
4. C(Cream puff)
5. D(Takahashi Unevolved)
6. E(Traveling Salesman among Aerial Cities)
7. これから
References

1. 感想

今回の ABC180 の difficulty は
A:灰、B:灰、C:灰、D:緑、E:水色、F:黄色
でCまでは比較的優し目だったように思います。私はA,B,C,D,EをACして5完(パフォーマンス:1286)でした。Dは実力ですが、Eは本当にたまたまで、理解できてないのでこれから勉強します。灰色の私としては、Cまで速く解いてD解ければいいなーくらいで参加したのでよかったです。
初参加から約1年半、ついに灰色を脱出して茶色になりました！（久しぶりに遅刻せずに参加できたことが大きかったように思います。）
というか最近まで物理やってたり就職活動があったので本腰入れてなかっただけなんですけどね。私ほどのポテンシャルがあってイケメンなら茶色飛び越えて緑までバビョーっと行っちゃいます！(ハードルは上げて上げて下をくぐる派！)

atcoder.jp

f:id:physics-heibon:20201018052542p:plain — 脱灰色！祝う○こ色！

2. A(box)

言われた通りやりまーす。（負になる事あるかな？と頭をよぎりましたが、ABCのAなので無いでしょー！と思って何も考えず提出しました。制約的にありません。）

N ,A, B = map(int,input().split())

print(N+B-A)

3. B(Various distances)

言われたものを計算しまーす。 $10^{-9}$ 精度まで必要ってことで一応 sqrt のところは decimal 使いましたが、python は何も気にしないでも大丈夫だったようです。C++とかだと double じゃなくて long long 使わないといけないらしいです。Python もfor文遅かったりするので一長一短ですね。ちなみに M:Manhattan、E:Euclid、C:Chebyshev の略でーす。
どうでもいいですが、マンハッタン距離を見ると45°回転した座標系を定義したくなる病気になりました。(マンハッタン距離の最小最大はそうすると考えやすいっておばあちゃんが言ってた。)

import math
from decimal import Decimal
N = int(input())
x = list(map(int, input().split()))

M = 0
E = 0
C = 0
for i in range(N):
    M += abs(x[i])
    E += (x[i])**2
    C = max(C,abs(x[i]))
E = Decimal(E).sqrt()
print(M, E, C)

4. C(Cream puff)

与えられた $N$ を割り切る正の整数を列挙してくださいってことなので、正の約数を列挙できればいいなーって感じです。 $1$ から調べ始めて $\sqrt{N}$ まで調べれば $O(10^6)$ で解けますね。以下の記事から引っ張ってそのまま貼り付けました。ありがとうございます。
qiita.com

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

N = int(input())

ans = make_divisors(N)
for i in range(len(ans)):
    print(ans[I])

5. D(Takahashi Unevolved)

最初は全然分からなかったんですが、実験しているうちに分かってきました。操作は掛けるか足すかですけど、掛けるのって最初の方にやっておかないと、後の方になって掛け算すると数字がバカデカくなって損しちゃうんですよね。だから後の方は足し算がお得(数字を比較的大きくしないで経験値を増やせる)で、最初の方は掛け算の方がお得です。後はいつ掛け算を止めるかですけど、掛け算をした結果が足し算をするより大きくなったら、足し算をした方が数を小さくできるのでやめ時です。もしくは、掛け算をした結果上限に達したら(掛け算だけで上限に達する、(1,10,2,100) の場合などです。)やめ時です。後者に気づかずに3,4回WA提出してしまいました。

掛け算していけばその数は指数関数的に増えていくので、掛け算の計算の部分はすぐに終わります。あとは足し算をするのみなので、何回足し算できるかを考えて足せばいいです。足し算をしていった結果 Y と同じになってはいけないので、その場合は「Bで、Aによる掛け算パートが終わった"残り"(left)を何回割れるか」の結果から-1しておけばいいです。(これらの事は、(X,Y,A,B) = (1,30,2,8)とか(1,32,2,8)とかで手を動かして実験してみた結果分かりました。)

import sys

X, Y, A, B = map(int,input().split())

ans = 0
#if abs(X-Y) == 0:
#    print(0)
#    sys.exit()

while X*A <= min(B,Y):
    ans += 1
    X = X * A
left = Y - X
if left%B != 0:
    ans += left//B
else:
    ans += left//B
    ans -= 1

print(ans)

6. E(Traveling Salesman among Aerial Cities)

パッと見て巡回セールスマン問題かなーと思って（同じノードに訪れることが許されているので厳密には違うんですが、今回定義されている"距離"に三角不等式が成り立ち、同じノードには訪れる必要がないので結局巡回セールスマン問題。）タイトル見たらまさにそう書いてましたが、勉強した事ないから出来ません。しかし残り40分くらいあったので暇だから勉強するかーと思って色々検索していたら、巡回セールスマン問題はbitDPという種類の問題らしいというのを見かけました。bit探索と区間DPは知ってるけど、そんな融合モンスター知らんよ〜って感じ。(最近遊戯王GX見てるんですが、シャイニング・フレア・ウイングマンかっこいい。サイバーエンドドラゴンと同じくらいかっこいい。)
それでも色々調べていると、次のサイト辿り着きました。
inarizuuuushi.hatenablog.com

理屈はよく分からんけど、距離行列(コスト行列？正式な名前は知りませんが、ノード $i$ からノード $j$ へ行くためのコスト、今回の場合は非対称行列)をぶち込めば巡回セールスマン問題を解いてくれる素晴らしいコードが落ちていたので拝借。ありがとうございます。
距離行列作ってテストを入れるとPythonで2秒以内に答えを出してくれるか怪しかったので念のためPyPy3で提出するとAC。完全にまぐれです。

# ---- memo -----------------
# 巡回セールスマン問題
# ---------------------------

def tsp(d):
    n = len(d)
    # DP[A] = {v: value}
    DP = dict()
    
    for A in range(1, 1 << n):
        if A & 1 << 0 == 0:# 集合Aが0を含まない
            continue
        if A not in DP:
            DP[A] = dict()

        # main
        for v in range(n):
            if A & 1 << v == 0:
                if A == 1 << 0:
                    DP[A][v] = d[0][v] if d[0][v] > 0 else float('inf')
                else:
                    DP[A][v] = min([DP[A ^ 1 << u][u] + d[u][v] for u in range(n) 
                                    if u != 0 and A & 1 << u != 0 and d[u][v] > 0]
                                  + [float('inf')])
    # 最後だけ例外処理
    V = 1 << n
    DP[V] = dict()
    DP[V][0] = min([DP[A ^ 1 << u][u] + d[u][0] for u in range(n) 
                    if u != 0 and A & 1 << u != 0 and d[u][0] > 0]
                    + [float('inf')]) 


    return DP[V][0]




if __name__ == '__main__':


    def cost(A,B):
        return abs(A[0]-B[0]) + abs(A[1]-B[1]) + max(0,B[2]-A[2])

    N = int(input())
    X = [0] * N
    Y = [0] * N
    Z = [0] * N
    List = []
    for i in range(N):
        X[i], Y[i], Z[i] = map(int,input().split())
        List.append([X[i], Y[i], Z[i]])

    D = [[0] * N for i in range(N)]
    for i in range(N):
        for j in range(N):
            D[i][j] = cost(List[i],List[j])

    res = tsp(D)
    #print(D)
    print(res)