ABC118 D

問題

動的計画法を使う。

dpn配列に文字列の長さ、dp配列に文字列を格納する。配列の長さはマッチ棒の個数。

dpnを0から順番に調べ、初期値(-1)ではなく、追加したマッチ棒の個数の地点の長さが

①追加したい個所と同じ

・追加したい個所に、追加したい個所と新たな文字列のうち、大きいほうを格納

②追加したい個所より長い

・dpnを更新

・追加したい個所に、新たな文字列を格納

最終的にdp[n]が答え。

mi = {"1": 2, "2": 5, "3": 5, "4": 4, "5": 5, "6": 6, "7": 3, "8": 7, "9": 6}
n, m = map(int, input().split())
A = input().split()
dpn = [0] + [-1] * 10010
dp = [""] * 10010
for i in range(n):
    for a in A:
        if dpn[i] != -1:
            cnt = dpn[i] + 1
            if dpn[i + mi[a]] < cnt:
                dpn[i + mi[a]] = cnt
                dp[i + mi[a]] = max(a + dp[i], dp[i] + a)
            elif dpn[i + mi[a]] == cnt:
                dp[i + mi[a]] = max(dp[i + mi[a]], a + dp[i], dp[i] + a)
print(dp[n])

ABC118 C

問題

最大公約数を求めればよい。

ただし、AtCoderのpython3の実行環境は3.4.3のため、math.gcdが使えない。

そのため、fractions.gcdを使う。

from fractions import gcd
n = int(input())
A = list(map(int, input().split()))
ans = A[0]
for a in A[1:]:
    ans = gcd(ans, a)
print(ans)

ABC118 B

問題

1人の場合は、その人が答えた食べ物の種類数が答え。

2人以上の場合は、1人目からN人目までの好きな食べ物の&をとればよい。

n, m = map(int, input().split())
ans = set(input().split()[1:])
for _ in range(n - 1):
    ans &= set(input().split()[1:])
print(len(ans))

ABC118 A

問題

bをaで割り切れたら、a + b を出力。

そうでなければ、b - a を出力

a, b = map(int, input().split())
print(a + b if b % a == 0 else b - a)

No787

問題

分かりやすいように、AとBを設定。

A：裏切り者でないのに裏切り者だと判定

B：裏切り者に対し、裏切り者と判定

とすると、計算式は以下のようになる。

P, Q = map(float, input().split())
print(P * Q * 100 / (P * Q + (100 - P) * (100 - Q)))

No786

問題

フィボナッチ数列

n = int(input())
ans = [1, 1] + [0] * 100
for i in range(2, n + 1):
    ans[i] = ans[i - 2] + ans[i - 1]
print(ans[n])

No785

問題

分かりやすいように変数を定義

R：赤が表示できる文字数

G：緑が表示できる文字数

B：青が表示できる文字数

上記より、カラーコードのイメージは

#RRGGBB

のようになるので、

「R * R * G * G * B * B」

を出力すればいい。

ans = 1
for s in (input() for _ in range(3)):
    if s == "NONE":
        ans *= 256
    else:
        ans *= (15 - s.count(',')) ** 2
print(ans)