htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Grand Contest 019 参戦記

oo---- 1428 -> 1425 (-3)

A - Ice Tea Store

結果:AC
Submission #1539280 - AtCoder Grand Contest 019 | AtCoder

アイスティーは1/4リットル・1/2リットル・1リットル・2リットルの4種類の値段が付いているが、購入するアイスティーはN(整数)リットルであるため、最も安く買うためには1/4リットル・1/2リットル・1リットルの中から複数種類を買う必要はない。よって1リットルの最安はmin(Q*4, H*2, S)であり、2リットルの単価のほうが安いケース、さらにNが奇数であるケースを考慮してアレする(適当)。

B - Reverse and Compare

結果:AC(5WA)
Submission #1544332 - AtCoder Grand Contest 019 | AtCoder

文字数をNとするとすべての文字がユニークならばN*(N-1)//2+1通りで、この中からダブりを引いていくのだが、どうすればいいか思いつかなかったのでシミュレートする関数を立てて色々文字列を食わせてみた。

def hoge(s):
    _set = set()
    add = _set.add
    add(s)
    l = len(s)
    for i in range(l, 0, -1):
        for j in range(l-i+1):
            s1 = s[:j]
            s2 = s[j:i+j][::-1]
            s3 = s[i+j:]
            add(s1+s2+s3)
    return len(_set)

print(hoge(s))

abcdefg
abcdeff
abcdeee
abcdddd

とか試したら各アルファベットにおけるダブリ文字数をniとするとni*(ni-1)//2分減ってたのがわかったのでそのように実装しました(思考停止)。

問題は1文字だけひっくり返す(=元の文字列そのままにする)ことができないと勘違いしていたため、2文字以上ひっくり返さないといけない=文字列によっては元の文字列が結果に入るケース(どっかでs[i] == s[i+1] or s[i] == s[i+2]が成り立つ場合かな?)と入らないケースがあると考え、不必要な場合分けを入れてWA生やしまくった。問題文を読み違えて大爆死したの久しぶりで反省しきり。