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"を出力しました。入力が１文字だけの時ループ内の処理を一回も行うことなく抜けてしまうことを見落としていて一回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")

ABC045を解いてみた

abc045.contest.atcoder.jp

A問題

　台形の面積の公式を実装するだけです。

a = int(input())
b = int(input())
h = int(input())

print(int((a+b)*h/2))

B問題

　Sa, Sb, Sc <= 100 と制約がゆるいので条件に従ってシミュレーションしました。O(100^3)なので問題ないはず。とりあえずで書いたら冗長な形になってしまった。

import sys

stra = input()
strb = input()
strc = input()

flag = 1

while True:
    if flag == 1:
        if len(stra) == 0:
            print("A")
            sys.exit()
        if stra[0:1] == 'a':
            flag = 1
        elif stra[0:1] == 'b':
            flag = 2
        elif stra[0:1] == 'c':
            flag = 3
        stra = stra[1:len(stra)]
    elif flag == 2:
        if len(strb) == 0:
            print("B")
            sys.exit()
        if strb[0:1] == 'a':
            flag = 1
        elif strb[0:1] == 'b':
            flag = 2
        elif strb[0:1] == 'c':
            flag = 3
        strb = strb[1:len(strb)]
    elif flag == 3:
        if len(strc) == 0:
            print("C")
            sys.exit()
        if strc[0:1] == 'a':
            flag = 1
        elif strc[0:1] == 'b':
            flag = 2
        elif strc[0:1] == 'c':
            flag = 3
        strc = strc[1:len(strc)]

C問題

　10の分割数は確か50くらいだったので+を入れる全てのパターンについて考えても問題なく動くと考え全パターンについて考える方針で実装しました。itertools.combinations()とjoin()とsplit()を活用して実装しました。

import itertools

s = input()
n = [i for i in s]
ans = 0

# +の個数
for i in range(len(n)):
    # +を入れるパターンを全探索
    for j in itertools.combinations(range(len(n)-1), i):
        temp = [i for i in s]
        # +を挿入
        for k in j[::-1]:
            temp.insert(k+1, "+")
        # list から 文字列に
        temp = "".join(temp)
        # +で区切ってリストに
        temp = temp.split("+")
        # リストの要素をint型に変換して総和を足す
        temp = map(int, temp)
        ans += sum(temp)

print(ans)

D問題

　h, w <= 10^9 と非常に大きくh, w回のループを回すのは無理そうです。n<=10^5と小さいのでn回のループで処理を行う方針で行ければ実行時間は問題なさそうです。１つの黒マスについて3×3の範囲を確かめることで全ての3×3マスの四角形について黒マスが何個あるのかを調べられます。その後配列の要素別の個数をカウントするところでO(HW)の方法しか思い浮かばず詰まってしまいました…　pair型でソートする方法で実装しました。Pythonのtupleやpairについて学べてよかったです。

from collections import Counter, defaultdict
h, w, n = map(int, input().split())
ab = [[int(i)-1 for i in input().split()] for j in range(n)]

d = defaultdict(int)

for i in range(n):
    for j in range(3):
        for k in range(3):
            if ab[i][0] - j >= 0 and ab[i][1] - k >= 0 and ab[i][0] - j < (h - 2) and ab[i][1] - k < (w - 2):
                d[(ab[i][0]-j, ab[i][1]-k)] += 1

print((h-2)*(w-2)-len(d))

c = Counter(d.values())
for i in range(1, 10):
    print(c[i] if i in c else 0)

ABC046を解いてみた

abc046.contest.atcoder.jp

A問題

　内包表現を使って入力を受けとり、set関数で重複を削除した配列の長さをlen()で数えました。

print(len(list(set([int(i) for i in input().split()]))))

B問題

　一番左のボールに塗る色がk種類あり、その右のボールの色はk-1種類、その右のボールの色もk-1種類とボールがn個続いていくので結果はk*(k-1)^(n-1)となります。あとは実装するだけです。

n, k = map(int, input().split())

ans = k
for _ in range(n-1):
    ans *= (k-1)

print(ans)

C問題

　得票数がそれぞれt, aで次の票数の比がi:jとすると ni >= t and nj >= a となるnを探し、得票数は t=ni, a=njとすれば求めることができます。tとaについて無駄に計算する方法しか思い浮かばず解法を考えつくのに時間がかかってしまいました…

import math

n = int(input())
ta = [[int(i) for i in input().split()] for j in range(n)]

