モノグサプログラミングコンテスト2024（AtCoder Beginner Contest 345）振り返り

最初に振り返り

前回は５完までいけたのだが、今回は A~C の 3完という結果に…

C は「これでなんで通らないの…?」って WA を重ねてしまいスコアを落としてしまったので、詰まったときはナイーブな実装に変えて結果を確かめるのは大事ですね。

D は制約条件見て、単純に全探索で大丈夫かなと安易に考えてしまった。マップ系の DFS, Backtrack もサッと描くことができなかったので同じような問題といてみて精進あるのみですね。

A - Leftrightarrow

< , = , > からなる３文字以上の文字列が与えられるので、 <===> のように < ではじまって > で終わる文字列になっているか確かめる問題。

最初と最後と間の文字列をすべてチェックすればOK

#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(S: str):
    res = (S[0] == "<") and (S[-1]==">") and all([x == "=" for x in S[1:-1]])
    print(YES if res else NO)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()

B - Integer Division Returns

最初単純に math.ceil(X/10) を使って切り上げを行ったらテストケースに失敗。

テストケースに 123456789123456789 のケースが書かれていて、だいぶ親切なように感じた。

Python でいうと、浮動小数点は 64ビットの倍精度浮動小数点で保存される。このとき仮数部に持てるのは 52ビットで、有効数字は 15桁ほどにしかならない (Wikipedia)

123456789123456789 は桁数の溢れがあり、 /10 で割り算をして浮動小数点になってしまうと値がずれてしまうため、整数のまま計算を行うことで算出することができる。

$\displaystyle y = \frac{x + (b-1)}{b}$

で計算をして少数を切り捨てることで、整数のまま切り上げの計算をすることができる。

#!/usr/bin/env python3
import sys

def solve(X: int):
    res = (X+9) // 10
    print(res)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    solve(X)

if __name__ == '__main__':
    main()

C - One Time Swap

ちょうど一回だけ文字列の交換を行い、その結果の文字列が何種類出るかを計算する問題。

２文字目以降から初めて、それまでに出てきた文字数から、同じ文字数の出現数を差し引いた数を足し合わせれば行けるじゃんと思ってすぐ提出する。結果 TLE。

もっと単純になアルゴリズムで

passed = set()
l = list(S)
for i in range(1, n):
    for j in range(0, i):
      l[i], l[j] = l[j], l[i]
      passed.add("".join(l))
      l[i], l[j] = l[j], l[i]

のようにして、結果を見ると、元々の文字列が含まれるケースが有ることも気づく。

ちょうど一回だけ 文字列の交換を行うというのがミソで、同じ文字列が複数回出る場合は元々の文字列も足し合わせる必要がある。一方ですべての文字列が１回しか出ないパターンは足し合わせる必要はない。

同一文字列が複数回出るパターンが有るか? を確認して足し合わせるようにして AC。

#!/usr/bin/env python3
import sys
from collections import defaultdict

def solve(S: str):
    patterns = 0
    passed = defaultdict(int)
    passed[S[0]] += 1
    total = 1

    for s in S[1:]:
        add = total - passed[s]
        patterns += add
        passed[s] += 1
        total += 1
    if any([x > 1 for x in passed.values()]):
        patterns += 1
    print(patterns)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()

D - Tiling

面積の大きいタイルから置き始め、全探索したらいけるのでは？と考え、

面積の多い順に Tile を並べ替え
置けそうなところを90度回転も含めて虱潰しにチェック

で行おうとしたが、 WA & TLE。枝切りも試してみたが時間間に合わずタイムアップ。

解説を見て、修正したのが以下のコード。

解説では、”タイルの使用する順番とタイルの置く向きが決まればタイルの置く場所は一意に決まる”、”常に埋めるべきマップの最上段且つ左端のマスを埋めるようにして、タイルの使用する順番とタイルの置く向きを探索する” と書かれていてそのように修正した。

とりあえず虱潰しにするのだけだと、 TLE になってしまうので、”何を探索しようとしているのか?” を意識して探索するのが重要なんだなというのは学び。

コードは backtrack っぽく書いて AC。

def yasuharu519(self):

日々の妄想