読者です 読者をやめる 読者になる 読者になる

AtCoder Beginner Contest 054

Atcoder ABC

参加しました、ギリギリでしたが全完しました
ABCで全完するのは2回目ですね
AtCoder Beginner Contest 054 - AtCoder Beginner Contest 054 | AtCoder

A.o
B.o
C.o
D.xxxxxxo

残り1分切ってて危なかったです
(全完の定義ってミスあっても全問解けたら全完と言っていいんでしょうか?)

A - One Card Poker

A: One Card Poker - AtCoder Beginner Contest 054 | AtCoder

問題概要

1枚のカードでポーカーをする、カードの強さは以下の通り
2 < 3 < ... < 10 < 11 < 12 < 13 < 1
AliceのカードがA, BobのカードがBで与えられるのでどちらが勝つか判定せよ
ただし両者が同じ強さのカードを持っていたら引き分けである

制約

  • 1 <= A, B <= 13

感想

愚直に場合分けをして書きました、プログラミング言語の練習問題のような感じです
解説見たら1は13よりでかい整数に変換して判定するのがいいみたいです、確かに
こういうのはタイプミスで出力を間違えるのが怖いですね

実際に書いたコード

def solve():
    A, B = map(int, input().split())
 
    if A == B:
        ans = 'Draw'
    else:
        if A == 1:
            ans = 'Alice'
        elif B == 1:
            ans = 'Bob'
        elif A > B:
            ans = 'Alice'
        else:
            ans = 'Bob'
 
    print(ans)
 
if __name__ == '__main__':
    solve()

なぜ解けたか?

  • 問題文に書いてあることをそのまま実装すればよい問題だった

B - Template Matching

B: Template Matching - AtCoder Beginner Contest 054 | AtCoder

問題概要

N * N の2値画像とM * Mのパターンが与えられる
画像の中にそのパターンが含まれているかどうか判定せよ

制約

  • 1 <= M <= N <= 50

感想

制約が小さいので画像の左上から愚直に全探索すればいけるなあと思いました
けど書いててめんどくさいなあ、って思ってしまったので一旦飛ばして次に行きました
別にめんどくさいってほどめんどくさくはなかったんですが、何かあまりすんなり書けませんでしたね……
実装力不足なんでしょうか

ともあれ実際に書いたコードです
計算量はO((N - M)^2 * M^2) = O(N^2 * M^2)ですね

def solve():
    N, M = map(int, input().split())
    A = []
    B = []
 
    for i in range(N):
        A.append(input())
    for i in range(M):
        B.append(input())
 
    for i in range(N - M + 1):
        for j in range(N - M + 1):
            for k in range(M):
                s1 = A[i + k][j:j + M]
                s2 = B[k]
                if s1 != s2:
                    break
            else:
                print('Yes')
                return None
 
    print('No')
 
if __name__ == '__main__':
    solve()

ちなみに解説動画ではKMPっていう文字列検索のアルゴリズムを使うとO(N^3)に落せて、さらにFFT高速フーリエ変換)を使うとO(N^2 log(N))まで落とせるらしいです。
FFTは難しそうなのでパスして、KMPってのを調べてみたんですが1次元だと何となく分かるんですが2次元の場合はどうやるんでしょう。
解説のpdfにあるハッシュを用いる方法ってのは、ラビンカープ法って奴みたいですね。普通にハッシュを計算するのでは同じだけど、ローリングハッシュを使うことで計算量を落とせるみたいです。

C - One-stroke Path

C: One-stroke Path - AtCoder Beginner Contest 054 | AtCoder

問題概要

N頂点の無向グラフが与えられる。グラフに二重辺と自己ループは無い。
頂点0からスタートして全ての頂点を1度だけ訪れるパスは何通りあるか?

制約

  • 2 <= N <= 8
  • 0 <= M <= N*(N-1)/2

感想

ぱっと見難しそうな問題なんですけど、制約がN <= 8ととても小さいんですよね。
だから全ての並べ方を試して、その並べ方の間の全てに辺があればカウントする、ってやり方で十分間に合います。
全ての並べ方を全列挙するのは、Pythonならitertoolsのpermutationsを使えば簡単にできます。
コンテスト中は始点が0固定なことを忘れていて、若干手間取りました

実際に書いたコード、計算量はO(N! * N)です

