AtCoder Beginner Contest 088 - C

beta.atcoder.jp

初め、aの存在範囲を勝手に-50 ~ 50としていて総当たりしたが間違いだと気が付く。 あくまでもa + bが0 <= a + b <= 100なのであってこれからa, bの存在範囲は決められない。

では違うアプローチ。 表のすべての値を足すとsum(a1, a2, a3, b1, b2, b3) * 3、というのはすぐわかる。3の倍数が出てきてうれしくなるが、これだけでは必要条件とはならなそう。 sum(a1, a2, a3, b1, b2, b3)がどこかにあるかと探すと、c11, c22, c33があった。 これらが3倍になっていることを確認すると、9つの数値が使われているのでよさそう、で実際よかった。

証明まで持ち込めはしないが直観的にはこれでいいか。

def solve(c1, c2, c3):
    if (c1[0] + c2[1] + c3[2]) * 3 == sum(c1) + sum(c2) + sum(c3):
        return "Yes"
    return "No"


if __name__ == "__main__":
    c1 = list(map(int, input().split(" ")))
    c2 = list(map(int, input().split(" ")))
    c3 = list(map(int, input().split(" ")))
    print(solve(c1, c2, c3))

AtCoder Beginner Contest 085 - C

beta.atcoder.jp

N枚のお札がすべてが5000円だったとして目標金額と合計金額の比較をすると、 合計金額を減らすためには5000円を1000円に変換するしかなく、 合計金額を増やすためには5000円を10000円に変換するしかない。 これを利用すればよい。 もし行ったり来たりしてもたどり着けないならばそれは不可能な数値。

実装上の注意としては、N枚目の変換が終わった後にもう一度判定を入れなくてはならないので、 ループをN+1回回すか、ループ終了後に再度判定を入れる必要がある。サンプルテストケースに助けられたので反省。 また、sumは毎回計算しても全然間に合ったが、本当は5000 * Nの初期値に対して変換のたびに-4000か+5000すれば追加の計算は不要。

もしお札が4枚だったら場合分け必要そうだから探索かな。。

def solve(N, Y):
    r = [5000 for _ in range(N)]
    for i in range(N + 1):
        s = sum(r)
        if s == Y:
            return (
            len([d for d in r if d == 10000]), len([d for d in r if d == 5000]), len([d for d in r if d == 1000]))
        elif s < Y and i < N:
            r[i] = 10000
        elif s > Y and i < N:
            r[i] = 1000
    return (-1, -1, -1)


if __name__ == "__main__":
    N, Y = tuple(map(int, input().split(" ")))
    print(" ".join(map(str, list(solve(N, Y)))))

AtCoder Beginner Contest 110 - C

beta.atcoder.jp

直観とテストケースに頼って実装してしまった。学びにならないのでよくない。

def solve(S, T):
    sm = {}
    tm = {}
    for s, t in zip(S, T):
        if s in sm and sm[s] != t:
            return "No"
        sm[s] = t

        if t in tm and tm[t] != s:
            return "No"
        tm[t] = s

    return "Yes"


if __name__ == "__main__":
    S = input()
    T = input()
    print(solve(S, T))

改めて考えてみる。 Sの中に含まれるある文字で構成されるグループは、置き換えによって文字そのものは変わるものの、 そのグループの位置は変わらない。 そして、このグループは統合することも分割することもできない。

SからTに変換するための必要条件として、グループの構成が常に同じになる＝S中のある文字に対して、T側が常に同じ文字で対応する、というのがあげられる。 S->Tの対応だけを考えてしまうと以下のようなケースが通ってしまうため、T->S側の対応も確認し、常に同じグループであることを確認する。

S = bbbbcccc T = aaaaaaaa

って感じでよいのかな。

AtCoder Beginner Contest 113 - C

beta.atcoder.jp

ソートとカウントして出力を作ってから元の順番で。tupleは便利。

def solve(N, M, PYs):
    Ys = {i + 1: 1 for i in range(N)}
    ret = {}
    for p, y in sorted(PYs, key=lambda x: x[1]):
        ret[(p, y)] = "{:06d}{:06d}".format(p, Ys[p])
        Ys[p] += 1
    return [ret[(p, y)] for (p, y) in PYs]

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    PYs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print("\n".join(solve(N, M, PYs)))

しかし、日曜日にいきなりやられても。。参加したかった。

AtCoder Beginner Contest 075 - C

beta.atcoder.jp

計算量的に一本ずつ外して探索して結果を確認すればよい。 あんまり実装しない隣接行列と再帰でやったが若干はまった。 あんまりなれない実装はするもんじゃないな。

def solve(N, M, ABs):
    ans = 0
    for i in range(M):
        adjMat = [[0 for _ in range(N)] for _ in range(N)]
        for k, (a, b) in enumerate(ABs):
            if k != i:
                adjMat[a - 1][b - 1] = 1
                adjMat[b - 1][a - 1] = 1

        def dps(a, visited):
            n = [i for i, b in enumerate(adjMat[a]) if b == 1]
            for nn in n:
                if nn not in visited:
                    visited.append(nn)
                    dps(nn, visited)
            return visited

        visited = dps(0, [])
        if len(visited) != N:
            ans += 1
    return ans


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABs))

AtCoder Beginner Contest 079 - C

beta.atcoder.jp

binaryで総当たり。やっと何も見ずにformatの中身をかけた。 evalはまぁ便利なので若干邪道と思いつつ使う。pythonばっかりつかってるとC++でちゃんと書けるか不安になる。

def solve(ABCD):
    for i in range(0, 8):
        ops = "{:03b}".format(i)
        op1 = "+" if ops[0] == "0" else "-"
        op2 = "+" if ops[1] == "0" else "-"
        op3 = "+" if ops[2] == "0" else "-"
        s = ABCD[0] + op1 + ABCD[1] + op2 + ABCD[2] + op3 + ABCD[3]
        if eval(s) == 7:
            return s + "=7"
    return "error"


if __name__ == "__main__":
    ABCD = input()
    print(solve(ABCD))

AtCoder Beginner Contest 046 - D / 047 - C

beta.atcoder.jp

気づけるか。そこが勝負。 解説の通りなんだけれども、得点を最大化する戦略はパーを出すだけ出す。 そして並び順はどうでもよい。 というのも、相手がグーを出しているとき、グーからパーにすると＋１ポイント。 相手がパーを出しているとき、グーからパーにしても＋１ポイントでどこをパーにしても常に同じ。

ここから得点計算すればよい。

教訓としては差分を考える、ということと、 極端なケースから始めよう、というところかな。

def solve(s):
    return len(s) // 2 - s.count("p")


if __name__ == "__main__":
    print(solve(input()))

beta.atcoder.jp

これも気づけるか。そこが勝負。 以前どこかで二次元の問題をやったときにでてきたもので、 色の境目の数がひっくり返す必要のあるもの。単にそれを数えればよい。

def solve(s):
    return s.count("BW") + s.count("WB")


if __name__ == "__main__":
    print(solve(input()))