a = 1
b = 1
for i in range(n):
    #n = max(math.floor(a/ta[i][0]), math.floor(b/ta[i][1]))
    n = max(~-a//ta[i][0] + 1, ~-b//ta[i][1] + 1)
    a = n * ta[i][0]
    b = n * ta[i][1]

print(a+b)

D問題

　答えとなる文字列をまず全てgと仮定します。そしてgからpに変えるとき、その箇所の入力がgであっても0→1で+1点、pであっても-1→0で+1点で等しいため、位置にかかわらず可能な限り多くの数のgをpに置き換えれば求めることができます。答えとなる文字列を求め、入力と照らし合わせて点数を確かめていけばO(N)=O(10^5)で時間内に答えを求めることができます。

s = input()

t = int(len(s)/2)
ans_left = 'g' * (len(s)-t)
ans_right = 'p' * t
ans = ans_left + ans_right
ret = 0

for i in range(len(s)-t):
    if(s[i:i+1] == 'p'):
        ret -= 1

for i in range(len(s)-t, len(s)):
    if(s[i:i+1] == 'g'):
        ret += 1

print(ret)

動的計画法

蟻本の動的計画法の漸化式を求める方法を実践してみたメモ

例１　ABC021のD問題
abc021.contest.atcoder.jp

　まず深さ優先探索で全探索を行う。a_i = numのときの取りうるパターン数を返す関数dfs(i, num)をつくり再帰処理を用いて計算しました。

# DFS
n = int(input())
k = int(input())

dp = [[0 for i in range(n)] for j in range(k)]
mo = 1000000007

# a_i = numのときに取りうるパターン数を返す
def dfs(i, num):
    count = 0

    # パターン数は1で確定
    if(i == k):
        return 1

    # a_i+1のときに取りうる状態をすべて試す
    for j in range(n-num+1):
        count = (count + (dfs(i+1, num+j) % mo)) % mo

    return count % mo

ans = 0
# a_1 = 1, 2, 3, … , n　について探索
for i in range(1, n+1):
    ans = (ans + dfs(1, i)) % mo
print(ans)

　次にメモ化再帰の形に書き換えます。記録用の変数dp[i][j]を用意してdfs(i, num)のときの結果をdp[i][num]に保管します。

# メモ化再帰
n = int(input())
k = int(input())

dp = [[0 for i in range(n)] for j in range(k)]
mo = 1000000007

def dfs(i, num):
    count = 0
    # 1 <= i、1 <= a_i なので0から始まる配列に合わせて-1
    # すでに一度探索していれば保管された変数を返す
    if(dp[i-1][num-1] != 0):
        return dp[i-1][num-1]

    if(i == k):
        return 1

    for j in range(n-num+1):
        count = (count + (dfs(i+1, num+j) % mo)) % mo

    # dfs(i, num) の返り値を保存
    dp[i-1][num-1] = count % mo
    return count % mo

ans = 0
for i in range(1, n+1):
    ans = (ans + dfs(1, i)) % mo
print(ans)

ここで変数dp[i][j]がどのように変化しているのかを見てみると、

dp[k-1][j] = 1
dp[i][j]   = dp[i+1][j]  (j == n-1)
             dp[i+1][j] + dp[i][j+1]  (j != n-1)

という漸化式で表せます。
i == kのときはjの値にかかわらず1パターンしかありえません。また、表の右及び下の値の和がそのマスの値になります。そこで再帰を用いた表現を使わずに２重ループを用いることで表せることがわかります。

# 動的計画法
n = int(input())
k = int(input())

dp = [[0 for i in range(n)] for j in range(k)]
# i == k-1のときは全て1
for i in range(n):
    dp[k-1][i] = 1

mo = 1000000007

# 漸化式に従って計算　右下から左上の方向へ探索
for i in range(1, k):
    _i = k-i-1
    for j in range(n):
        _j = n-j-1
        # 一番右の列のとき
        if(_j == n-1):
            dp[_i][_j] = dp[_i+1][_j] % mo
        # それ以外の時
        else:
            dp[_i][_j] = (dp[_i+1][_j] + dp[_i][_j+1]) % mo

ans = 0
for i in range(n):
    ans = (ans + dp[0][i]) % mo

print(ans)

ABC021を解いてみた

A問題

　nが8より大きいか、4より大きいか…と貪欲的に判定していきました。
A問題にしては難しいなーと思ったら数字の重複可能なことを見逃してました…

n = int(input())

flag = [0 for _ in range(4)]
count = 0

if n >= 8:
    flag[3] = 1
    n -= 8
    count += 1
if n >= 4:
    flag[2] = 1
    n -= 4
    count += 1
if n >= 2:
    flag[1] = 1
    n -= 2
    count += 1
if n >= 1:
    flag[0] = 1
    n -= 1
    count += 1

print(count)

for i in range(4):
    if flag[i] == 1:
        print(2 ** i)

B問題

　入力例を見て考えると、同じ街を通っていれば最短経路ではないといえそうです。
そこで始点、終点、経由した街に重複がなければYESを出力すれば良さそうです。

import sys

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

p.append(a)
p.append(b)

# 重複確認
for i in range(len(p)):
    for j in range(len(p)):
        if i != j and p[i] == p[j]:
            print("NO")
            sys.exit()

print("YES")

C問題

　ワーシャルフロイド法を用いて始点から全ての点への最短経路を求め、始点からメモ化再帰で最短経路を数えたつもりだったんですがREが出てしまいました…　手元の環境では実行時エラーが出せず、直せません…

D問題

　深さ優先探索→メモ化再帰→動的計画法とアルゴリズムを変えていき計算量O(nk)で部分点解法になりました。

# メモ化再帰
n, k = map(int, input().split())

dp = [[0 for i in range(n)] for j in range(k)]
mo = 1000007

def dfs(i, num):
    count = 0
    if(dp[i-1][num-1] != 0):
        return dp[i-1][num-1]
    # print("i:{0} num:{1}".format(i, num))

    if(i == k):
        return 1

    for j in range(n-num+1):
        count = (count + (dfs(i+1, num+j) % mo)) % mo

    dp[i-1][num-1] = count % mo
    print("dp[{0}][{1}] = {2}".format(i-1, num-1, dp[i-1][num-1]))
    return count % mo

ans = 0
for i in range(1, n+1):
    ans = (ans + dfs(1, i)) % mo
print(ans)

# 動的計画法
n = int(input())
k = int(input())

dp = [[0 for i in range(n)] for j in range(k)]
for i in range(n):
    dp[k-1][i] = 1

mo = 1000000007

for i in range(1, k):
    _i = k-i-1
    for j in range(n):
        _j = n-j-1
        if(_j == n-1):
            dp[_i][_j] = dp[_i+1][_j] % mo
        else:
            dp[_i][_j] = (dp[_i+1][_j] + dp[_i][_j+1]) % mo

ans = 0
for i in range(n):
    ans = (ans + dp[0][i]) % mo

print(ans)

次に解説を読んで重複組み合わせの考え方を用いてO(NlogP)で実装したつもりなんですがTLEでした…

n = int(input())
k = int(input())

mod = 1000000007

# 二分累乗法
def pow(x, n, mo):
    if n == 0: return 1
    if n == 1: return x

    if (n%2)==0:
        return ((pow(x, n/2, mod) % mo) ** 2) % mo
    else:
        return (x * (((pow(x, int(n/2), mod) % mo) ** 2) % mo)) % mo

fact = [0 for i in range(n+k)]
ifact = [0 for i in range(n+k)]
fact[0] = 1
ifact[0] = 1

for i in range(1, n+k):
    fact[i] = fact[i-1] * i % mod
    ifact[i] = pow(fact[i], mod-2, mod)

ret = (fact[n+k-1]*ifact[k]%mod)*ifact[n-1]%mod
print(ret)

ABC020を解いてみた

A問題

　qの値に合わせて出力する内容を変えます。

q = int(input())

if q == 1:
    print("ABC")
else:
    print("chokudai")

B問題

　文字列として入力をそれぞれ受け取り連結しました。そして、整数型に変換して2倍したものを出力しました。

a, b = input().split()

c = a + b
c = int(c)

print(c*2)

C問題

　全探索する方法しか思いつかなかったので解説を見ました。蟻本を参考にダイクストラ法と二分探索を組み合わせて実装しましたが、全てのケースでREになってしまいました…　手元の環境でREを再現できない…

import math
#入力
h, w, t = map(int, input().split())
board = [[i for i in input()] for j in range(h)]

# route_list[i][j] は i から j へのコスト
# ノードの番号は左上が0で右下が最大　
# 0 1 2 3
# 4 5 6 7 みたいな感じ
route_list = [[math.inf for i in range(h*w)] for j in range(h*w)]
moveCol = [0, 0, 1, -1]
moveRow = [1, -1, 0, 0]

low = 1
high = t
mid = int((low + high) / 2)

while True:
    # 入力をグラフとして隣接行列の形に落とし込む
    for i in range(w):
        for j in range(h):
            # 探索元のノードの番号
            current_node_num = (j * w) + i

            # startとgoalのノードの番号
            if(board[j][i] == 'S'):
                start_node_num = j * w + i
            elif(board[j][i] == 'G'):
                goal_node_num = j * w + i

            for k in range(4):
                # つながっている次のマスはどこか
                nextx = i + moveCol[k]
                nexty = j + moveRow[k]
                # print("i:{0} j:{1} k:{2} nextx:{3} nexty:{4}".format(i, j, k, nextx, nexty))

                #　次のマスが枠外になっていなかったら
                if( 0 <= nextx and nextx < w and 0 <= nexty and nexty < h):
                    # 次のマスのノードの番号
                    next_node_num = nexty * w + nextx

                    # 次に行くのが黒いマス 黒いマスにうつるのはx秒かかる
                    if(board[nexty][nextx] == '#'):
                        route_list[current_node_num][next_node_num] = mid
                    else:
                        route_list[current_node_num][next_node_num] = 1

    # スタートからの最短距離
    d = [math.inf for i in range(w*h)]
    # 使われたかのフラグ
    used = [False for i in range(w*h)]

    # 始点への距離は0
    d[start_node_num] = 0

    # ダイクストラ法
    while True:
        v = -1
        # まだ使われていない頂点のうち距離が最小のものを探す
        for u in range(h*w):
            if ((not used[u]) and (v == -1 or d[u] < d[v])): v = u

        # すでに全部探索していればループを抜ける
        if(v == -1):
            break
        # 番号vの使用されたかのフラグをTrueにする
        used[v] = True

        # 今までのと今回のループで短いほうを最小の距離とする
        for u in range(w*h):
            d[u] = min(d[u], d[v] + route_list[v][u])

    # 時間内にたどり着けるなら
    if(d[goal_node_num] <= t):
        low = mid
    else:
        high = mid
    mid = int((low + high) / 2)

    # 条件を満たすまで２分探索
    if(high - low == 1):
        break

    #print("low:{0} mid:{1} high:{2}".format(low, mid, high))

print(low)

D問題

　自力では15点まで、解説読んで100点分までは実装できました。満点解法は包除定理の実装部分で詰まったのでできたら追記します…

ABC019を解いてみた

A問題

　入力を配列として受け取り、sort関数を用いてsortしたあと中間の要素を出力しました。

a = [int(i) for i in input().split()]

a.sort()
print(a[1])

B問題

　変数sに入力の文字列を受け取り、先頭から連続した文字が何個続くのかを求め、文字と続く個数を答えの変数に追加、そして答えに入力した分を文字列sから取り除きます。この処理をsがなくなるまで繰り返すことで答えを求めました。

# 文字列sの先頭から同じ文字が何個連続しているのかを返す
def countConsectiveCharacter(s):
    # 少なくとも1文字は連続している
    cnt = 1
    for i in range(len(s)-1):
        if(s[i] == s[i+1]):
            cnt += 1
        else:
            return cnt
    return cnt

# 入力
s = input()

i = 0
ans = ""
while len(s) > 0:
    c = countConsectiveCharacter(s)
    ans += s[0] + str(c)
    # sがなくなったら終了
    if len(s) == c:
        break
    # c番目からの文字を切り出してsに代入
    else:
        s = s[c:]
    #print("s[i], c, ans")
    #print(s, c, ans)

print(ans)

C問題

　全探索ではO(n^2)と部分点の制約しかクリアできそうにありません。そこで工夫した方法を考えると、xと2xが等しくなるならば要素の値を2で割り切れなくなるまで割っていき、異なる要素の個数を数えることで結果を求めることができます。これならば計算量はO(n)で実行時間には問題なさそうです。

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

# 各要素について適用
for i in range(len(a)):
    # 2で割り切れなくなるまで割っていく
    while(a[i] % 2 == 0):
        a[i] = int(a[i]/2)

# setでリストの重複を取り除き、listで配列化　lenでその要素数を数える
print(len(list(set(a))))

D問題

　問題文を読んでまず出力の形式に驚きました…　解説に基づいて実装しました。