from itertools import permutations

def solve():
    N, M = map(int, input().split())
    Adj = [[0]*N for i in range(N)]
 
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        Adj[a][b] = 1
        Adj[b][a] = 1
 
    cnt = 0
 
    for line in permutations(range(1, N)):
        path = [0] + list(line)
        # debug(path, locals())
 
        for i in range(N - 1):
            if not Adj[path[i]][path[i + 1]]:
                break
        else:
            cnt += 1
 
    print(cnt)
 
 
if __name__ == '__main__':
    solve()

解説動画を見ていると、permutationsを使わないでやる方法も教えてくれたのでそっちも書いてみました
ビット演算を使って、posが既に決まった先頭個数、maskがまだ使用していない数字の集合を現しています。
そして先頭N個が確定したらpermutationが決まったことを意味するのでそのpermutationに対して、全ての間に辺があったらカウントするという処理を書いています。
solveからdfsに渡すときは、先頭が0固定なので、pos = 1, mask = (1 << N) - 1 - 1 として、maskは既に0が使われた状態で渡します。
……としているつもりがmask = (2 << N) - 1 - 1になっちゃってますね。まあこれでも余分なビットがあるだけで支障なく動いたようですが……

cnt = 0
 
def dfs(N, Adj, p, pos, mask):
    global cnt
 
    if pos == N:
        for i in range(N - 1):
            if not Adj[p[i]][p[i + 1]]:
                break
        else:
            cnt += 1
 
        return None
 
    for i in range(N):
        if mask & (1 << i):
            p[pos] = i
            dfs(N, Adj, p, pos + 1, (mask ^ (1 << i)))
 
    return None
 
def solve():
    global cnt
    cnt = 0
 
    N, M = map(int, input().split())
    Adj = [[0]*N for i in range(N)]
 
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        Adj[a][b] = 1
        Adj[b][a] = 1
 
    p = list(range(N))
    dfs(N, Adj, p, 1, (2 << N) - 1 - 1)
 
    print(cnt)
 
if __name__ == '__main__':
    solve()

それでこれはO(N! * N)の総当たりのアルゴリズムですが、これはbitDPという手法を使うことによって計算量をO(2^N * N^2)に落すことができるようです。
上のpermutationsを使わないdfsでも使ってますが、有限集合を2進数に対応させるという手法を使って2次元のDPをします。
O(N! * N)ではせいぜいN = 9が限界ですが、O(2^N * N^2)ならN = 15, 16あたりまで計算可能になります。
こっちは書けました、長くなりそうなので別立ての記事で紹介したいと思います。

D - Mixing Experiment

D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder

問題概要

ある物質Cを作りたい。その物質はタイプAの物質と、タイプBの物質をMa:Mbの比率で混ぜ合わせることで作れる。
N種類の薬品があり、各薬品はタイプAの物質をa_i, タイプBの物質をb_i含んでおり、それのコストはc_iである。
これらの薬品をいくつか買って物質Cを作るときの物質Cを作るための最小コストを求めよ。
ただし、どの組合せで薬品を買っても物質Cを作れないときは-1を出力せよ。

制約

  • 1 <= N <= 40
  • 1 <= a_i, b_i <= 10
  • 1 <= c_i <= 100
  • 1 <= Ma, Mb <= 10
  • gcd(Ma, Mb) = 1

感想

問題を見てうーん、となったが何となくDPっぽい問題だなという察しはついた。制約的にもそんな感じがする。
けど比率が絡んできて単純にDPするっていうのは難しそうだな……と思う。

一旦比率のことは忘れて、商品iまで使えるとき、タイプAをX, タイプBをYにするときの最小コストって感じでdpテーブルを作って、それを最後まで計算して、最後に比率がMa:Mbとなる状態だけを見て最小のものを探せばいいんじゃないかというところにたどり着く。
問題は計算量で、この方法はN*10N*10N、最悪6400000回くらいのループになる。正直Pythonだと2*10^6を超えた時点でかなり怪しいのでこれは無理だけど、Pypyを使えば10^7ぐらいまでは対応できるという感覚なので多分いけると踏んだ。ので、この方針で実装することにした。

