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

水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

ABC 032に参加しました

3.34完.79位.334点の人の中では一番点数が高かったので,良しとしよう(4完できなかったのでダメ)


公式の解説スライドはこちら


http://www.slideshare.net/chokudai/abc032


A問題

abc032.contest.atcoder.jp

回答

Submission #605956 - AtCoder Beginner Contest 032 | AtCoder

繰り返しで,a,b 両方の剰余が0になるような値を求める.


本当は最大公約数を用いて解くべきであろうが,制約を見て愚直実装をした.

a, b, c = [int(input()) for _ in range(3)]
res = c
while True:
    if res % a == 0 and res % b == 0:
        print(res)
        break
    res += 1

B問題

abc032.contest.atcoder.jp


回答

Submission #606181 - AtCoder Beginner Contest 032 | AtCoder


分割した文字列をsetにどんどん追加していく.setのsizeが答え.

s = input()
n = int(input())
     
slen = len(s)
res = set([])
for i in range(slen-n+1):
    res.add(s[i:i+n])
print(len(res))

C問題

abc032.contest.atcoder.jp


回答

Submission #606608 - AtCoder Beginner Contest 032 | AtCoder


しゃくとり法を知っていたので,しゃくとり法で.とりあえず伸ばせるだけのばして,伸ばせなくなったら前の方を詰めて,みたいなやり方です.


ただし,入力値に0が含まれていればN, k == 0の時は0にするように先に判定しておく必要あり.

n, k = map(int, input().split())
sli = [int(input()) for _ in range(n)]
if 0 in sli:
    print(n)
    exit(0)
if k == 0:
    print(0)
    exit(0)
sidx = 0
eidx = 0
sumnum = 1
res = 0
for i in range(n):
    sumnum *= sli[i]
    if sumnum > k:
        eidx = i
        res = max(res, eidx - sidx)
        while sumnum > k:
            sumnum /= sli[sidx]
            sidx += 1
print(max(res, n - sidx))

D問題

34点分しかとれず.

abc032.contest.atcoder.jp


回答(34点分)


Submission #607525 - AtCoder Beginner Contest 032 | AtCoder


想定解じゃなかった.(小並感)


私の開放では,dictで値を持っておいてdpみたいな形でした,愚直にmapで殴ったというべきか….それで,最大値を求めると.


結構さっくりとコードが書けたので,個人的には短くて満足です.


結局,想定としては条件ごとに分割するのが正義みたい.途中から自分もそれに気づいたのですが,どうもPythonだとTLE多発させてしまい,しかも上記のコードのテストの状況から全く進展しないという….


一応,私が目指していた解放は,1<=w<=1000の場合はほぼ方針が一緒でしたが,これで通らないのはなんでという感じ….やっぱりDPとLL系言語は相性が悪そう.C++で書きなおそうか思案中です.誰かがPythonのコードを公開してくれれば,それでもいいのですが.


ただ,部分点を自力で取れたのはね,良かったと思います.(総合的な結果見ても今回3.34完で78位であったし,少し難し目のABCだったのかもしれません.)

N, W = map(int, input().split())
dp = {}
viwi = [[int(x) for x in input().split()] for _ in range(N)]
for i in range(N):
    vi, wi = viwi[i][0], viwi[i][1]
    adddic = {}
    for k, v in dp.items():
        if (k + wi) <= W:
            if (k + wi) in dp:
                adddic[k + wi] = max(dp[k] + vi, dp[k + wi])
            else:
                adddic[k + wi] = dp[k] + vi
    if wi <= W:
        adddic[wi] = vi
    dp.update(adddic)
print(max(dp.values()))

あと若干テストケース弱かった疑惑ありますが,私もdpのdict内に同じ要素が存在しているかどうかをチェックせずに上書きして追加していたのに通ったので,今回本当に弱かった説がありますね….解説に乗っている方法も,全部明らかに損みたいな積み荷ばかりしかない場合にどう対処するのかなあと.




ただ,4完できなかったのは本当に悔しいな? くそ…


9 / 300