ferinの競プロ帳

競プロについてのメモ

ABC044を解いてみた

abc044.contest.atcoder.jp

A問題

 k < n のとき ans = k*x + (n-k)*y
 k >= n のとき ans = n*x と場合分けできるのでそれに従って実装するだけです。

n = int(input())
k = int(input())
x = int(input())
y = int(input())

if k < n:
    ans = k*x+(n-k)*y
else:
    ans = n*x
print(ans)

B問題

 入力をソートして同じ文字が連続している個数を数え、奇数のものが一つでもあれば"No"を、なければ"Yes"を出力しました。入力が1文字だけの時ループ内の処理を一回も行うことなく抜けてしまうことを見落としていて一回WAを出してしまいました…

import sys
w = list(input())
w.sort()

if len(w) == 1:
    print("NO")
    sys.exit()

count = 1
for i in range(1, len(w)):
    if w[i] == w[i-1] :
        count += 1
    else:
        if count % 2 == 1:
            print("No")
            sys.exit()
        count = 1

print("Yes")

C問題

 深さ優先探索を書いて、それからメモ化再帰の形に書き換えました。O(xn^3) ≒ O(3*10^7) 程度の計算量で問題ないと思ったんですがTLE…

n, a = map(int, input().split())
x = [int(i) for i in input().split()]

dp = [[[0 for i in range(n+1)] for j in range(n+1)] for k in range(50*n+1)]
count = 0

# 今見ているのがi番目、選んでいるカードがj枚、今の合計がsum
def dfs(i, j, sum):
    global count
    # すでに記録されていれば記録を返す(メモ化再帰)
    if dp[sum][j][i] != 0:
        return dp[sum][j][i]

    if i == n:
        if sum == a*j and j != 0:
            return 1
        else:
            return 0

    # x[i] を 選ぶ場合と選ばない場合
    dp[sum][j][i] = dfs(i+1, j, sum) + dfs(i+1, j+1, sum + x[i])
    return dp[sum][j][i]

print(dfs(0, 0, 0))

動的計画法で実装するところで詰まってしまい、kissgeさんのコードを見てcollectionsを使って実装しました。Submission #855383 - AtCoder Beginner Contest 044 | AtCoder

D問題

 全探索する方法しか思い浮かばなかったので解説をみて実装しました。<= sqrt(n) や < sqrt(n) の境界を表す方法で時間がかかってしまったのと、b > sqrt(n) のときにp:1->sqrt(n)とループしていたためにbが大きい方から試してしまっていてbの最小値を算出できていなかったところでハマってしまいWA連発&時間をかけてしまいました…
あとデバッグで使ったprint文を消し忘れていて無駄にWAを出してしまったので本番でやらかさないよう気をつけたいです。

import math, sys

n = int(input())
s = int(input())

def f(b, n):
    if n < b:
        return n
    else:
        return f(b, math.floor(n/b)) + n % b

if s == n:
    print(n+1)
    sys.exit()

# b <= sqrt(n) のとき
for b in range(2, math.floor(math.sqrt(n))+1):
    if(f(b, n) == s):
        print(b)
        sys.exit()

# b > sqrt(n)のとき
for p in range(1, math.floor(math.sqrt(n))+1):
    _p = math.floor(math.sqrt(n))+1-p
    b = int((n-s)/_p) + 1
    if(b >= 2 and f(b, n) == s):
        print(b)
        sys.exit()

print("-1")