けど実装がいろいろとまずかった。
まずこういう最小値求める問題って普通初期値にinfみたいなでかい数字入れとけばいいみたいな感じらしいけど、なぜか作れないことを表すために-1を入れていた。それによって無駄に処理がめんどくさくなった。
けどそれより根本的な問題があった。普通にやるなら、最初にN*10N*10Nのdpテーブルを作って、下からdpしていけばそれでいい。けれど、別にN*10N*10N全て作る必要は無くて一個前の状態だけ保持しとけばいいから2*10N*10Nのdpテーブルでいい(もう少し工夫すれば単に10N*10Nの2次元テーブルでよかったみたいだけど)
もちろん理論的には計算量一緒だから意味なさげではあるけど、実際プログラムすると1次元の場合でも後者のほうが速くなるということが経験上あったので、後者のほうでやろうとした。
だからdp[0]に前の状態を記憶させる→dp[0]の情報を用いてdp[1]を更新→終わったらdp[1]のデータをdp[0]にコピー→……
とやろうとした。ここで最後に2次元リストのコピーをするのだけど、これを単に
dp[0] = dp[1][:]
としていた。1次元リストならこれでコピーになっていていいんだけど、2次元だとこれではダメだった。
最終的には行ごとに分けて、1行ずつリストをコピーすることで解決した。かなりギリギリだった。

と言う感じで6回くらいWAしたり焦ってRE出した結果こうなった。最終的にはAC出せたのでよかったけれど。
後に普通にN*10N*10Nのdpテーブルを作る、リストのコピーが必要ない方法でやったらPypyで普通にTLEすることなく通った。ありゃー。

まあ結果はどうあれ、DPすれば解ける問題をちゃんとDPできて通せたのはよかったと思う。
DPは競プロにおいて典型手法らしいのでしっかりと身に着けて使えるようになっておきたい。

というわけで実際に書いたソースコード、計算量はO(N^3 * MAX^2)(MAXはa_i, b_iの取り得る最大値)
初期値が悪いので無駄が多い

def solve():
    N, Ma, Mb = map(int, input().split())
    a_w = []
    b_w = []
    costs = []
 
    for i in range(N):
        a, b, c = map(int, input().split())
        a_w.append(a)
        b_w.append(b)
        costs.append(c)
 
    dp = [[[-1]*(10*N + 1) for j in range(10*N + 1)]
            for k in range(2)]
 
    dp[0][0][0] = 0
    dp[1][0][0] = 0
 
    for i in range(N):
        for a in range(10*N + 1):
            for b in range(10*N + 1):
                if a - a_w[i] >= 0 and b - b_w[i] >= 0:
                    if dp[0][a - a_w[i]][b - b_w[i]] >= 0:
                        if dp[1][a][b] == -1:
                            dp[1][a][b]= dp[0][a - a_w[i]][b - b_w[i]] + costs[i]
                        else:
                            min_ = min(dp[1][a][b],
                                       dp[0][a - a_w[i]][b - b_w[i]] + costs[i])
                            dp[1][a][b] = min_
        
        for k in range(10*N + 1):
            dp[0][k] = dp[1][k][:]
 
    min_cost = float('inf')
 
    for a in range(10*N + 1):
        for b in range(10*N + 1):
            if a != 0 and b != 0:
                if a * Mb == b * Ma and dp[1][a][b] > 0:
                    min_cost = min(min_cost, dp[1][a][b])
 
    if min_cost == float('inf'):
        ans = -1
    else:
        ans = min_cost
 
    print(ans)
 
 
if __name__ == '__main__':
    solve()

ちなみにpythonだと3重ループとかはitertoolsのproductを使うとネストが深くなることなく、スマートに書けるようです
それは知ってるんですが、Pypy3でproduct使うと単純にfor文を重ねた場合と比較して若干遅くなるという現象があるみたいで、私は使わないことにしてます
理由は分からないんですがAtcoderのコードテストとかで試してみると遅くなるんですよね、なんでだろう
まあ見づらいという以外は特にデメリットが無いのでいいのですが

この問題も工夫の仕様があるみたいで、まずdpの状態数を減らすという方法があるみたいです
確かに最終的には比率がMa:Mbのところだけ求めればいいので、無駄が多そうだなという気はします、けどどうやって減らせばいいのかは思いつきません
次に半分全列挙という方法があるみたいです、これはそのまま半分に分けて全列挙して最後に上手い事処理してやるみたいです、どうやって上手い事やるかはよく分かりません