Zenn
🐷

AtCoder ARC110 鹿島建設プログラミングコンテスト2020 個人的メモ

2020/12/06に公開
Python
#
競技プログラミング
AtCoder
tech

所感

ab2完
bは残り1分半でacした
今回もめっちゃ冷えるかと思ってたので良かった
でも冷えてるのは良くない
やっぱり考察が細部まで詰め切れてないのが良くない

arc110score

A - Redundant Redundancy

答えをXとする
問題よりXは2からNの全ての数で割った時，余りが1
よって，X-1は2~Nの全ての数で割り切れる
2からNの全てで割り切れるのは，2からNの全ての数の公倍数
なので，(最小公倍数)+1を出力すればおｋ

#!/usr/bin/env python3
from math import gcd
from functools import reduce

N = int(input())

ans = reduce(lambda a, b: a * b // gcd(a, b), range(2, N + 1)) + 1
print(ans)

B - Many 110

考察がしっちゃかめっちゃか
おかげでコードも汚い
そのせいで8waもしてる

まず，Tから"110"を除く
その後のTの長さで場合分け

  • |T|=0の場合
    この場合，Tは"110"のみで構成されていると分かる

  • |T|=1の場合
    2通りの場合がある

    • Tの先頭が"110"の後尾である"0”
    • Tの後尾が"110"の先頭である"1"

  • |T|=2の場合
    3通りの場合がある

    • Tの先頭が"110"の後尾である"0”かつTの後尾が"110"の先頭である"1"
    • Tの先頭が"110"の後尾2文字である"10"
    • Tの後尾が"110"の先頭2文字である"11"

  • |T|=3の場合
    2通りの場合がある

    • Tの先頭が"110"の後尾である"0”かつTの後尾が"110"の先頭2文字である"11"
    • Tの先頭が"110"の後尾2文字である"10”かつTの後尾が"110"の先頭である"1"

  • |T|=4の場合
    Tの先頭が"110"の後尾2文字である"10”かつTの後尾が"110"の先頭2文字である"11"

  • 上記以外の場合
    "110"が連続した文字列Sの中にTは含まれない

上記の場合分けでいずれかに該当する場合はTがS中に含まれるので答えを計算する
計算方法はうまく言葉にならなかった
その内書くかもしれない

解説は0に注目してた
なるほどなぁって思った
うまい考えがあるもんだ
想定解でのコードもその内載せたい

#!/usr/bin/env python3
N = int(input())
T = input()

T = T.replace("110", "")

res = False
ans = 0
if len(T) == 4 and T[:2] == "10" and T[-2:] == "11":
    res = True
elif len(T) == 3:
    if (T[0] == "0" and T[-2:] == "11") or (T[:2] == "10" and T[-1] == "1"):
        res = True
        ans -= 1
elif len(T) == 2:
    if T[:2] == "10" or T[-2:] == "11" or (T[0] == "0" and T[-1] == "1"):
        res = True
        if (T[0] == "0" and T[-1] == "1"):
            ans -= 1
elif len(T) == 1:
    if T[0] == "0" or T[-1] == "1":
        res = True
elif len(T) == 0:
    res = True

if res:
    res = -(-N // 3) - 1
    ans += 10 ** 10 - res
    if N == 1 and T == "1":
        ans *= 2
    print(ans)
else:
    print(0)

参考

Discussion